added problems

AlveeM · AlveeM · commit f7f7d43e6f92 · 2021-03-26T10:17:53.000-04:00
diff --git a/leetcode/top-interview-questions/02_medium_collection/03_trees_and_graphs/03_construct_binary_tree_from_preorder_and_inorder.py b/leetcode/top-interview-questions/02_medium_collection/03_trees_and_graphs/03_construct_binary_tree_from_preorder_and_inorder.py
@@ -0,0 +1,23 @@
+class Solution:
+    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
+        n = len(inorder)
+        if n == 0: return None
+        
+        self.inorder = inorder
+        self.preorder = preorder
+        self.ino_map = {val: idx for idx, val in enumerate(inorder)}
+        self.p_idx = 0
+        
+        return self.buildTreeRec(0, n - 1)
+        
+    def buildTreeRec(self, start, end):
+        if start > end: return None
+        
+        root_val = self.preorder[self.p_idx]
+        self.p_idx += 1
+        root = TreeNode(root_val)
+        ino_idx = self.ino_map[root_val]
+        
+        root.left = self.buildTreeRec(start, ino_idx - 1)
+        root.right = self.buildTreeRec(ino_idx + 1, end)
+        return root
diff --git a/leetcode/top-interview-questions/02_medium_collection/03_trees_and_graphs/04_populating_next_right_pointer.py b/leetcode/top-interview-questions/02_medium_collection/03_trees_and_graphs/04_populating_next_right_pointer.py
@@ -0,0 +1,59 @@
+from collections import deque
+
+class Solution:
+    def connect(self, root: 'Node') -> 'Node':
+        if not root: return root
+        
+        q = deque()
+        q.append(root)
+        
+        while q:
+            n = len(q)
+            level = []
+            
+            for _ in range(n):
+                node = q.popleft()
+                level.append(node)
+                
+                if node.left: 
+                    q.append(node.left)
+                if node.right: 
+                    q.append(node.right)
+            
+            for i in range(len(level) - 1):
+                level[i].next = level[i + 1]
+        
+        return root
+
+class Solution2:
+    def connect(self, root: 'Node') -> 'Node':
+        if not root:
+            return root
+        
+        # Start with the root node. There are no next pointers
+        # that need to be set up on the first level
+        leftmost = root
+        
+        # Once we reach the final level, we are done
+        while leftmost.left:
+            
+            # Iterate the "linked list" starting from the head
+            # node and using the next pointers, establish the 
+            # corresponding links for the next level
+            head = leftmost
+            while head:
+                
+                # CONNECTION 1
+                head.left.next = head.right
+                
+                # CONNECTION 2
+                if head.next:
+                    head.right.next = head.next.left
+                
+                # Progress along the list (nodes on the current level)
+                head = head.next
+            
+            # Move onto the next level
+            leftmost = leftmost.left
+        
+        return root 
diff --git a/leetcode/top-interview-questions/02_medium_collection/03_trees_and_graphs/05_kth_smallest_element_in_bst.py b/leetcode/top-interview-questions/02_medium_collection/03_trees_and_graphs/05_kth_smallest_element_in_bst.py
@@ -0,0 +1,17 @@
+class Solution:
+    def kthSmallest(self, root: TreeNode, k: int) -> int:
+        self.count = 0
+        self.res = 0
+        self.inorder(root, k)
+        return self.res
+    
+    def inorder(self, node, k):
+        if not node: return
+        self.inorder(node.left, k)
+        
+        self.count += 1
+        if self.count == k:
+            self.res = node.val
+            return
+        
+        self.inorder(node.right, k)
diff --git a/leetcode/top-interview-questions/02_medium_collection/03_trees_and_graphs/06_number_of_islands.py b/leetcode/top-interview-questions/02_medium_collection/03_trees_and_graphs/06_number_of_islands.py
@@ -0,0 +1,30 @@
+class Solution:
+    def numIslands(self, grid: List[List[str]]) -> int:
+        if not grid or not grid[0]:
+            return 0
+        
+        count = 0
+        m = len(grid)
+        n = len(grid[0])
+        
+        for r in range(m):
+            for c in range(n):
+                if grid[r][c] == '1':
+                    self.markGrid(grid, r, c)
+                    count += 1
+
+        return count
+    
+    def markGrid(self, grid, r, c):
+        grid[r][c] = '2'
+        m = len(grid)
+        n = len(grid[0])
+        
+        if r - 1 >= 0 and grid[r-1][c] == '1':
+            self.markGrid(grid, r-1, c)
+        if r + 1 < m and grid[r+1][c] == '1':
+            self.markGrid(grid, r+1, c)
+        if c - 1 >= 0 and grid[r][c-1] == '1':
+            self.markGrid(grid, r, c-1)
+        if c + 1 < n and grid[r][c+1] == '1':
+            self.markGrid(grid, r, c+1)
diff --git a/leetcode/top-interview-questions/02_medium_collection/04_backtracking/01_letter_combinations_of_a_phone_number.py b/leetcode/top-interview-questions/02_medium_collection/04_backtracking/01_letter_combinations_of_a_phone_number.py
@@ -0,0 +1,30 @@
+class Solution:
+    def letterCombinations(self, digits: str) -> List[str]:
+        if len(digits) == 0: return []
+        
+        self.letters = {
+            "2": "abc",
+            "3": "def",
+            "4": "ghi",
+            "5": "jkl",
+            "6": "mno",
+            "7": "pqrs",
+            "8": "tuv",
+            "9": "wxyz"
+        }
+        
+        self.digits = digits
+        self.res = []
+        self.backtrack(0, [])
+        return self.res
+    
+    def backtrack(self, idx, path):
+        if len(path) == len(self.digits):
+            self.res.append(''.join(path))
+            return
+        
+        letters = self.letters[self.digits[idx]]
+        for letter in letters:
+            path.append(letter)
+            self.backtrack(idx + 1, path)
+            path.pop()
diff --git a/leetcode/top-interview-questions/02_medium_collection/04_backtracking/02_generate_parenthesis.py b/leetcode/top-interview-questions/02_medium_collection/04_backtracking/02_generate_parenthesis.py
@@ -0,0 +1,16 @@
+class Solution:
+    def generateParenthesis(self, n: int) -> List[str]:
+        res = []
+        
+        def backtrack(path, left, right):
+            if len(path) == n * 2:
+                res.append(path)
+                return
+            
+            if left < n:
+                backtrack(path + '(', left + 1, right)
+            if left > right:
+                backtrack(path + ')', left, right + 1)
+                
+        backtrack('', 0, 0)
+        return res
diff --git a/leetcode/top-interview-questions/02_medium_collection/04_backtracking/03_permutations.py b/leetcode/top-interview-questions/02_medium_collection/04_backtracking/03_permutations.py
@@ -0,0 +1,33 @@
+class Solution:
+    def permute(self, nums: List[int]) -> List[List[int]]:
+        self.res = []
+        self.traverse(nums, [])
+        return self.res
+    
+    def traverse(self, nums, path):
+        if len(nums) == 0:
+            self.res.append(path)
+            return
+        
+        for i in range(len(nums)):
+            new_nums = nums[:i] + nums[i+1:]
+            new_path = path + [nums[i]]
+            self.traverse(new_nums, new_path)
+
+class Solution2:
+    def permute(self, nums: List[int]) -> List[List[int]]:
+        self.visited = set()
+        self.res = []
+        self.backtrack(nums, [])
+        return self.res
+    
+    def backtrack(self, nums, path):
+        if len(nums) == len(path):
+            self.res.append(path.copy())
+            return
+        
+        for num in nums:
+            if num not in self.visited:
+                self.visited.add(num)
+                self.backtrack(nums, path + [num])
+                self.visited.remove(num)
diff --git a/leetcode/top-interview-questions/02_medium_collection/04_backtracking/04_subsets.py b/leetcode/top-interview-questions/02_medium_collection/04_backtracking/04_subsets.py
@@ -0,0 +1,12 @@
+class Solution:
+    def subsets(self, nums: List[int]) -> List[List[int]]:
+        self.res = []
+        self.backtrack(0, [], nums)
+        return self.res
+    
+    def backtrack(self, start, path, nums):
+        self.res.append(path.copy())
+        for i in range(start, len(nums)):
+            path.append(nums[i])
+            self.backtrack(i + 1, path, nums)
+            path.pop()
