Posts

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. I O n u p t u p t u : t : n u 2 m s # = r e [ a 2 c , h 4 , t 1 o , 1 i , n 1 d 7 e ] x 1 a n d t h e n f r o m t h e r e l a s t i n d e x . 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() 4 7 3 9 1 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 Given the head of a singly linked list and two integers, reverse the nodes of the list from position left to position right. E.g: reverseBetween(head, 2, 4) 1 -> 2 -> 3 -> 4 -> 5 Returns 1 -> 4 -> 3 -> 2 -> 5 Solution class Solution: def reverse(self, head, steps): tmp = head prev = None tail = head i = 0 while tmp and i < steps: current = tmp n = current.next current.next = prev prev = current tmp = n i+=1 head = current tail.next =n t = head return head def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode: tmp=head j = 1 prev = None if right -left ==0: return head while tmp and j < left: prev = tmp tmp=tmp.next j =j+1 a = self.reverse(tmp, right+1 - left) if not prev: return a prev.next = a return head Time complexity: O(n) Space complexity: 1 ...

Challenge Given a non-negative number represented as a string, return the smaller possible integer after removing K digits. E.g " 1 1 0 4 1 " Will output 41 Solution 1 I really liked my first solution, however performances can’t be worst. It’s a brute force approach doing backtracking, basically I tried to remove 3 digits in every possible position. from copy import deepcopy class Solution: def helper(self, num, k, arr, start): if len(arr) == k: self.res.append(deepcopy(arr)) return for i in range(start, len(num)): arr.append(i) self.helper(num, k, arr, i+1) arr.remove(i) return def remove_from_list(self, num, to_remove): num = list(num) r = [] for i, e in enumerate(num): if i not in to_remove: r.append(e) return r def removeKdigits(self, num: str, k: int) -> str: if k == len(num): return "0" self.res = [] self.helper(tuple(num), k, [], 0) r = int(num) for i in self.res: ret = self.remove_from_list(num, i) ret = int("".join(ret)) r = min(r, ret) return str(r) Solution 2 After failing on a lot of different test cases it looks like this greedy implementation below works. ...

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

Challenge Given a String S return all palindrome partitions. Example 1: I O n u p t u p t u : t : s [ = [ " " a a " b , c " " b " , " c " ] Example 2: I O n u p t u p t u : t : s [ = [ " " a a " b , b " " b b " ] , [ " a " , " b " , " b " ] ] Solution Get all subset of the string. Check if this subset is only composed of palindromes If so add it to the result class Solution: def check_palindrome(self, s): stack = [] for e in list(s): stack.insert(0, e) for e in s: i = stack.pop(0) if i != e: return False return True def get_all_subsets(self, start, s, arr): if arr and not 0 in arr: self._set.add(tuple(arr[:])) for i in range(start, len(s)): arr.append(i) self.get_all_subsets(i+1, s, arr) arr.pop() return def cutter(self, s, cuts): res = [] for cut in cuts: cut = list(cut) cut = [0] + cut + [len(s)] tmp = [] for i, e in enumerate(cut): if i > 0: tmp.append(s[cut[i-1]:cut[i]]) ct = 0 for t in tmp: if self.check_palindrome(t): ct +=1 if ct == len(tmp): res.append(tmp) if self.check_palindrome(s): res.append([s]) return res def partition(self, s: str) -> List[List[str]]: if not s: return if len(s) == 1: return [s] self._set = set() self.get_all_subsets(0, s, []) return self.cutter(s, self._set) Time complexity Space Complexity O(2^n) O(n)

Challenge Given the head of a linked list, find all the values that appear more than once in the list and delete the nodes that have any of those values. Return the linked list after the deletions. e.g 1 2 > 3 > 2 r e t u r n s 1 3 Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def print_list(self, head): tmp = head while tmp: print(tmp.val, end=", ") tmp = tmp.next def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode: tmp = head oc = defaultdict(int) while tmp: oc[tmp.val] += 1 tmp = tmp.next tmp = head prev = head while tmp: if oc[tmp.val] > 1 and tmp == head: head = tmp.next prev = head elif oc[tmp.val] > 1: prev.next = tmp.next else: prev = tmp tmp = tmp.next self.print_list(head) return head Solution 2 - Using dummy node def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode: tmp = head oc = defaultdict(int) while tmp: oc[tmp.val] += 1 tmp = tmp.next fake = ListNode() fake.next = head prev = fake tmp = head while tmp: if oc[tmp.val] > 1: prev.next = tmp.next else: prev = tmp tmp = tmp.next return fake.next

Challenge Implement a queue (FIFO) using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty). Solution class MyQueue: def __init__(self): self.stack1 = [] self.stack2 = [] self.mypeek = None def push(self, x: int) -> None: if not self.stack1: self.mypeek = x self.stack1.insert(0, x) return None def pop(self) -> int: while len(self.stack1): val = self.stack1.pop(0) self.stack2.insert(0, val) if self.stack2: ret = self.stack2.pop(0) while len(self.stack2): val = self.stack2.pop(0) self.stack1.insert(0, val) return ret def peek(self) -> int: if self.stack1: self.mypeek = self.stack1[len(self.stack1)-1] return self.mypeek if self.peek else None def empty(self) -> bool: if len(self.stack1) == 0: return True return False