Python

Challenge The array nums represent the value inside each house. What is stopping you to rob everything is that you cannot rob two consecutive houses without triggering the alarm. Determine the maxium amout of money you can rob without triggering the alarm. Solution 1 - Recursion class Solution: def helper(self, index, nums, val): if index > len(nums)-1: self.m = max(self.m, val) return self.helper(index+1, nums, val) self.helper(index+2, nums, nums[index] + val) def rob(self, nums: List[int]) -> int: self.m = float("-inf") self.helper(0, nums, 0) return self.m Time Complexity: O(2^n) ...

Challenge Given a String S and and an array representing the cost of each deletion. You goal is to minimize the cost needed to remove all consecutive repetive characters. Example 1: "aba" [2,3,4] => 0 Example 2: "abaa" [2,3,4,1] => 1 Solution 1 - Brute Force - TLE class Solution: def no_consecutive_letters(self, s): t = "" for e in s: if e !="#": t += e for i in range(1,len(t)): if t[i-1] == t[i]: return False return True def helper(self, s, current_cost, cost, index): if self.no_consecutive_letters(s): self.min_cost = min(current_cost, self.min_cost) return 0 if index > self.s_len: return 0 self.helper(s[:index] + "#" +s[index+1:] , current_cost + cost[index], cost,index+1) self.helper(s, current_cost, cost,index+1) return 0 def minCost(self, s: str, cost: List[int]) -> int: self.s_len = len(s)-1 self.min_cost = float("inf") self.helper(s, 0, cost, 0) return self.min_cost Solution 2 - Greedy class Solution: def remove_n_max(self, n, cost): c = sorted(cost) res = [] for i in range(0, n-1): res.append(c[i]) return sum(res) def minCost(self, s: str, cost: List[int]) -> int: total = 0 i = 0 while i < len(s): arr = [] current = 0 in_loop = False tmp = [] while i < len(s)-1 and s[i] == s[i+1]: arr.append(cost[i]) in_loop = True current +=1 tmp.append(s[i]) i += 1 if in_loop is True: arr.append(cost[i]) total += self.remove_n_max(current+1, arr) i += 1 return total

Challenge You are given a board 8 x 8, a position(x,y) as well of a color. You task is to determine if this move is valid. A move is considered valid, if you have can have (vertically, horizontally or in digonal), starting from this position, a structure like so: color given then opposite N colors then color given. For example [“B”,“W”,“W”,“B”] or [“W”,“B”,“W”] is valid in any direction. This [“B”,“B”,“W”] or [“W”,"."] is invalid. ...

Challenge Given a rod of length N. You are also given an array that represents the revenue of each cut size. You want to maximize revenue. E.g : [2,3,7,8], piece of length 1 gets you 2$. Solution Top down with Memoization: class Solution: def helper(self, n, cost): if n < 0: return 0 if n == 0: return cost if n in self.memo: return self.memo[n] res = 0 for i in range(1, len(self.cost)+1): res = max(res, self.helper(n-i, cost + self.cost[i])) self.memo[n] = res return self.memo[n] def rodCutting(self, n, cuts): self.res = 0 self.memo = {} cost = {} for i, e in enumerate(cuts): cost[i+1] = e self.cost = cost return self.helper(n, 0)

Challenge Your task is to print the Nth catalan number. catalan(5) = 42 Solution Bottom up def catalan(n): res = [0 for i in range(n+1)] res[0] = 1 s = 0 for i in range(1, n+1): for j in range(0, i): res[i] += res[j] * res[i-j-1] return res[n] Time Complexity: O(n^2) Top Down def catalan(n): if n == 0 or n ==1: return 1 s = 0 for i in range(n): s += catalan(i) * catalan(n-1-i) return s Time Complexity: O(n!) Application Find the number of unique BST.

Challenge Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. The order of the initial linked list must be preserved. Solution from copy import deepcopy class Solution: def add_to_list(self, head, node,x): node.next = None if head is None and node.val < x: self.left_part = node self.left_tail = node return elif head is None and node.val >= x: self.right_part = node self.right_tail = node return if head == self.left_part: self.left_tail.next = node self.left_tail = node if head == self.right_part: self.right_tail.next = node self.right_tail = node def partition(self, head: ListNode, x: int) -> ListNode: self.left_part = None self.right_part = None tmp = head while tmp: tmp_cpy = deepcopy(tmp) if tmp.val < x: self.add_to_list(self.left_part, tmp_cpy,x) else: self.add_to_list(self.right_part, tmp_cpy,x) tmp = tmp.next tmp = self.left_part if not tmp: return self.right_part self.left_tail.next = self.right_part return self.left_part Time complexity: O(n) Space complexity: O(1) ...

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. ...

Challenge You are painting post on a fence of size N. Only K consecutive post can have the same color. Return the number of way you can paint the fence. E.g: N = 3 K = 2 -> will return 6 Solution 1 - Time Limted Exceeded class Solution: def helper(self,n, k, fence) ->int: if len(fence) >= 3 and fence[-3] == fence[-2] == fence[-1]: return if len(fence) == n: self.count += 1 return for i in range(0, k): self.helper(n, k, fence + str(i)) def numWays(self, n: int, k: int) -> int: self.count = 0 self.helper(n, k, "") return self.count The code above will create a recursion tree like so: ...

Challenge I came across this challenge on leetcode that the goal is to generate a new board after a row, column is selected. Here is an online version of the game. It’s a very BFS like challenge, down below the code. Solution class Solution: def is_valid_coord(self, board, row, col): if row >= 0 and row < len(board) and col >= 0 and col < len(board[0]): return True return False def adjacent_mine(self, board, direction, x, y): adjacent_mine = 0 for nx, ny in direction: new_row = nx + x new_col = ny + y if self.is_valid_coord(board, new_row, new_col) and board[new_row][new_col] == 'M': adjacent_mine += 1 return adjacent_mine def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]: pos_x, pos_y = click if board[pos_x][pos_y] == 'M': board[pos_x][pos_y] = "X" return board queue = [click] # left down right up direction = [[0,-1], [1,-1], [1,0], [1,1], [0,1], [-1,1], [-1,0], [-1,-1]] seen = set() while queue: x, y = queue.pop(0) if board[x][y] == "E" and self.adjacent_mine(board, direction, x, y) == 0: board[x][y] = 'B' seen.add((x, y)) for nx, ny in direction: if self.is_valid_coord(board, nx+x, ny+y) and (nx+x, ny+y) not in seen: queue.append([nx+x, ny+y]) elif board[x][y] == "E" and self.adjacent_mine(board, direction, x, y) >= 0: board[x][y] = str(self.adjacent_mine(board, direction, x, y)) return board Time Complexity: O(m*n) Space Complexity: O(m+n) ...