added problems

AlveeM · AlveeM · commit 6afbf34d5d76 · 2020-12-11T07:45:04.000-05:00
diff --git a/leetcode/patterns/11-modified-binary-search/01_find_smallest_letter_greater_than_target.py b/leetcode/patterns/11-modified-binary-search/01_find_smallest_letter_greater_than_target.py
@@ -0,0 +1,16 @@
+class Solution:
+    def nextGreatestLetter(self, letters, target):
+        l = 0
+        r = len(letters) - 1
+        
+        if letters[0] > target or letters[-1] <= target:
+            return letters[0]
+        
+        while l < r:
+            mid = (l + r) // 2
+            if letters[mid] > target:
+                r = mid
+            else:
+                l = mid + 1
+                
+        return letters[l]
diff --git a/leetcode/patterns/11-modified-binary-search/02_first_last_pos_of_el_in_sorted_array.py b/leetcode/patterns/11-modified-binary-search/02_first_last_pos_of_el_in_sorted_array.py
@@ -0,0 +1,57 @@
+# https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
+class Solution:
+    def searchRange(self, nums, target):
+        res = [-1, -1]
+        
+        if len(nums) == 0: return res
+        if nums[0] > target or nums[-1] < target: return res
+        
+        first_idx = self.binarySearch(nums, target, True) 
+        last_idx = self.binarySearch(nums, target, False)
+        
+        return [first_idx, last_idx]
+        
+    def binarySearch(self, nums, target, isFirst):
+        idx = -1
+        l = 0
+        r = len(nums) - 1
+
+        while l <= r:
+            mid = (l + r) // 2
+            if nums[mid] == target:
+                idx = mid
+                if isFirst:
+                    r = mid - 1
+                else:
+                    l = mid + 1
+            elif nums[mid] > target:
+                r = mid - 1
+            else:
+                l = mid + 1
+
+        return idx
+
+class Solution2:
+    def searchRange(self, nums, target):
+        l = 0
+        r = len(nums) - 1
+        
+        if not nums: return [-1, -1]
+        if nums[0] > target or nums[-1] < target: return [-1, -1]
+        
+        while nums[l] != nums[r]:
+            mid = (l + r) // 2
+            if nums[mid] > target:
+                r = mid - 1
+            elif nums[mid] < target:
+                l = mid + 1
+            else:
+                if nums[l] < target:
+                    l += 1
+                elif nums[r] > target:
+                    r -= 1
+                    
+        if nums[l] == target:
+            return [l, r]
+        else:
+            return [-1, -1]
diff --git a/leetcode/patterns/11-modified-binary-search/03_search_in_a_sorted_arr_of_unknown_size.py b/leetcode/patterns/11-modified-binary-search/03_search_in_a_sorted_arr_of_unknown_size.py
@@ -0,0 +1,20 @@
+class Solution:
+    def search(self, reader, target):
+      l = 0
+      r = 1
+
+      while reader.get(r) < target:
+        r *= 2
+      l = r // 2
+
+      while l <= r:
+        mid = (l + r) // 2
+        val = reader.get(mid)
+        if val == target:
+          return mid
+        elif val > target:
+          r = mid - 1
+        else:
+          l = mid + 1
+
+      return -1
diff --git a/leetcode/patterns/11-modified-binary-search/04_peak_index_in_a_mountain_array.py b/leetcode/patterns/11-modified-binary-search/04_peak_index_in_a_mountain_array.py
@@ -0,0 +1,13 @@
+class Solution:
+    def peakIndexInMountainArray(self, arr):
+        l = 0
+        r = len(arr) - 1
+        
+        while l < r:
+            mid = (l + r) // 2
+            if arr[mid] < arr[mid+1]:
+                l = mid + 1
+            else:
+                r = mid
+                
+        return l
diff --git a/leetcode/patterns/11-modified-binary-search/05_find_peak_element.py b/leetcode/patterns/11-modified-binary-search/05_find_peak_element.py
@@ -0,0 +1,13 @@
+class Solution:
+    def findPeakElement(self, nums):
+        l = 0
+        r = len(nums) - 1
+        
+        while l < r:
+            mid = ((l + r) // 2) + 1
+            if nums[mid-1] > nums[mid]:
+                r = mid - 1
+            else:
+                l = mid
+                
+        return l
