added new problems

AlveeM · AlveeM · commit 95b1b9729b05 · 2021-03-27T21:52:31.000-04:00
diff --git a/leetcode/top-interview-questions/02_medium_collection/04_backtracking/05_word_search.py b/leetcode/top-interview-questions/02_medium_collection/04_backtracking/05_word_search.py
@@ -0,0 +1,36 @@
+class Solution:
+    def exist(self, board: List[List[str]], word: str) -> bool:
+        self.board = board
+        self.word = word
+        
+        for r in range(len(board)):
+            for c in range(len(board[0])):
+                if board[r][c] == word[0] and self.dfs(r, c, 0):
+                    return True
+                    
+        return False
+    
+    def dfs(self, r, c, idx):
+        if idx == len(self.word):
+            return True
+        
+        if self.isNotValid(r, c, idx):
+            return False
+        
+        current_char = self.board[r][c]
+        self.board[r][c] = ''
+        
+        hasWord = (self.dfs(r + 1, c, idx + 1) or
+                  self.dfs(r - 1, c, idx + 1) or
+                  self.dfs(r, c + 1, idx + 1) or
+                  self.dfs(r, c - 1, idx + 1))
+        
+        self.board[r][c] = current_char
+        return hasWord
+        
+    def isNotValid(self, r, c, idx):
+        return (r < 0 or 
+                r >= len(self.board) or
+                c < 0 or
+                c >= len(self.board[0]) or
+                self.board[r][c] != self.word[idx])
diff --git a/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/01_sort_colors.py b/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/01_sort_colors.py
@@ -0,0 +1,19 @@
+class Solution:
+    def sortColors(self, nums: List[int]) -> None:
+        """
+        Do not return anything, modify nums in-place instead.
+        """
+        low = 0
+        high = len(nums) - 1
+        i = 0
+        
+        while i <= high:
+            if nums[i] == 0:
+                nums[i], nums[low] = nums[low], nums[i]
+                i += 1
+                low += 1
+            elif nums[i] == 1:
+                i += 1
+            else:
+                nums[i], nums[high] = nums[high], nums[i]
+                high -= 1
diff --git a/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/02_top_k_frequent_elements.py b/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/02_top_k_frequent_elements.py
@@ -0,0 +1,18 @@
+from heapq import *
+from collections import Counter
+
+class Solution:
+    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
+        num_freq_map = Counter(nums)
+        min_heap = []
+
+        for num, freq in num_freq_map.items():
+            heappush(min_heap, (freq, num))
+            if len(min_heap) > k:
+                heappop(min_heap)
+        
+        top_nums = []
+        while min_heap:
+            top_nums.append(heappop(min_heap)[1])
+        
+        return top_nums
diff --git a/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/03_kth_largest_element_in_an_array.py b/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/03_kth_largest_element_in_an_array.py
@@ -0,0 +1,14 @@
+from heapq import *
+
+class Solution:
+    def findKthLargest(self, nums: List[int], k: int) -> int:
+        min_heap = []
+        for i in range(k):
+            heappush(min_heap, nums[i])
+            
+        for i in range(k, len(nums)):
+            if nums[i] > min_heap[0]:
+                heappop(min_heap)
+                heappush(min_heap, nums[i])
+        
+        return min_heap[0]
diff --git a/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/04_find_peak_element.py b/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/04_find_peak_element.py
@@ -0,0 +1,14 @@
+class Solution:
+    def findPeakElement(self, nums: List[int]) -> int:
+        l = 0
+        r = len(nums) - 1
+        
+        while l < r:
+            mid = l + (r - l + 1) // 2
+            
+            if nums[mid - 1] > nums[mid]:
+                r = mid - 1
+            else:
+                l = mid
+        
+        return l
diff --git a/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/05_search_for_a_range.py b/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/05_search_for_a_range.py
@@ -0,0 +1,33 @@
+class Solution:
+    def searchRange(self, nums: List[int], target: int) -> List[int]:
+        res = [-1, -1]
+        
+        first = self.binarySearch(nums, target, True)
+        last = self.binarySearch(nums, target, False)
+        
+        res[0] = first
+        res[1] = last
+        
+        return res
+        
+    def binarySearch(self, nums, target, first):
+        l = 0
+        r = len(nums) - 1
+        idx = -1
+        
+        while l <= r:
+            m = l + (r - l) // 2
+            num = nums[m]
+            
+            if num < target:
+                l = m + 1
+            elif num > target:
+                r = m - 1
+            else:
+                idx = m
+                if first:
+                    r = m - 1
+                else:
+                    l = m + 1
+                
+        return idx
diff --git a/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/06_merge_intervals.py b/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/06_merge_intervals.py
@@ -0,0 +1,21 @@
+class Solution:
+    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
+        if len(intervals) <= 1: return intervals
+        
+        intervals.sort(key=lambda interval: interval[0])
+        res = []
+        start = intervals[0][0]
+        end = intervals[0][1]
+        
+        for i in range(1, len(intervals)):
+            interval = intervals[i]
+            
+            if interval[0] <= end:
+                end = max(end, interval[1])
+            else:
+                res.append([start, end])
+                start = interval[0]
+                end = interval[1]
+        
+        res.append([start, end])
+        return res
diff --git a/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/07_search_in_rotated_sorted_array.py b/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/07_search_in_rotated_sorted_array.py
@@ -0,0 +1,23 @@
+class Solution:
+    def search(self, nums: List[int], target: int) -> int:
+        l = 0
+        r = len(nums) - 1
+        
+        while l <= r:
+            m = (l + r) // 2
+            
+            if nums[m] == target:
+                return m
+            
+            if nums[l] <= nums[m]:
+                if nums[l] <= target < nums[m]:
+                    r = m - 1
+                else:
+                    l = m + 1
+            else:
+                if nums[m] < target <= nums[r]:
+                    l = m + 1
+                else:
+                    r = m - 1
+        
+        return -1
diff --git a/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/08_search_in_a_2D_matrix_II.py b/leetcode/top-interview-questions/02_medium_collection/05_sorting_and_searching/08_search_in_a_2D_matrix_II.py
@@ -0,0 +1,19 @@
+class Solution:
+    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
+        if not matrix: return False
+        
+        n = len(matrix[0])
+        r = len(matrix) - 1
+        c = 0
+        
+        while r >= 0 and c < n:
+            num = matrix[r][c]
+            if num == target:
+                return True
+            elif num > target:
+                r = r - 1
+            else:
+                c = c + 1
+        
+        return False
+            
