Recursion

Challenge Given an array of positive intege, each element represents the max length, you need to find the min number of jump in order to reach the end of the array. Input: nums = [2,4,1,1,17] Output: 2 # reach to index 1 and then from there last index. Solution - Recursion (TLE) class Solution: def helper(self, nums, current_index, steps, l, previous): # ending recursion early if already above if len(previous) >= self.m: return if current_index >=l-1: self.m = min(self.m, len(previous)) return for i in range(1, steps + 1): if current_index + i < l: self.helper(nums, current_index + i, nums[current_index + i],l, previous + [1]) def min_jump(self, nums: List[int]): if not nums: return 0 self.m = float('inf') previous = [] self.helper(nums, 0, nums[0], len(nums), previous) return self.m Solution 2 - Memoization class Solution: def helper(self, nums, current_index): if current_index >= len(nums)-1: return 0 if current_index in self.memo: return self.memo[current_index] steps = nums[current_index] for i in range(1, steps+1): self.m = min(self.m, 1 + self.helper(nums, current_index + i)) self.memo[current_index] = self.m return self.m def min_jump(self, nums: List[int]): if not nums: return 0 self.m = float('inf') self.memo = {} return self.helper(nums, 0)

Challenge Given a binary Tree, find the lowest common ancestor of two nodes. Example: LCA(4,9) => 7 LCA() 3 / \ 7 1 / \ \ 4 9 2 Solution 1 - Recursion class Solution: def helper(self, root, nodes): if not root: return None if root in nodes: return root left = self.helper(root.left, nodes) right = self.helper(root.right,nodes) if left and right: return root if left and right is None: return left if right and left is None: return right def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode': return self.helper(root, nodes) Solution 2 - Iterative Another strategy is for each node keep in memory his parent. Then you can go up the ancestry tree and find the lowest they share. ...