Meta Flashcards

Question

42. Trapping Rain Water Hard Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining. Example 1: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Answer 1

1. Two pointers 2. Fast forward left and right until they are 0 3. If left>right: return 0 4. lmax=heights[0], rmax=heights[-1] 5. while left<=right, if current left is greater than right, then 1. set lmax 2. trapped+= lmax-hleft 3. left+=1 6. Do reverse for right def trap(self, heights: List[int]) -> int: if len(heights)==1: return 0 left = 0 while heights[left] == 0: left += 1 right = len(heights) - 1 while heights[right] == 0: right -= 1 if left > right: return 0 lmax = heights[0] rmax = heights[-1] trapped = 0 while left <= right: hleft = heights[left] hright = heights[right] if hleft < hright: lmax = max(hleft, lmax) trapped += lmax - hleft left += 1 else: rmax = max(rmax, hright) trapped += rmax - hright right -= 1 return trapped T: O(n) S: O(1)

Answer 2

1. Regular multiplication. Initialize result to [0]* (N1+N2) 2. Outer loop is reversed(num1) and inner loop is reversed(num2) 3. Initialize temp=pos (which was originally len(result)-1 4. During each iteration, result[temp]+= n1*n2 result[temp-1]+= result[temp]//10 result[temp]%=10 temp-=1 (for inner loop) 5. pos-=1 for outer loop 5. Finally, we need to skip off all the leading zeroes and return the string class Solution: def multiply(self, num1: str, num2: str) -> str: N1=len(num1) N2=len(num2) result=[0]*(N1+N2) pos=len(result)-1 for n1 in reversed(num1): temp=pos for n2 in reversed(num2): result[temp]+=int(n1)*int(n2) result[temp-1]+=result[temp]//10 result[temp]%=10 temp-=1 pos-=1 pt=0 while pt

Answer 3

1. Use a mask def permuteUnique(self, nums: List[int]) -> List[List[int]]: nums.sort() mask=0 result=[] self.helper(nums, [], result, mask) return result def helper(self, nums, curr, result, mask): if mask ==(1<0 and nums[i]==nums[i-1] and not mask&(1<<(i-1)): continue self.helper(nums, curr+[nums[i]], result, (mask | (1<

Answer 4

1. Call helper with curr, and result 2. Iterate through i, len(nums) and invoke helper. 3. Add nums[i] to curr but pass nums[:i]+nums[i+1:] to helper self.helper(nums[:i]+nums[i+1:], curr=[nums[i]], result) T: N! (n steps for each permutation) S: O(N) not counting the result

Answer 5

1. Flip and reverse 2. While flipping range(R) but C=range(r) def rotate(self, matrix: List[List[int]]) -> None: R=len(matrix) C=len(matrix[0]) for r in range(R): for c in range(r): matrix[r][c], matrix[c][r]=matrix[c][r], matrix[r][c] for r in range(R): matrix[r].reverse() T: O(n*m) S: O(1)

Answer 6

def groupAnagrams(self, strs: List[str]) -> List[List[str]]: mapp = defaultdict(list) for st in strs: mapp[tuple(sorted(st))].append(st) return [v for k,v in mapp.items()] T: O(N*KlogK) S: O(NK) K = maximum length of the string in strs

Answer 7

1. If negative, make it positive and x=1/x 2. Loop until x and divide n//2 and x*x. But before that, if odd, append to result (result=result*x), n-=1 def myPow(self, x: float, n: int) -> float: result=1 if n<0: n=-n x=1/x while n: if n%2!=0: result=result*x n-=1 x*=x n//=2 return result T: O(logn) S: O(1)

Answer 8

1. Backtracking and post processing is slightly tricky. 2. p=len(curr) and p+q in anti_diag and p-q in diag and q not in curr 3. remaining dot is n-p-1 def solveNQueens(self, n: int) -> List[List[str]]: res=[] self.solve_n_queens(n, [], [], [], res) result=[] for r in res: curr=[] for pos in r: st=('.'*pos) + 'Q' + '.'*(n-pos-1) curr.append(st) result.append(curr) return result def solve_n_queens(self, n, curr, diag, anti_diag, result): p=len(curr) if p==n: result.append(curr.copy()) return for q in range(n): if q not in curr and (p+q) not in anti_diag and (p-q) not in diag: self.solve_n_queens(n, curr+[q], diag+[p-q], anti_diag +[p+q], result) T: O(n!) S: O(n^2) - board is of size N*N

Answer 9

1. if i>max_reach (initialized to 0), return False 2. max_reach=max(max_reach, i+num) def canJump(self, nums: List[int]) -> bool: max_reach=0 for i, num in enumerate(nums): if i>max_reach: return False max_reach=max(max_reach, i+num) return True T: O(n) S: O(1)

Answer 10

1. set start interval to be mstart and mend 2. Iterate through intervals[1:] 3. If mstartmend, then 1. add old mstart and mend to result 2. mstart,mend=cstart,cend 4. Finally before exiting, add mstart, mend to result to capture dangling one def merge(self, intervals: List[List[int]]) -> List[List[int]]: if not intervals: return None intervals.sort(key=lambda x: x[0]) mstart,mend=intervals[0] result=[] for cstart, cend in intervals[1:]: if cstart<=mend and mstart<=cend: mstart=min(cstart, mstart) mend=max(cend, mend) elif cstart>mend: result.append([mstart, mend]) mstart, mend=cstart, cend result.append([mstart, mend]) return result T:O(nlogn) S:O(n) - for sorting

Answer 11

1. Three conditions. 2. if cendnend: #the new interval has passed result.append(nstart,nend) result.extend(intervals[i:]) return result 4. else: #overlap nstart=min(nstart, cstart) nend =max(nend,cend) 5. finally, add residual - result.append(nstart,nend) def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]: nstart, nend=newInterval result=[] for i,interval in enumerate(intervals): cstart, cend=interval if cendnend: result.append([nstart, nend]) result.extend(intervals[i:]) return result else: nstart=min(nstart, cstart) nend=max(nend, cend) result.append([nstart, nend]) return result T:O(n) S:O(1)

Answer 12

1. DP - recursive and tabulation. 2. For tabulation, populate a m*n dp with 1 and start R,C loop with 1,R and 1,C 3. For recursion, the way to think about is a tree. 4. base case is (r,c)=(R-1, C-1): return 1 5. if r=R or c==C: return 0 6. counts=self.helper(R, C, r+1, c) + self.helper(R, C, r, c+1) def uniquePaths(self, m: int, n: int) -> int: return self.helper(m, n, 0,0, {}) def helper(self, R, C, r, c, memo): if (r,c) in memo: return memo[(r,c)] if (r,c) == (R-1, C-1): return 1 if r==R or c==C: return 0 counts=self.helper(R, C, r+1, c, memo) counts+=self.helper(R, C, r, c+1, memo) memo[(r,c)]=counts return counts def uniquePaths(self, m: int, n: int) -> int: R = m C = n dp = [[1] * C for _ in range(R)] for r in range(1, R): for c in range(1, C): dp[r][c] = (dp[r - 1][c] + dp[r][c - 1]) return dp[-1][-1] T: O(n*m) S: O(n*m)

Answer 13

1. Key principles: 1. Dot cannot come after e 2. Sign has to be [0] or just after e [i-1]. If i>0 and s[i-1].lower()!=e: return False 3. If e seen, then number must be seen after that. So, return number_seen 2. Four variables: is_e_seen, is_number_seen, is_dot_seen and is_sign_seen 3. If digit faced, number_seen=True 4. If dot seen and (dot already seen or e_seen), return False. Else, set the var 5. If e_seen and (e already seen or not number_seen) (first e), return False. Else set var and number_seen=False 6. else, return False 7. return number_seen def isNumber(self, s: str) -> bool: s=s.strip() is_dot_seen=False is_e_seen=False is_number_seen=False is_sign_seen=False for i,c in enumerate(s): if c in '1234567890': is_number_seen=True elif c=='.': if is_dot_seen or is_e_seen: return False is_dot_seen=True elif c in '+-': if i>0 and s[i-1].lower()!='e': return False is_sign_seen=True elif c in 'eE': if is_e_seen or not is_number_seen: return False is_e_seen=True is_number_seen=False else: return False return is_number_seen T: O(N) S: O(1)

Answer 14

1. Very hard problem def fullJustify(self, words, maxWidth): N = len(words) L = maxWidth i = 0 result = [] def get_kwords(i): curr_len = len(words[i]) k = 1 while i + k < N: next_len = len(words[i + k]) + 1 if curr_len + next_len <= L: k += 1 curr_len += next_len else: break return k def insert_space(i, k): line = ' '.join(words[i:i + k]) if k == 1 or i + k == N: spaces = L - len(line) line += ' ' * spaces return line else: spaces = L - len(line) + (k - 1) space = spaces // (k - 1) left_words = spaces % (k - 1) if left_words > 0: line = (" " * (space + 1)).join(words[i:i + left_words]) line += (" " * (space + 1)) line += (" " * space).join(words[i + left_words: i + k]) else: line = (" " * space).join(words[i:i + k]) return line i = 0 while i < N: word_count = get_kwords(i) line = insert_space(i, word_count) result.append(line) i += word_count return result T: O(n) - length of words*average length of the word S: O(n)

Answer 15

1. Stack 2. Split on '/' and iterate 3. If c in ['', ' ', '.'] - single space, no space or dot, then continue 4. If c=='..' and stack, pop() 5. Else append to stack 6. return '/'+'/'.join(stack) def simplifyPath(self, path: str) -> str: path=path.split('/') stack=[] for p in path: if p in ['.', ' ', '']: continue elif p=='..': if stack: stack.pop() else: stack.append(p) return '/'+'/'.join(stack) T: O(n) S: O(n)

Answer 16

1. dp = [0]* C+1*R+1 2. dp[r][0]=r, dp[0][c]=c def minDistance(self, word1: str, word2: str) -> int: R=len(word1) C=len(word2) dp=[[0] * (C+1) for _ in range(R+1)] for r in range(R+1): dp[r][0]=r for c in range(C+1): dp[0][c]=c for r in range(1, R+1): for c in range(1, C+1): if word1[r-1]==word2[c-1]: dp[r][c]=dp[r-1][c-1] else: dp[r][c]=1+min(dp[r-1][c-1], dp[r][c-1], dp[r-1][c]) return dp[-1][-1] T: O(M*N) S: O(M*N)

Answer 17

1. left, right, one_start 2. If 1, just increment left 3. if 2, swap with right and decrement right 4. if 0, swap os with left and increment os def sortColors(self, nums: List[int]) -> None: left=0 right=len(nums)-1 ostart=0 while left<=right: if nums[left]==2: nums[left],nums[right]=nums[right],nums[left] right-=1 elif nums[left]==0: nums[left], nums[ostart]= nums[ostart], nums[left] ostart+=1 left+=1 elif nums[left]==1: left+=1 T: O(n) S: O(1)

Answer 18

1. Sliding window. class Solution: def minWindow(self, s: str, t: str) -> str: if len(t)>len(s): return "" counter=Counter(t) ws=0 matches=0 min_window=float('inf') min_string="" for we, swe in enumerate(s): if swe in counter: counter[swe]-=1 if counter[swe]==0: matches+=1 while matches ==len(counter): sws=s[ws] if we-ws+10: matches-=1 ws+=1 return min_string T: O(S+T) S: O(S+T)

Answer 19

1. Backtracking - Skip, Pick 2. helper has index and current 3. if index==len(nums), then add to result and return 4. skip: self.bt(nums, result, index+1, curr) 5. pick: self.bt(nums, result, index+1, curr+[nums[index]]) def subsets(self, nums: List[int]) -> List[List[int]]: result=[] self.bt(nums, 0, [], result) return result def bt(self, nums, index, curr, result): if index==len(nums): result.append(curr.copy()) return self.bt(nums, index+1, curr, result) self.bt(nums, index+1, curr+[nums[index]], result) T: O(N* 2^n) - Copying is another N S:O(n) - Curr space

Answer 20

1. Monotonic increasing stack 2. append 0 to heights so that it pops off based on the last element 3. initialize stack to -1 because it makes it easier for calculating the width (W=i-stack[-1]-1) def largestRectangleArea(self, heights: List[int]) -> int: heights.append(0) stack = [-1] max_area = 0 for i, height in enumerate(heights): while stack and heights[stack[-1]] > height: ii = stack.pop() H = heights[ii] W = i - stack[-1]-1 max_area = max(max_area, H * W) stack.append(i) return max_area T: O(n) S: O(n)

Answer 21

1. Helper with -sys.maxsize and sys.maxsize as mini and maxi 2. Validate left and right class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: return self.is_valid(root, -sys.maxsize, sys.maxsize) def is_valid(self, node, mini, maxi): if not node: return True if not mini bool: stack=[] node=root prev=float('-inf') while node or stack: if node: stack.append(node) node=node.left elif stack: node=stack.pop() if prev>=node.val: return False prev=node.val node=node.right return True T: O(n) S: O(n)

Answer 22

1. Generic level order traversal 2. for _ in range(len(queue) def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: return None node=root queue=deque([root]) result=[] while queue: level=[] for _ in range(len(queue)): node=queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result T: O(n) S: O(n)

Answer 23

1. Level order traversal. But for level use deque (append and appendleft) def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: return [] node=root queue=deque([root]) left_to_right=True result=[] while queue: level=deque([]) for _ in range(len(queue)): node=queue.popleft() if left_to_right: level.append(node.val) else: level.appendleft(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) left_to_right=not left_to_right result.append(level) return result T: O(n) S: O(n)

Answer 24

1. Root to leaf with a target_sum - DFS (track target_sum, curr) 2. In the helper, if node.val==target_sum and not node.left and not node.right: result.add(curr.copy()) 3. if not node: return 4. if node.left: self.dfs(node.left, target_sum-node.val, curr+[node.val], result) 5. same with node.right class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]: if not root: return None result=[] self.path_sum(root, targetSum, [], result) return result def path_sum(self, node, target, curr, result): if not node.left and not node.right and target==node.val: curr+=[node.val] result.append(curr.copy()) return if node.left: self.path_sum(node.left, target-node.val, curr+[node.val], result) if node.right: self.path_sum(node.right, target-node.val, curr+[node.val], result) BFS has a lot of space overhead, since we need to maintain all the paths in the queue T: O(n^2) - Worst case, if it is a complete binary tree, we need to traverse through N/2 leaves. S: O(n)

Answer 25

1. Level order traversal 2. prev = None 3. If prev, prev.next=node 4. prev=node def connect(self, root: 'Optional[Node]') -> 'Optional[Node]': if not root: return root queue = deque([root]) while queue: prev = None for _ in range(len(queue)): node = queue.popleft() if not prev: prev = node else: prev.next = node prev = node if node.left: queue.append(node.left) if node.right: queue.append(node.right) return root T: O(n) S: O(n)

Answer 26

1. Just keep comparing current price to previous price and accumulate them into profit def maxProfit(self, prices: List[int]) -> int: profit=0 for i in range(1, len(prices)): if prices[i-1]

Answer 27

1. Hold all the nums in a set 2. Entry when num-1 is not in set (least number) 3. count=1, while count+num is not in set: count+=1 4. set max_count def longestConsecutive(self, nums: List[int]) -> int: hset=set(nums) max_count=0 for num in nums: if num-1 not in hset: count=1 while num+count in hset: count+=1 max_count=max(count, max_count) return max_count T:O(n) S:O(n)

Answer 28

1. BFS - queue.append((root, str(root.val)) 2. Keep adding to the str. If not node.left and not node.right, total+=int(str_val) def sumNumbers(self, root: Optional[TreeNode]) -> int: if not root: return 0 queue=deque([(root, str(root.val))]) result=0 while queue: node, sval=queue.popleft() if not node.left and not node.right: result+=int(sval) continue if node.left: queue.append((node.left, sval+str(node.left.val))) if node.right: queue.append((node.right, sval+str(node.right.val))) return result T:O(n) S:O(n)

Answer 29

1. Simple BT recursion (helper has curr and result) 2. At each level iterate from 1, len(s)+1 and check if s[:i] is palindrome. 3. If yes, then call the helper recursively with s[i:], curr=[s[:i]] S: O(N*2^N) - 2N - there could be 2N possible substrings in the worst case T: N*2^N N=3, aaa, the first level of the tree is [a]aa, [aa][a], [aaa] Essentially, there are 8 nodes in the tree, which is 2^3

Answer 30

1. BFS 2. Keep a copy dictionary, copy={root:Node(root.val)} 3. Upon popping, iterate through neis, if nei not in copy: copy[nei]=Node(nei.val) queue.append(nei) copy[node].neighbours.append(copy[nei]) 4. return copy[root] from typing import Optional class Solution: def cloneGraph(self, root: Optional['Node']) -> Optional['Node']: if not root: return root queue=deque([root]) copy={root: Node(root.val)} while queue: node=queue.popleft() for nei in node.neighbors: if nei not in copy: copy[nei]=Node(nei.val) queue.append(nei) copy[node].neighbors.append(copy[nei]) return copy[root] T: O(V+E) S: O(V)

Answer 31

1. Have a copy map and do two traversals. 2. First time copy[node]=Node(node.val) 3. Next time, copy[node].next=copy.get(node.next) & copy[node].random=copy.get(node.random) 4. return copy[head] def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]': if not head: return None copy={head:Node(head.val)} node=head while node: if node not in copy: copy[node]=Node(node.val) node=node.next node=head while node: copy[node].next=copy.get(node.next) copy[node].random=copy.get(node.random) node=node.next return copy[head] T: O(N) S: O(N)

Answer 32

1. DP. Recursion 2. Helper has curr and result 3. if not s: result.append(curr.copy()) 4. for i in range(len(s)), call helper by skipping i (s[:i]+s[i+1:]) def wordBreak(self, s: str, wordDict: List[str]) -> bool: words=set(wordDict) N=len(s) dp=[False]*(N+1) dp[0]=True for i in range(N+1): for j in range(i): word=s[j:i] if word in words and dp[j]==True: dp[i]=True return dp[-1] T: O(n*m*k), n being the size of the string, m is the length of the worddict and k is the average length of the word in the worddict S: O(n)

Answer 33

1. DP. Recursion 2. Helper has curr and result 3. if not s: result.append(curr.copy()) 4. for i in range(len(s)+1). Remember to loop until len(s)+1 def wordBreak(self, s: str, wordDict: List[str]) -> List[str]: result=[] self.helper(s, 0, set(wordDict), [], result) return result def helper(self, s, index, words, curr, result): if not s: result.append(' '.join(curr)) return for i in range(len(s)+1): if s[:i] in words: self.helper(s[i:], i, words, curr+[s[:i]], result) T: O(2^n) - Worst case, every letter is a word. String concat O(n), since for each recursive call n/k (k=average length of a valid word) = O(2^n*n) S: O(n)

Answer 34

1. Find mid 2. Reverse the second half 3. Merge both lists. def reorderList(self, head: Optional[ListNode]) -> None: fast=head slow=head while fast.next and fast.next.next: slow=slow.next fast=fast.next.next second=slow.next slow.next=None #reverse mid prev=None while second: nxt=second.next second.next=prev prev=second second=nxt #merge head1=head head2=prev while head2: nxt=head1.next head1.next=head2 head1=head2 head2=nxt T: O(n) S: (1)

Answer 35

1. init - head.next=tail, tail.prev=head, self.mapp={} 2. get - if not key in self.mapp, return -1 else: ret_node=self.mapp[key], self.remove_node(ret_node) del self.mapp[key] self.move_to_first(ret_node) self.mapp[key]=ret_node 3. put - nnode=Node(key,val) if key in self.mapp: per_node=self.mapp[key] self.remove_node(per_node) del self.mapp[key] self.move_to_first(nnode) self.mapp[key]=nnode if len(self.mapp)>self.capacity: last_node=self.tail.prev self.remove_node(last_node) del self.mapp[last_node.key] 4. move_to_first nxt=self.head.next self.head.next=node node.prev=self.head node.next=nxt next.prev=node 5. remove_node prev=node.prev node.prev.next=node.next node.next.prev=prev class Node: def __init__(self, key, val, prev=None, next=None): self.key=key self.val=val self.prev=prev self.next=next class LRUCache: def __init__(self, capacity: int): self.capacity=capacity self.head=Node(0,0) self.tail=Node(0,0) self.head.next=self.tail self.tail.prev=self.head self.mapp={} def get(self, key: int) -> int: if key not in self.mapp: return -1 node=self.mapp[key] self.remove_node(node) self.add_to_front(node) return node.val def put(self, key: int, value: int) -> None: if key in self.mapp: node=self.mapp[key] node.val=value self.remove_node(node) self.add_to_front(node) else: node=Node(key, value) self.add_to_front(node) self.mapp[key]=node if len(self.mapp)>self.capacity: last_node=self.tail.prev self.remove_node(last_node) del self.mapp[last_node.key] def remove_node(self, node): prev=node.prev node.prev.next=node.next node.next.prev=prev def add_to_front(self, node): pnext= self.head.next self.head.next=node node.prev=self.head pnext.prev=node node.next=pnext T: O(1) S: O(capacity)

Answer 36

1. Unlike assumption, we have to maintain two stacks - one for values and the other one for min so far. 2. While adding a value, check if the current value is lesser than the top most value on the min_stack 3. Add the minimum of the top value, incoming value to the top of the min_stack. class MinStack: def __init__(self): self.stack=[] self.min_stack=[] def push(self, val: int) -> None: self.stack.append(val) if not self.min_stack: self.min_stack.append(val) else: mini=min(val, self.min_stack[-1]) self.min_stack.append(mini) def pop(self) -> None: self.stack.pop() self.min_stack.pop() def top(self) -> int: return self.stack[-1] def getMin(self) -> int: return self.min_stack[-1] T: O(1) S: O(n)

Answer 37

1. Binary search. 2. if (mid==0 or nums[mid]>nums[mid-1]) and (mid==N-1 or nums[mid]>nums[mid+1], return mid 3. elif nums[low]<=nums[mid]: low+=1 (too far - we need mid-1, so moving left ahead) 4. else, high-=1 Remember that unlike binary search, we aren't doing low=mid+1, It's just low+=1 def findPeakElement(self, nums: List[int]) -> int: N=len(nums) left=0 right=N-1 while left<=right: mid=(left+right)//2 if (mid==0 or nums[mid]>nums[mid-1]) and (mid==N-1 or nums[mid]>nums[mid+1]): return mid elif nums[left]<=nums[mid]: left+=1 else: right-=1 Alternative: def findPeakElement(self, nums: List[int]) -> int: N=len(nums) left=0 right=N-1 if left==right: return left while left

Answer 38

Do an inorder traversal 1. init - set node=root and stack=[] 2. next - modified inorder. (ensure that stack is always populated) while node: stack.append(node) node=node.left nxt=stack.pop() return_val=nxt.val node=node.right return return_val 3. has_next: return stack or node class BSTIterator: def __init__(self, root: Optional[TreeNode]): self.stack=[] self.node=root def next(self) -> int: while self.node: self.stack.append(self.node) self.node=self.node.left nxt=self.stack.pop() ret_val=nxt.val self.node=nxt.right return ret_val def hasNext(self) -> bool: return self.stack or self.node T: O(n) S: O(n)

Answer 39

select distinct l1.num as ConsecutiveNums from Logs l1 join Logs l2 on l2.id=l1.id+1 join Logs l3 on l3.id=l2.id+1 where l1.num=l2.num and l2.num=l3.num

Answer 40

1. DP - initialize to N+1 2. dp[1]=nums[0 3. Iterate from 1 to N and dp[i+1]=max(dp[i-1]+nums[i], dp[i]) def rob(self, nums: List[int]) -> int: dp=[0]*(len(nums)+1) dp[1]=nums[0] for i in range(1, len(nums)): dp[i+1]=max(dp[i-1]+nums[i], dp[i]) return dp[-1] T: O(n) S: O(n)

Answer 41

1. Level order traversal 2. if i==level-1 (N-1), add to result def rightSideView(self, root: Optional[TreeNode]) -> List[int]: if not root: return None queue=deque([root]) result=[] while queue: level=len(queue) for i in range(level): node=queue.popleft() if i==level-1: result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result T: O(n) S: O(d) - tree diameter

Answer 42

DFS class Solution: def numIslands(self, grid: List[List[str]]) -> int: R=len(grid) C=len(grid[0]) count=0 for r in range(R): for c in range(C): if grid[r][c]=='1': self.dfs(grid, r, c, R, C) count+=1 return count def dfs(self, grid, r, c, R, C): grid[r][c]='0' neis = [(r+1, c), (r-1, c), (r, c+1), (r, c-1)] for nr, nc in neis: if -1

Answer 43

1. BFS and check if cycle exists WHITE, GRAY, BLACK = 0,1,2 class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph=defaultdict(list) for u,v in prerequisites: graph[u].append(v) colors=defaultdict(int) for u in range(numCourses): if colors[u]==WHITE and self.has_cycle(u, graph, colors): return False return True def has_cycle(self, node, graph, colors): colors[node] = GRAY for nei in graph[node]: if colors[nei]==GRAY: return True elif colors[nei]==WHITE: if self.has_cycle(nei, graph, colors): return True else: continue colors[node]=BLACK return False T: O(V+E) S: O(V+E)

Answer 44

1. Topsort while checking is there's no cycle WHITE,GRAY,BLACK=0,1,2 class Solution: def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]: graph=defaultdict(list) for u,v in prerequisites: graph[u].append(v) colors=defaultdict(int) tops=[] for node in range(numCourses): if colors[node]==WHITE: if self.has_cycle(node, colors, graph, tops): return [] return tops if len(tops)==numCourses else [] def has_cycle(self, node, colors, graph, tops): colors[node]=GRAY for nei in graph[node]: if colors[nei]==GRAY: return True elif colors[nei]==WHITE: if self.has_cycle(nei, colors, graph, tops): return True else: continue tops.append(node) colors[node]=BLACK return False T: O(V+E) S: O(V+E)

Answer 45

1. Construct a Trie and add all words 2. Do a dfs on Trie. class TrieNode: def __init__(self, val=None): self.val = val self.children = {} self.end_node = False class Trie: def __init__(self): self.root = TrieNode() def add_word(self, word): node = self.root for c in word: if c not in node.children: nnode = TrieNode(c) node.children[c] = nnode node = node.children[c] node.end_node = True # # def search(self, word): # node = self.root # for c in word: # if c not in node.children: # return False # node = node.children[c] # return node.end_node class WordSearch: def findWords(self, board: List[List[str]], words: List[str]) -> List[str]: R = len(board) C = len(board[0]) trie = Trie() for word in words: trie.add_word(word) # print(trie) result = [] self.num_words = len(words) for r in range(R): for c in range(C): if board[r][c] in trie.root.children: self.dfs(board, r, c, R, C, trie.root, result, "") return result def dfs(self, board, r, c, R, C, troot, result, curr): if self.num_words == 0: return if troot.end_node: result.append(curr) troot.end_node = False self.num_words -= 1 neis = [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)] for nr, nc in neis: if -1 < nr < R and -1 < nc < C and board[nr][nc] in troot.children: self.dfs(board, nr, nc, R, C, troot.children[board[nr][nc]], result, curr + board[nr][nc]) T: O(n*4^L) - L is the length of the word in the dictionary S: O(k*L) - k number of words in the dictionary and L average length of the words

Answer 46

1. Do houserobber twice (once with nums[1:] and second with nums[:-1] def rob(self, nums: List[int]) -> int: if not nums: return 0 if len(nums)==1: return nums[0] skip_first=self.helper(nums[1:]) skip_last=self.helper(nums[:-1]) return max(skip_first, skip_last) def helper(self, nums): N=len(nums) dp=[0]*(N+1) dp[1]=nums[0] for i in range(1, N): dp[i+1]=max(dp[i-1]+nums[i], dp[i]) return dp[-1] T: O(n) S: O(n)

Answer 47

1. For finding largest, create min_heap 2. Keep pushing to heap. If len(heap)>k, pop 3. return pq[0] T: O(NlogK) S: O(k) (Also consider quickselect) def findKthLargest(self, nums: List[int], k: int) -> int: if not nums: return -1 pivot=random.choice(nums) left=[num for num in nums if num>pivot] mid=[num for num in nums if num==pivot] right=[num for num in nums if numL+M: return self.findKthLargest(right, k-L-M) return mid[0] T: O(n) - average case - balanced partitioning. O(n^2) worst case - when the pivot is always chosen to be the smallest or largest in the array. S: O(n) - storage of partitioned lists

Answer 48

1. Regular basic calculator 2. Create an opset 3. For digit. num*10+int(c) 4. For open parens, just append op to stack and reset op and num (this is for starting a new context) 5. For close parens or c in opset: self.update() set op=c num=0 if c==')': temp_num and while loop until stack[-1] is in opset self.update(temp_num, stack.pop()) - the previous op 6. for c in s+'+' def calculate(self, s: str) -> int: op='+' num=0 opset={'+','-','*','/'} stack=[] for c in s+'+': if c.isdigit(): num=num*10 + int(c) elif c==')' or c in opset: self.update(num, op, stack) op=c num=0 if c==')': tmp_num=0 while stack[-1] not in opset: tmp_num+=stack.pop() self.update(tmp_num, stack.pop(), stack) elif c=='(': stack.append(op) op='+' num=0 return sum(stack) def update(self, num, op, stack): if op=='+': stack.append(num) elif op=='-': stack.append(-num) elif op=='*': prev=stack.pop() stack.append(num*prev) elif op=='/': prev=stack.pop() stack.append(int(prev/num)) T: O(n) S: O(n)

Answer 49

1. op="+', num='0', stack=[] 2. Iterate through s and keep accumulating num if digit. 3. If an operator is faced, call self.update(num, op, stack). Reset num and op to defaults 4. return sum(stack) def calculate(self, s: str) -> int: op='+' num=0 stack=[] for c in s+'+': if c.isdigit(): num=num*10 +int(c) elif c in '+-/*': self.update(num, op, stack) op=c num=0 return sum(stack) def update(self, num, op, stack): if op=='+': stack.append(num) elif op=='-': stack.append(-num) elif op=='*': prev=stack.pop() stack.append(prev*num) elif op=='/': prev=stack.pop() stack.append(int(prev/num)) T: O(n) S:O(n)

Answer 50

1. If p_valnode_val and q_val>node_val: node=node.right 3. Else, we've found the split point, return node T: O(N) S: O(N)

Answer 51

1. Similar to meeting point of LinkedList 2. Find depth of both nodes using simple iteration (while node, node=node.parent) 3. Compare the longest and shortest. Move longest to the level of shortest (for _ in range(ldepth-sdepth), lnode=lnode.parent) 4. Move both lnode and snode up, lnode=lnode.parent, snode=snode.parent 5. If they are equal return T: O(N) S: O(1)

Answer 52

def deleteNode(self, node): node.val=node.next.val node.next=node.next.next T: O(1) S: O(1)

Answer 53

1. left and right =[1]*N 2. left =(1,N) , right = reversed (range(N-1) 3. left[i]=left[i-1]*nums[i-1] 4. right[i]=right[i+1]*nums[i+1] def productExceptSelf(self, nums: List[int]) -> List[int]: result = [] N = len(nums) left = [1] * (N) right = [1] * (N) for i in range(1, N): left[i] = left[i - 1] * nums[i - 1] for i in reversed(range(N - 1)): right[i] = right[i + 1] * nums[i + 1] for l, r in zip(left, right): result.append(l * r) return result T: O(n) S: O(n)

Answer 54

1. Recursion and build from inside. 2. if num==0: return [''] 3. If num==1: return ['0','1','8'] 4. temp=build_strobogrammatic(num-2) 5. for l in temp: result.append('1'+l+'1') (do for 69, 88, and 96) 6. if n!=num, result prefix and suffix 0 def findStrobogrammatic(self, n: int) -> List[str]: if not n: return [] return self.find_stobogrammatic(n, n) def find_stobogrammatic(self, n, num): if num == 0: return [''] elif num == 1: return ['0', '1', '8'] result = [] temp = self.find_stobogrammatic(n, num - 2) for l in temp: if num != n: result.append('0' + l + '0') result.append('1' + l + '1') result.append('6' + l + '9') result.append('8' + l + '8') result.append('9' + l + '6') return result T: O(5^n) S: O(5^n) - O(n/2) for call stack

Answer 55

1. Maintain result=defaultdict(list) 2. Iterate through each string. Calculate key for each string and push it to map 3. Key calculation: Iterate through each s and compare against it's first character (ord(c)-ord(s[0])) %26. Return a tuple of the ords as key. Note the s[0] instead of the usual ord('a') If it is not tuple and keep it as just a num string, then there's no difference between 112 - 11,2 and 1,12 def groupStrings(self, strings: List[str]) -> List[List[str]]: mapp=defaultdict(list) for s in strings: key=self.get_key(s) mapp[key].append(s) return [v for k,v in mapp.items()] def get_key(self, s): key=[] for c in s: k=(ord(c)-ord(s[0]))%26 key.append(k) return tuple(key) T: O(n*k) - we iterate over all the characters of all the strings. S: O(n*k) - we store the string and their hashvalue in the map

Answer 56

1. Sort the meeting rooms by start time 2. Add only the end to the pq 3. if the next meeting has start time which is >= than the end time of the top of the pq, then pop from pq 4 return size of pq def minMeetingRooms(self, intervals: List[List[int]]) -> int: min_conf=-sys.maxsize intervals.sort(key=lambda i: i[0]) pq=[] for ms, me in intervals: if pq and ms>=pq[0]: heapq.heappop(pq) heapq.heappush(pq, me) return len(pq) T: O(nlogn) S: O(n)

Answer 57

1. Undirected graph. Check if there are cycles in the loop. 2. Also check if len(colors)==len(graph) - disconnected graph. Do DFS only from 0. 3. Check if gray and nei!=parent: then return False. Else, gray is fine because this is an undirected graph WHITE,GRAY,BLACK=0,1,2 class Solution: def validTree(self, n: int, edges: List[List[int]]) -> bool: if not edges and n == 1: return True if not edges and n > 1: return False graph = defaultdict(list) for u, v in edges: graph[u].append(v) graph[v].append(u) if len(graph) != n: return False colors = defaultdict(int) if self.has_cycle(0, graph, colors, -1): return False if len(colors) != len(graph): return False return True def has_cycle(self, node, graph, colors, parent): colors[node] = GRAY for nei in graph[node]: if colors[nei] == GRAY and nei != parent: return True elif colors[nei] == WHITE: if self.has_cycle(nei, graph, colors, node): return True colors[node] = BLACK return False T: O(V+E) S: O(V+E)

Answer 58

1. Calculate mid and more than one mid, return [] 2. Divide into half and 'join' them to avoid empty strings 3. call helper - with half, curr, N, mid, result (N=len(half)) 4. if len(curr)=N, then append to result 5. for i in range(len(half)), skip for duplicates and call self. def generatePalindromes(self, s: str) -> List[str]: counter=Counter(s) mid=[k for k,v in counter.items() if v%2==1] if len(mid)>1: return [] mid=mid[0] if mid else '' half = ''.join([k*(v//2) for k,v in counter.items()]) result=[] self.generate_palins(half, '', mid, len(half), result) return result def generate_palins(self, half, curr, mid, N, result): if len(curr)==N: result.append(curr+mid+curr[::-1]) return for i in range(len(half)): if i>0 and half[i]==half[i-1]: continue self.generate_palins(half[:i]+half[i+1:], curr+half[i], mid, N, result) T: O(N/2!) S: O(N) - depth of the recursion tree can go upto n/2 in the worst case

Answer 59

1. Graph cycle finding 2. Iterate through zip(words, words[1:]) and then zip(word1, word2) 3. short circuit - if len(word1)>len(word2) and word1[:len(word2)]==word2: return False 4. if c1!=c2, then add to graph and break 5. Iterate through all the letters {for node in graph for n in node} 6. find cycle (if colors[n]==WHITE) 7. Return reverse of result - topsort WHITE,GRAY,BLACK=0,1,2 class Solution: def alienOrder(self, words: List[str]) -> str: graph=defaultdict(list) for word1, word2 in zip(words, words[1:]): if word1!=word2 and word1[:len(word2)]==word2: return "" for c1, c2 in zip(word1, word2): if c1!=c2: graph[c1].append(c2) break else: continue nodes={c for word in words for c in word} result=[] colors=defaultdict(int) for n in nodes: if colors[n]==WHITE: if self.has_cycle(n, graph, colors, result): return "" return ''.join(result[::-1]) def has_cycle(self, n, graph, colors, result): colors[n]=GRAY for nei in graph[n]: if colors[nei]==GRAY: return True elif colors[nei]==WHITE: if self.has_cycle(nei, graph, colors, result): return True else: continue colors[n]=BLACK result.append(n) return False T: O(C+E) - c is the number of unique characters in both words S: O(C+E)

Answer 60

1. Encode & decode 2. encode : f"{len(s):{s}" 3. decode: i=0 while i str: result="" for s in strs: result+=f"{len(s)}:{s}" return result def decode(self, s: str) -> List[str]: i=0 result=[] while i

Answer 61

1. Backtracking, helper with i, curr, cstring, prev 2. In the callee function, loop through from num (1, len(nums)+1) and send to the helper only the remaining string. 3. The initial parameters are self.helper(nums[i:], target, curr=int(nums[:i]), cstring=nums[:i], prev=int(nums[:i]), result) 4. Within the helper, if not nums and curr==target, then result.append(cstring) 5. if not nums: return 6. Iterate through the remaining num (1, len(nums)-1), three branches - one for add, subtraction and multiply (multiply is tricky) 7. add - params self.helper(nums[i:], target, curr=curr+int(nums[:i]), cstring=cstring+nums[:i], prev=int(nums[:i]), result) 8. sub - params self.helper(nums[i:], target, curr=curr-int(nums[:i]), cstring=cstring-nums[:i], prev=-int(nums[:i]), result) 9. mult - params self.helper(nums[i:], target, curr=curr-prev+prev*int(nums[:i]), cstring=cstring*nums[:i], prev=prev*int(nums[:i]), result) class Solution: def addOperators(self, nums: str, target: int) -> List[str]: result=[] for i in range(1, len(nums)+1): if i==1 or (i>1 and nums[0]!='0'): self.add_operators(nums[i:], target, int(nums[:i]), int(nums[:i]), nums[:i], result) return result def add_operators(self, nums, target, curr, prev, cstring, result): if not nums and curr==target: result.append(cstring) if not nums: return for i in range(1, len(nums)+1): if i==1 or (i>1 and nums[0]!='0'): num=int(nums[:i]) self.add_operators(nums[i:], target, curr+num, num, cstring+'+'+str(num), result) self.add_operators(nums[i:], target, curr-num, -num, cstring+'-'+str(num), result) self.add_operators(nums[i:], target, curr-prev+prev*num, prev*num, cstring+'*'+str(num), result) T: O(3^n) S: O(n)

Answer 62

1. BFS - Do a r,c sweep andadd all 0 to the queue 2. if grid[r][c]==INF, then update grid[r][c]= dist+1 def wallsAndGates(self, rooms: List[List[int]]) -> None: R = len(rooms) C = len(rooms[0]) INF = 2147483647 queue = deque([]) for r in range(R): for c in range(C): if rooms[r][c] == 0: queue.append((r, c, 0)) while queue: r, c, dist = queue.popleft() neis = [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)] for nr, nc in neis: if -1 < nr < R and -1 < nc < C and rooms[nr][nc] == INF: rooms[nr][nc] = dist + 1 queue.append((nr, nc, dist + 1)) T: O(n) S: O(n)

Answer 63

Floyd's cycle finding algorithm is fantastic for this. def findDuplicate(self, nums: List[int]) -> int: tortoise=hare=nums[0] while True: tortoise=nums[tortoise] hare=nums[nums[hare]] if tortoise==hare: break tortoise=nums[0] while tortoise!=hare: hare=nums[hare] tortoise=nums[tortoise] return tortoise T: O(n) S: O(1) def findDuplicate(self, nums: List[int]) -> int: nums.sort() for i in range(1, len(nums)): if i>0 and nums[i]==nums[i-1]: return nums[i] return -1 # store=set() # for num in nums: # if num in store: # return num # store.add(num) # return -1

Answer 64

#live : <2 - die #live : >=2 x <=3 - live #live : >3 - die #dead : =3 - live 1. Iterate through R, C and add count if the people are either 1 or -1 2. Convert living people (1) who are going to die in next cycle as -1 3. Convert dead people with 3 people living around as 2 During the final sweep, convert -1 to 0 and 2 to 1 def gameOfLife(self, board: List[List[int]]) -> None: """ Do not return anything, modify board in-place instead. """ R=len(board) C=len(board[0]) for r in range(R): for c in range(C): neis = [(r+1, c),(r-1, c), (r, c+1), (r, c-1), (r+1, c+1), (r+1, c-1), (r-1, c+1), (r-1, c-1) ] count=0 for nr,nc in neis: if -13 or count<2) and board[r][c]==1: board[r][c]=-1 elif count==3 and board[r][c]==0: board[r][c]=2 for r in range(R): for c in range(C): if board[r][c]==2: board[r][c]=1 elif board[r][c]==-1: board[r][c]=0 T: O(n*m) S: O(1)

Answer 65

1. Have two pq, left_max and right_min 2. Push to left_max if not left_max or incoming num<= - left_max[0] 3. else, push to right_max 4. if len(self.left_max)-len(self.right_min)>=2: pop from left_max and push to right_min 5. vice verse 6. for find median, if both lens are the same, then average. Else, return top class MedianFinder: def __init__(self): self.left_max=[] self.right_min=[] def addNum(self, num: int) -> None: if not self.left_max or num<=-self.left_max[0]: heapq.heappush(self.left_max, -num) else: heapq.heappush(self.right_min, num) if len(self.left_max)-len(self.right_min)>=2: popped=heapq.heappop(self.left_max) heapq.heappush(self.right_min, -popped) elif len(self.right_min)-len(self.left_max)>=2: popped=heapq.heappop(self.right_min) heapq.heappush(self.left_max, -popped) def findMedian(self) -> float: if len(self.left_max)==len(self.right_min): return (-self.left_max[0]+self.right_min[0])/2.0 elif len(self.left_max)>len(self.right_min): return -self.left_max[0] else: return self.right_min[0] T: O(5logn) - O(logn) - at best there are 3 heap insertions and 2 heap deletions at every iteration S: O(n)

Answer 66

1. Simple mid calculation 2. loop thorugh r and c and append to rows and cols array 3. sort both rows and cols and find mid point for both 4. distance=0 5. Loop through rows and calculate abs(mid_dist-r). Same for cols. distance+=abs(c-mid_c)

Answer 67

1. For serialization, BFS. 1. if popped value is '#', append to result 2. Else, append node.val 3. if node.left and right, append to queue. If not append ('#') 4. return ','.join(result) 2. For deserialization, maintain a queue and an index1 (root = TreeNode(data[0) 1. Split data[1:] and add to deque. 2. pop value and see if '#'. If not, append to treenode and increment index (also add to the queue)

Answer 68

1. Zip and iterate. Maintain two dictionary to keep track of counter for s and g 2. If they are equal, add to bulls 3. If they are not, add to s and g counter 4. In order to calculate cows, loop through the secret dictionary and check if character is in g. If yes, cows+= min(counter in s, counter in g) def getHint(self, secret: str, guess: str) -> str: bulls = 0 cows = 0 sd = defaultdict(int) gd = defaultdict(int) for s, g in zip(secret, guess): if s == g: bulls += 1 else: sd[s] += 1 gd[g] += 1 for k in sd: if k in gd: cows += min(sd[k], gd[k]) return f"{bulls}A{cows}B" T: O(n) S: O(n)

Answer 69

1. BFS/Level order traversal - because we need to do minimum number of removals 2. For each popped string in the level, check "is_valid" and add to result and set found=True 3. if found==True, then stop adding to queue because this level is good enough as shortest (but not before adding the items to the queue) 4. For each index in the popped string, if they are not () continue. Else, construct s[:i]+s[i+1:] and add to queue (don't forget the seen because of undirected nature of this/cycle) T: On the first level, there's only one string which is the input string s, let's say the length of it is n, to check whether it's valid, we need O(n) time. On the second level, we remove one ( or ) from the first level, so there are C(n, n-1) new strings, each of them has n-1 characters, and for each string, we need to check whether it's valid or not, thus the total time complexity on this level is (n-1) x C(n, n-1). Come to the third level, total time complexity is (n-2) x C(n, n-2), so on and so forth... Finally we have this formula: T(n) = n x C(n, n) + (n-1) x C(n, n-1) + ... + 1 x C(n, 1) = n x 2^(n-1). S: O(n) (????)

Answer 70

1. Prepare a prefix sum (sums) matrix (R+1, C+1). 2. for r in range(R+1) and for c in range (C+1), sums[r][c]=sums[r-1][c]+ sums[r][c-1]+matrix[r-1][c-1]-sums[r-1][c-1] 3. During sum region, the indices are all incremented by 1 (row1+=1, col1+=1, row2+=1, col2+=1) 4. return sums[row2][col2]-sums[row1-1][col2]-sums[row1][col1-1]+sums[row1-1][col1-1]

Answer 71

1. Level order traversal 2. queue keeps (node, vorder) – (root, 0) 3. for left, add (node.left, vorder-1) and for right (node.right, vorder+1) 3. Keep track of maxi and mini for final result consolidation T: O(n) S: O(n)

Answer 72

1. EMPTY_LAND changes every iteration because we want to traverse only through them. 2. Do a BFS for each EMPTY_LAND and EMPTY_LAND-=1 3. Return the local_min_dist that we saw during each BFS 4. Set the result min_dist to this local_min_dist at the end of each iteration. Return

Answer 73

1. DP - initialized dp to float('inf'), dp[0]=0 def coinChange(self, coins: List[int], amount: int) -> int: dp=[float('inf')]*(amount+1) dp[0]=0 for a in range(1, amount+1): for coin in coins: if a>=coin: dp[a]=min (dp[a], 1+ dp[a-coin]) return dp[-1] if dp[-1]

Answer 74

1. DFS and return self.result 2. Within dfs, if not node, return float('inf'), float('-inf'), 0 for lmax, rmin, count 3. lmax, lmin, count=self.dfs(node.left) and (same for right) 4. count=float('-inf') 5. if lmax<=node.val<=rmin: count=lcount+rcount+1 update self.result 6. return min(lmin, node.val), max(rmax, node.val), count class Solution: def largestBSTSubtree(self, root: Optional[TreeNode]) -> int: self.result=0 self.subtree(root) return self.result def subtree(self, node): if not node: return float('inf'), float('-inf'), 0 lmin, lmax, lcount=self.subtree(node.left) rmin, rmax, rcount=self.subtree(node.right) count=float('-inf') if node.val>lmax and node.val

Answer 75

1. Simple yet tricky. 2. Initialize first and second to inf 3. If num<=first, set first to num 4. If num<=second, second to num 5. else return true def increasingTriplet(self, nums: List[int]) -> bool: first=second=float('inf') for num in nums: if num<=first: first=num elif num<=second: second=num else: return True return False

Answer 76

1. BFS 2. If node.isInteger(), total+=level*each.getInteger() 3. Else, queue.apepnd(node.getList(), level+1) T: O(N) S: O(N) N=total number of nested elements in the input list

Answer 77

1. Create a queue and add the nested iterator to the queue 2. next: return queue.popleft().getInteger() 3. hasnext: check if the queue is empty or not. If not empty, check if the top is integer - (queue[0].isInteger). If integer, return true else: pop off the top (which is a list) and add the elements to the queue (in reverse order) - queue.extendleft(lst.getList()[::-1]) class NestedIterator: def __init__(self, nestedList: [NestedInteger]): self.queue=deque(nestedList) def next(self) -> int: return self.queue.popleft().getInteger() def hasNext(self) -> bool: while self.queue: if self.queue[0].isInteger(): return True else: lst=self.queue.popleft() self.queue.extendleft(lst.getList()[::-1]) T: O(n) S: O(n)

Answer 78

1. Counter and push to heap 2. If len(pq)>k, heappop() 3. Iterate through pq and add to result

Answer 79

1. During the init, hold rows, cols array, self.n 2. diag and anti_diag int 3. Upon move (row, col, player), 1. if r==c, add 1 to self.diag if player 1 or -1 if player 2 2. if r+c==N-1, then add 1 to self.anti_diag if player 1 else -1 3. self.rows[row]+=1 if player 1 else -1 4. self.cols[col]+=1 if player 1 else -1 4. If rows[r]==n or cols[c]==n or self.diag==n or self.anti_diag==n, then return player 5. if rows[r]==-n.. return player

Answer 80

1. Binary search but the search function is to count_values_less_than_mid>=k. If greater, then high=mid-1, result=mid 2. The result=mid is important so that we capture the value which has greater than of "equal to". If it is equal to, we move left a little. 3. in count_values_less_than_mid, c=C-1, for r in range R, while c>=0 and grid[r][c]>mid: c-=1 count+=c+1 (IMPT) return count

Answer 81

1. Three functions, insert, remove, getRandom - create vals array and mapp of val to index 2. Insert: 1. if val not in map, insert to vals, set map's index to be N-1. 3. Remove: 1. if val in map, get index of the item 2. Get last value and identify its index from map 3. swap (overwrite) removable item with last item 4. Update map's index for last item with the removable item's index 5. remove last item from vals 6. remove last item from map 4. getRandom: 1. random.randomint(0, len(vals)-1) 2. return self.vals[ri]

Answer 82

1. Instead of index in the map, maintain a set of indexes. 2. Set pop (for popping a random element) and discard for removing a specific element from set. class RandomizedCollection: def __init__(self): self.vals=[] self.mapp=defaultdict(set) def insert(self, val: int) -> bool: self.vals.append(val) self.mapp[val].add(len(self.vals)-1) return len(self.mapp[val])==1 def remove(self, val: int) -> bool: if self.mapp[val]: rmi=self.mapp[val].pop() #fetch one index last_val=self.vals[-1] self.vals[rmi]=last_val self.mapp[last_val].add(rmi) self.mapp[last_val].discard(len(self.vals)-1) self.vals.pop() return True return False def getRandom(self) -> int: return random.choice(self.vals)

Answer 83

1. Encode & decode 2. encode : f"{len(s):{s}" 3. decode: i=0 while i str: result="" for s in strs: result+=f"{len(s)}:{s}" return result def decode(self, s: str) -> List[str]: i=0 result=[] while i

Answer 84

1. Maintain an index map. 2. Lookup the target value in the map, which would return a list 3. random.randint(0, len(ll)-1). Return ll[random_index]

Answer 85

1. Construct a graph: graph[u].append((v,val)), graph[v].append((u,1/val)) 2. BFS after that.

Answer 86

1. Halve the sum and do DP 2. skip or pick - helper must have index, target, nums and memo def canPartition(self, nums: List[int]) -> bool: summ = sum(nums) if summ & 1: return False target = summ // 2 return self.can_partition(nums, target, 0, {}) def can_partition(self, nums, target, i, memo): if (target, i) in memo: return memo[(target, i)] if target < 0 or i >= len(nums): return False if target == 0: return True # skip num skip = self.can_partition(nums, target, i + 1, memo) # pick num pick = self.can_partition(nums, target - nums[i], i + 1, memo) memo[(target, i)] = skip or pick return skip or pick T: O(M*N) - target*index S: O(M*N) - max memo values is target*index

Answer 87

1. R=0,C=0 is pacific and R-1, C-1 is atlantic - get their starts 2. Do a bfs to get all the r,c which are higher than the neighbours (heights[nr][nc]>=heights[r][c] 3. add all astarts to atops and pstarts to ptops 3. return atops&ptops

Answer 88

1. Iterate through R and C 2. if board[r][c]=='X' and (r==0 or board[r-1][c]=='.') and (c==0 or board[r][c-1]=='.'): count+=1 def countBattleships(self, board: List[List[str]]) -> int: R=len(board) C=len(board[0]) count=0 for r in range(R): for c in range(C): if board[r][c]=='X' and (r==0 or board[r-1][c]=='.') and (c==0 or board[r][c-1]=='.'): count+=1 return count The reason why this works is that since we check only the top and the left, the count will be incremented only for the boundary of the battleship. T: O(N+M) S: O(1)

Answer 89

1. Sort intervals based on end 2. Initialize previous_end to float('-inf') 3. Check if current start >= previous_end: If yes, then there is no overlap. So, set the current_end as previous_end 4. Else, increment the count def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: intervals.sort(key=lambda i: i[1]) pe = float('-inf') count = 0 for cs, ce in intervals: if cs >= pe: pe = ce else: count += 1 return count T:O(nlogn) S: O(1) or O(n) space for sorting

Answer 90

1. DFS with prefix sum - with self.result (int) 2. Call helper with prefix, csum def pathSum(self, node: Optional[TreeNode], target: int) -> int: self.result = 0 prefix = defaultdict(int) prefix[0] = 1 self.dfs(node, target, prefix, 0) return self.result def dfs(self, node, target, prefix, csum): if not node: return csum += node.val self.result += prefix[csum - target] prefix[csum] += 1 self.dfs(node.left, target, prefix, csum) self.dfs(node.right, target, prefix, csum) prefix[csum] -= 1 csum -= node.val T:O(n) S: O(n)

Answer 91

1. Sliding window 2. counter(p), matches 3. The while condition is tricky. class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: counter=Counter(p) ws=0 matches=0 result=[] for we, swe in enumerate(s): if swe in counter: counter[swe]-=1 if counter[swe]==0: matches+=1 while matches==len(counter): if s[ws] in counter: counter[s[ws]]+=1 if counter[s[ws]]>0: matches-=1 if we-ws+1==len(p): result.append(ws) ws+=1 return result

Answer 92

1. Very subtle issues can prop up 2. slow=fast=0 3. Iterate until fast1, then chars[slow+1]=str(c) iteration 6. slow+=1, fast+=1 7. The subtle thing is to set chars[slow]=chars[fast] at the beginning so that the array doesn't retain the original values. def compress(self, chars: List[str]) -> int: slow=fast=0 N=len(chars) while fast1: for c in str(count): chars[slow+1]=c slow+=1 slow+=1 fast+=1 return slow

Answer 93

1. Key functions - count() 2. validate ipv4 and ipv6 separately 3. if ip.count('.')==3, then validate ipv4 4. if ip.count(':')==7, then validate ip6 5. ipv4: comps = ip.split('.'). For each comp, a. if len(comp)==0 or len(comp)>3, then return False b. if (comp[0] and len(comp)!=1) or comp is not digit() or int(comp)>255, return False 6. ipv6: comps=ip.split(':'). For each comp, a. if len(comp)==0 or len(comp)>4: return False b. if not all (c in valids for c in comp): return False valids = "1234567890abcdefABCDEF" So, essentially, 1. do a length check 2. for ipv4, do a digit check and (the digit doesn't start with 0 or int(comp)>255) 3. for ipv6, check if for all letters in comp, check if each letter is in valids

Answer 94

1. Give up already. :-) 2. Just like median in a datastream, use 2 heaps 3. left_max and right_min. Also maintain an count_dict which keeps track of whether the num to the count that is in the heap that needs to be popped/ignored. 4. Step 1: Iterate from 0 to k and push to left_max, then pop from left_max and push to right_min. If right_min's length is greater than left_max (invariant), then pop from right min and push to left max 5. calculate median for the first three values now. 6. Step 2: Iterate from k to len(nums). 7. pick prev_num = nums[i-k] and increment count_dict 8. if the prev_num0, vice versa 13. For the final bit, loop until the the top of the left_max values is in count_dict. If yes, pop off and decrement count_dict 14. Same with right_min 15. Calculate median and return result def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]: left_max = [] right_min = [] result = [] count_dict = defaultdict(int) for i in range(k): heappush(left_max, -nums[i]) heappush(right_min, -heappop(left_max)) if len(right_min) > len(left_max): heappush(left_max, -heappop(right_min)) median = self.find_median(left_max, right_min, k) result.append(median) for i in range(k, len(nums)): prev_num = nums[i - k] count_dict[prev_num] += 1 balance = -1 if prev_num <= median else 1 if nums[i] <= median: balance += 1 heappush(left_max, -nums[i]) else: balance -= 1 heappush(right_min, nums[i]) if balance < 0: heappush(left_max, -heappop(right_min)) elif balance > 0: heappush(right_min, -heappop(left_max)) while left_max and count_dict[-left_max[0]] > 0: count_dict[-left_max[0]] -= 1 heappop(left_max) while right_min and count_dict[right_min[0]] > 0: count_dict[right_min[0]] -= 1 heappop(right_min) median = self.find_median(left_max, right_min, k) result.append(median) return result def find_median(self, max_heap, min_heap, k): if k & 1: return -max_heap[0] else: return (-max_heap[0] + min_heap[0]) / 2 T: O(nlogk) S: O(n)

Answer 95

1. BFS but we'll have to let the path flow until we meet an obstacle 2. Add start to the queue, hold directions array 3. for dr, dr in dirs, nr,nc=r,c while -1

Answer 96

1. Create a list dictionary 2. Iterate through R and C and populate result[r+c] and append to the list 3. For the final result, if the r+c is even (zero index), reverse the list. Else, just append

Answer 97

1. Level order traversal 2. For each level maintain a curr_max and add to result at the end of level exit def largestValues(self, root: Optional[TreeNode]) -> List[int]: if not root: return None queue = deque([root]) result = [] while queue: level = len(queue) cmax = float('-inf') for _ in range(level): node = queue.popleft() cmax = max(cmax, node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(cmax) return result T: O(n) S: O(n) - or O(m) where m = max number of nodes in that level

Answer 98

1. prefix_sum{0:1} 2. csum=(csum+num)%k 3. if csum in prefix (which means that if we subtract that prefix, we get a multiple of k), then check if i-prefix[csum]>=2 4. else, prefix[csum]=i

Answer 99

1. Maintain a prefix_sum {0:0} 2. Enumerate nums starting from 1 (enumerate(nums, 1)) 3. if num==0, sum-=1, else sum+=1 4. if summ in prefix_sum, max_length = max(max_length, i-prefix_sum[summ]) 5. else prefix_sum[sum]=i

Answer 100

1. DFS on click 2. within dfs, if board[r][c] in MX, board[r][c]='X' and return (this enables that click does not cover entire board and returns after it sees a mine) 3. neis - all 4 + diagonal 4. Traverse through all neis and keep track of the count by counting all the 'X' around. This needs to be the value on the grid 5. if count>0, set the board value (str) 6. else set board[nr][nc]='B' and call dfs for all 'E'

Answer 101

1. Use stack 2. num='' 3. if c.isdigit() or c=='-': num+=c 4. if c=='(': create a node and reset num. Add node to stack (only if num) 5. if c==')': if num, then create node and check if stack[-1].left is None. If none append. If right is none, append if not num, then pop node from stack and append to left or right to the stack[-1] def str2tree(self, s: str) -> Optional[TreeNode]: stack=[] num='' for c in s: if c.isdigit() or c=='-': num+=c elif c=='(': if num: node=TreeNode(int(num)) stack.append(node) num='' elif c==')': if num: node=TreeNode(int(num)) num='' if not stack[-1].left: stack[-1].left=node elif not stack[-1].right: stack[-1].right=node else: node=stack.pop() if not stack[-1].left: stack[-1].left=node elif not stack[-1].right: stack[-1].right=node return stack[-1] if stack else TreeNode(int(num)) if s else None T: O(n) S: O(n)

Answer 102

1. Need to return root + left + leaves + right 2. left: node=root.left (this ensures that we always to to the left most node. But if there are right nodes, then we go there and then take the left most node in the right branch) while node left.append(node.val) if node.left: node=node.left else: node=node.right 3. Same for right. But reverse the list since we need to go bottom up while listing 4. Do DFS for leaves if not node: return if node!=root and not node.left and not node.right: leaves.append(node.val) dfs(node.left) dfs(node.right) 5. dfs(node)

Answer 103

1. Like next_permutation 2. Iterate from the N-1 until the values are increasing. (while nums[target-1]>nums[target]: target-=1) 3. if target==0, then return -1 4. Set target=target-1 5. source=N-1 and loop until you have a digit that is lesser than the source (while nums[source]<=nums[target]: source-=1) 6. swap both the values 7. left=target+1, right = len(nums)-1 8. reverse the values 9. if not -1<=result<=2**31-1: return -1 class Solution: def nextGreaterElement(self, n: int) -> int: nums=list(str(n)) target=len(nums)-1 while target>0 and nums[target-1]>=nums[target]: target-=1 if target==0: return -1 target-=1 source=len(nums)-1 while nums[source]<=nums[target]: source-=1 nums[source], nums[target]=nums[target], nums[source] left=target+1 right=len(nums)-1 while left<=right: nums[left], nums[right]=nums[right], nums[left] left+=1 right-=1 ret=int(''.join(nums)) if not 1<=ret<=2**31-1: return -1 return ret T: O(n) S: O(n)

Answer 104

1. Keep prefix_sum=defaultdict, prefix_sum[0]=1 2. if csum-k in prefix_sum, result+=prefix_sum[csum-k] 3. Add prefix_sum[csum]+=1

Answer 105

1. Level order traversal 2. When the level == depth, then create a left and right node whose left and right is the node.left and node.right 3. Also, set node.left=new_left and node.right=new_right 4. Finally add the node.left and node.right to the queue if they aren't null. def addOneRow(self, root: Optional[TreeNode], val: int, depth: int) -> Optional[TreeNode]: clevel = 1 if depth == 1: return TreeNode(val, root, None) queue = deque([root]) while queue: clevel += 1 level = len(queue) for _ in range(level): node = queue.popleft() if clevel == depth: left = TreeNode(val) left.left = node.left node.left = left right = TreeNode(val) right.right = node.right node.right = right if node.left: queue.append(node.left) if node.right: queue.append(node.right) return root T:O(n) S:O(n)

Answer 106

1. Stack. Also maintain result=[0]*N 2. If start, then add to stack. 3. If end, pop from stack and update result[fn]+= diff (end_time-start_time +1 (remember the 1 because of 0 index)) 4. Also peep into the stack and update the result[prev_fn]-= diff

Answer 107

1. Expand from center. 2. Manacher's algorithm can do O(n) def countSubstrings(self, s: str) -> int: result=0 for i in range(len(s)): odd_count=self.expand(s, i, i) even_count=self.expand(s, i, i+1) result+=(odd_count+even_count) return result def expand(self, s, left, right): count=1 while left>=0 and right

Answer 108

1. Binary search 2. If xarr[mid+k]: left=mid+1 else: #x is in array (not true always) ldist=abs(x-arr[mid]) rdist=abs(x-arr[mid+k]) if ldist

Answer 109

1. Convert num to a list of strings 2. Iterate through i to N-1 and check if there are s[i] int: s=list(str(num)) N=len(s) for i in range(N-1): if s[i]=max_num: max_num=s[j] max_index=j for j in range(min_index, -1, -1): if s[j]

Answer 110

1. Maintain a lmin and lmax 2. If you meet a '(', then increment both. If you meet a ')', decrement both 3. If you meet a '*', you could consider it as a left or right parens. So, decrement lmin and increment lmax 4. If lmax<0, then exit. Since, even after factoring '*' as left parens, the count is <0. So, it's not a proper parenthesis string 5. If lmin<0, reset to 0. Since the minimum parenthesis must be equal to 0 6. Finally return lmin==0

Answer 111

1. DFS 2. if not node, return 0 3. recurse for left and right and get the left_len and right_len 4. left_len=(left_len+1) if node.left and node.left.val==node.val else 0 5. right_len=(right_len+1) if node.right and node.right.val==node.val else 0 6. update max_length = max (max_length, left_len+right_len) 7. return max(left_len, right_len) def longestUnivaluePath(self, root: Optional[TreeNode]) -> int: if not root: return 0 longest = 0 def dfs(node): nonlocal longest if not node: return 0 left_len = dfs(node.left) right_len = dfs(node.right) left_len = (left_len + 1) if node.left and node.left.val == node.val else 0 right_len = (right_len + 1) if node.right and node.right.val == node.val else 0 longest = max(longest, left_len + right_len) return max(left_len, right_len) dfs(root) return longest T: O(n) S: O(n)

Answer 112

1. DFS 2. The return value from dfs is the probability which is p+=dfs(n,k-1, nr,nc)/8 def knightProbability(self, n: int, k: int, row: int, column: int) -> float: dirs=[(2,1), (2,-1), (-2,1), (-2,-1), (1,2), (1,-2), (-1,2), (-1,-2)] def dfs(N, k, r, c, memo): if k==0: return 1 if (k,r,c) in memo: return memo[(k,r,c)] p=0 for dr, dc in dirs: nr,nc=r+dr, c+dc if -1

Answer 113

1. Sliding window 2. first_sum=sum(nums[:k]), second_sum= nums[k:2k]... 3. Maintain max_first_sum, max_first_and_second_sum, max_total_sum 4. Also maintain max_first_index, first_and_second_index, total_index 5. Iterate from 1 to len(nums)-3*k+1 6. In each iteration, first_sum+=nums[i+k-1]-nums[i-1] 7. second_sum+=nums[i+2k-1]-nums[i+k-1] def maxSumOfThreeSubarrays(self, nums, k): first_sum = sum(nums[:k]) second_sum = sum(nums[k:2 * k]) third_sum = sum(nums[2 * k:3 * k]) max_first_sum = first_sum max_first_second_sum = first_sum + second_sum max_total_sum = first_sum + second_sum + third_sum max_first_index = [0] max_first_second_index = [0, k] max_total_index = [0, k, 2 * k] for i in range(1, len(nums) - (3 * k) + 1): first_sum += nums[i + k - 1] - nums[i - 1] second_sum += nums[i + 2 * k - 1] - nums[i + k - 1] third_sum += nums[i + 3 * k - 1] - nums[i + 2 * k - 1] if first_sum > max_first_sum: max_first_sum = first_sum max_first_index = [i] if max_first_sum + second_sum > max_first_second_sum: max_first_second_sum = max_first_sum + second_sum max_first_second_index = max_first_index + [i + k] if max_first_second_sum + third_sum > max_total_sum: max_total_sum = max_first_second_sum + third_sum max_total_index = max_first_second_index + [i + 2 * k] return max_total_index

Answer 114

1. Create a helper and return value from helper 2. min_stickers(stickers, target, index) -> int 3. if not target: return 0 4. if index==len(stickers), return float('inf') 5. Skip target, pick target. Skip: result = recursive call, index+1 6. Pick - new_target=target, 7. for c in stickers[index], i=find(new_target, c). 8. if i!=-1, new_target=new_target[:i]+new_target[i+1:]. Also touched=True 9. if touched, result=min(result, self.min_stickers(stickers, new_target, index+1)) 10. return result 11. Remember to return 0 if not target 12. Remember to call self.dfs (with no increment to index) if the sticker is selected. class Solution: def minStickers(self, stickers: List[str], target: str) -> int: result= self.bt(stickers, 0, target, {}) return result if result

Answer 115

1. Do a DFS for each '1' and keep track of the area and max_area 2. Within the dfs. if not -1

Answer 116

1. Sliding window 2. while ws<=we and cprod>=k: cprod/=nums[ws] ws+=1 maxi=max(maxi, we-ws+1))

Answer 117

1. Graph problem (undirected graph) 2. Maintain a name dict as well to map name against email id 3. Iterate through the emails in a list item and map all the candidates [email[i] to email[0]] 4. Do a dfs on graph while keeping seen (undirected graph) 5. While doing dfs, for each unseen item, keep an emails set to keep track of all the emails visited. 6. Add result.append([name]+list(sorted(emails))

Answer 118

1. Tough one - DFS 2. Iterate through s1 and start calling dfs when you match s2[0] 3. Once you find the first char match, do dfs with i and 1 (j), the start indexes of s1 and s2. 4. the return from DFS is the max index of s1, which is j. if j-i str: min_length=float('inf') min_string="" for i, c in enumerate(s1): if c==s2[0]: j=self.dfs(s1, s2, i, 1) if j-i

Answer 119

1. Iterate through the asteroids. 2. If positive asteroid, add to the stack (since only negative creates collisions) 3. If negative, while stack and stack[-1]>0 and stack[-1]

Answer 120

1. Monotonically increasing stack (nums[stack[-1]]

Answer 121

1. In order traversal (while node or stack, if node, add to stack and left, if stack, materialize and right) 2. During materialization, head.next=node, node.prev=head, head=head.next 3. Finally, head.right=sent.right, sent.right.left=head 4. return sent.right

Answer 122

1. Both serialize and deserialize has helper functions. 2. Serialize: preorder - append node.val to result. Iterate through child and recurse for each child. At the end of the iteration, append '#' 3. Deserialize: pop top and create root. Call helper function with queue 4. while queue[0]!='#': child=Node(queue.popleft()) node.children.append(child) self.helper(child) queue.popleft() #pop off the # class Codec: def serialize(self, root: 'Node') -> str: result=[] def preorder(node): if not node: return result.append(str(node.val)) for child in node.children: preorder(child) result.append('#') preorder(root) return ' '.join(result) def deserialize(self, data: str) -> 'Node': if not data: return None queue=deque(data.split()) root=Node(int(queue.popleft())) def helper(node): if not node: return while queue[0]!='#': child=Node(int(queue.popleft())) node.children.append(child) helper(child) queue.popleft() #remove # helper(root) return root T: O(n) S: O(n)

Answer 123

1. Use stack 2. prev=None 3. pop from stack and if prev, prev.next=node, node.prev=prev 4. At the end prev=node 5. if node.next: stack.append(node.next) 6. if node.child: stack.append(node.child) but make the node.child=None def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]': if not head: return head stack=[head] prev=None while stack: node=stack.pop() if prev: prev.next=node node.prev=prev if node.next: stack.append(node.next) if node.child: stack.append(node.child) node.child=None prev=node return head T: O(n) S: O(n)

Answer 124

1. Counter and add it to the max_heap 2. Pop from the top and append to the result. We need to hold this popped from temp so that the next time we choose some other string 3. Before adding the current kv to temp, pop from the previous temp and push it to the heap 4. if updated_count>0, temp=[old_val, updated_count]

Answer 125

1. Particularly tough one. 2. Regular for digits 3. for opening brackets, add op to stack and reset op and num 4. for c in opset or c=='): update(op, num, stack) op=c num=0 if c==')': temp_sum=0 while stack[-1] not in opset: tmp_sum+=stack.pop() update(temp_sum, stack.pop(), stack) def calculate(self, s: str) -> int: stack = [] op = '+' num = 0 opset = set('+-/*') for c in s+'+': if c.isdigit(): num = num*10 + int(c) elif c==')' or c in opset: self.update(num, op, stack) op=c num=0 if c==')': tmp_sum=0 while stack[-1] not in opset: tmp_sum+=stack.pop() self.update(tmp_sum, stack.pop(), stack) elif c=='(': stack.append(op) op='+' num=0 return sum(stack) def update(self, num, op, stack): if op == '+': stack.append(num) elif op == '-': stack.append(-num) elif op == '*': stack.append(stack.pop() * num) elif op == '/': stack.append(int(stack.pop() / num)) T: O(n) S: O(n)

Answer 126

1. Do a counter on target string (s) 2. Iterate through the order. If c (each) is in counter, then result+=c*counter[c] 3. Delete from counter too. 4. Iterate finally through the counter for lingering k,v and append to the end of the result

Answer 127

1. Create a inode in advance with the input value. If not head, just return inode. 2. Three scenarios 3. Middle scenario (easy): if node.val<=insert_val<=node.next.val, break 4. Max and min scenarios: if node.next.val=node.val or insert_val<=node.next.val), break 5. Single node scenario: if node.next==head, break 6. nxt=node.next, node.next=inode, inode.next=nxt

Answer 128

1. Binary search - sort the ages 2. for each age, lb=(age//2+7)+1, ub = age 3. li=bisect_left(ages, lb), ui=bisect_right(ages, ub) 4. if ui-li<=0: continue 5. result+=ui-li 6. exclude current age: if lb<=age<=ub, then result-=1

Answer 129

1. DFS through all 1. Start with island id=2. Mark all islands 2. Also keep track of the island sizes within the dfs (by passing the island_size dict) 3. grid[r][c]=island_id 4. Iterate through the grid and dfs for 0. Look around and fetch unique island_ids (set) 5. Calculate max size based on island_size. Store the max in result.

Answer 130

1. Create goback function with robot.right()*2 with robot.move in middle 2. Prepare directions with clockwise rotation [(0,-1), (-1,0), (0,1), (1,0)] 3. Call dfs with visited and r,c as 0,0. direction=0 4. In the dfs, robot.clean() and add to visited 5. Loop through range(4), the new_direction would be (direction+i)%4 6. nr,nc = r+dirs[new_direction][0] and [1] for r and c 7. If nr,nc not in visited and robot.move(), recurse and goback 8. outside the if condition, robot.turnRight class Solution: def cleanRoom(self, robot): dirs=[(0,-1), (-1,0), (0,1), (1,0)] visited=set() self.dfs(robot, 0, 0, dirs, visited, 0) def dfs(self, robot, r, c, dirs, visited, direction): visited.add((r,c)) robot.clean() for i in range(4): new_direction=(direction+i)%4 nr=r+dirs[new_direction][0] nc=c+dirs[new_direction][1] if (nr,nc) not in visited and robot.move(): self.dfs(robot, nr, nc, dirs, visited, new_direction) self.go_back(robot) robot.turnRight() def go_back(self, robot): robot.turnRight() robot.turnRight() robot.move() robot.turnRight() robot.turnRight() T: O(n) S: O(1)

Answer 131

def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float: result=float('inf') rates=sorted([(w/q, q) for q,w in zip(quality,wage)]) total_quality=0 pq=[] for rate, q in rates: heapq.heappush(pq, -q) total_quality+=q if len(pq)>k: qq=heapq.heappop(pq) total_quality-=-qq if len(pq)==k: result=min(result, total_quality*rate) return result

Answer 132

1. Convert tree to undirected graph using BFS. 2. BFS: Do a BFS on target (target, dist=0), If dist==k: add to result. 4. If dist==k, add to result. And set touched=True. 5. If touched, continue (not break), since we need to look at all the other items in the queue 5. Else, For all other neighbours of the graph, add to queue (provided not seen) T: O(n) S: O(n)

Answer 133

1. DFS with helper - helper has level 2. if not node: return (node, level) 3. left, ldist = self.dfs(node.left, level+1) 4. right, rdist=self.dfs(node.right, level+1) 5. if ldist>rdist: return left, ldist elif rdist>ldist: return right, rdist else: node, ldist

Answer 134

1. Binary search between 1 and max(piles) 2. for pile in piles: hours+=math.ceil(pile//mid) 3. if hours<=h: #we are eating faster than required. right=mid-1 else: left=mid+1 The reason why we are doing right=mid-1 even when the hours <=h is that, we wanted to increase the number of hours. And the way to increase the number of hours is to reduce the size of the mid (pile being constant). In order to decrease the size of the mid, we do right=mid-1

Answer 135

1. Calculate prefix sum array and store. Also keep total 2. Generate a random number between 0 and total (random.random()*self.total) 2. Binary search on the array and return the value

Answer 136

1. Sliding window with window being 2 (while len(mapp)>2) class Solution: def totalFruit(self, fruits: List[int]) -> int: ws = 0 max_fruits = 0 mapp = defaultdict(int) for we, fwe in enumerate(fruits): mapp[fwe] += 1 while len(mapp) > 2: fws = fruits[ws] mapp[fws] -= 1 if mapp[fws] == 0: del mapp[fws] ws += 1 max_fruits = max(max_fruits, we - ws + 1) return max_fruits T: O(n) S: O(n)

Answer 137

1. Do a level order traversal and construct a list from a tree, tree=[None] 2. Return tree[1] for get_tree 3. For insertion, get the size of the tree before inserting the incoming node 4. parent=self.tree[N//2] 5. if N&1, insert to right. Else insert to left class CBTInserter: def __init__(self, root: Optional[TreeNode]): self.tree=[None] self.level_order(root) def insert(self, val: int) -> int: node=TreeNode(val) N=len(self.tree) self.tree.append(node) parent=self.tree[N//2] if N&1: parent.right=node else: parent.left=node return parent.val def get_root(self) -> Optional[TreeNode]: return self.tree[1] def level_order(self, root): queue=deque([root]) while queue: node=queue.popleft() self.tree.append(node) if node.left: queue.append(node.left) if node.right: queue.append(node.right) T: O(1) S: O(n)

Answer 138

1. No need for stack. Two variables can do it. 2. If '(', left+=1 3. if ')' and left>0, left-=1 4. else, right+=1 5. return left+right

Answer 139

1. DFS to find all the r,c that constitute one bridge. Exit after finding 1 2. BFS from all the starting points until we find the next island. return dist-1 def shortestBridge(self, grid: List[List[int]]) -> int: R = len(grid) C = len(grid[0]) isle_one = [] found = False for r in range(R): if not found: for c in range(C): if grid[r][c] == 1: self.dfs(r, c, R, C, isle_one, grid) found = True break return self.bfs(isle_one, grid, R, C) def dfs(self, r, c, R, C, isle_one, grid): isle_one.append((r, c, 0)) grid[r][c] = 0 neis = [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)] for nr, nc in neis: if -1 < nr < R and -1 < nc < C and grid[nr][nc] == 1: self.dfs(nr, nc, R, C, isle_one, grid) def bfs(self, isle_one, grid, R, C): queue = deque(isle_one) seen = set() while queue: r, c, dist = queue.popleft() seen.add((r, c)) if grid[r][c] == 1: return dist - 1 neis = [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)] for nr, nc in neis: if -1 < nr < R and -1 < nc < C and (nr, nc) not in seen: queue.append((nr, nc, dist + 1)) seen.add((nr, nc)) return -1 T: O(M*N) S: O(M*N)

Answer 140

1. BFS and maintain a is_null boolean 2. If we meet an empty node, set the is_null to be true 3. If we meet a node, check if the previous nodes has been null, If yes, return False 4. Add node.left and node.right def isCompleteTree(self, root: Optional[TreeNode]) -> bool: queue=deque([root]) is_null=False while queue: node=queue.popleft() if not node: is_null=True else: if is_null: #some node is not empty in this level return False queue.append(node.left) queue.append(node.right) return True

Answer 141

1. Closest. So, max heap 2. Add to heap, -(x**2+y**2), x,y 3. If len(pq)>k: heappop() 4. While pq, append (x,y) to result and return

Answer 142

1. fi=0, si=0, Iterate through firstList and secondList (fi List[List[int]]: fi=0 si=0 M=len(firstList) N=len(secondList) result=[] while fi

Answer 143

1. Level order traversal. Keep track of (node, vorder). Also max_left and max_right 2. To the result dictionary, add sorted(level_list)

Answer 144

1. Sliding window 2. If you meet a '0', reduce k 3. while k<0: move ws 4. At the end of the loop, we-ws+1

Answer 145

1. Binary search with low=max(weights) and high=sum(weights) 2. Similar to koko eating bananas 3. Even if the days are found, we'll have to try and go for the least weight capacity of the ship - which means that the high=mid-1 (because high = sum(weights), meaning all the weights is being carried by one ship). def shipWithinDays(self, weights: List[int], days: int) -> int: low=max(weights) high=sum(weights) while low<=high: mid=(low+high)//2 total=0 pdays=1 for weight in weights: if total+weight>mid: total=weight pdays+=1 else: total+=weight if pdays<=days: high=mid-1 else: low=mid+1 return low T:O(nlogN) - Since within binary search we are traversing through the weights again. S: O(1)

Answer 146

1. Linear and binary search solution. 2. In the linear solution, iterate from 1, N-1 3. gap = nums[i]-nums[i-1] 4. if gap int: for i in range(1, len(nums)): gap=nums[i]-nums[i-1] -1 if gap int: N=len(nums) if k>self.get_missing_num_counts(nums, N-1): return nums[N-1] +k - self.get_missing_num_counts(nums, N-1) left=0 right=N-1 while left<=right: mid=(left+right)//2 mid_counts=self.get_missing_num_counts(nums, mid) if mid_counts

Answer 147

1. Hard and tricky 2. loop for '-' first and get the level 3. loop for !='-' to get the value 4. create a new node with value 5. if len(stack)>level, pop from stack 6. if stack and stack[-1].left is not populated, then set the node to the left 7. else if stack: set node to the right 8. Finally add the node to the stack. def recoverFromPreorder(self, s: str) -> Optional[TreeNode]: i=0 N=len(s) stack=[] while ilevel: stack.pop() if stack and not stack[-1].left: stack[-1].left=node elif stack: stack[-1].right=node stack.append(node) return stack[0] T: O(s) S: O(s)

Answer 148

1. Backtracking with helper (i=0) 2. Within the helper, if i>=len(arr): return 0 3. Iterate j through (i, min(i+k, len(nums)-1)): curr_max=max(curr_max, nums[i]) window=j-i+1 result=max(result, self.helper(nums, k, j+1) + curr_max*window) class Solution: def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int: return self.max_sum_after_partitioning(arr, k, 0, {}) def max_sum_after_partitioning(self, arr, k, i, memo): if i in memo: return memo[i] if i>=len(arr): return 0 result=0 curr_max=0 for j in range(i, min(i+k, len(arr))): curr_max=max(curr_max, arr[j]) window=j-i+1 result=max(result, self.max_sum_after_partitioning(arr, k, j+1, memo) + curr_max*window) memo[i]=result return result T:O(n*k) - since the helper loop has a max of k range S: O(n)

Answer 149

1. BFS with chess directions. def minKnightMoves(self, x: int, y: int) -> int: dirs = [(2, 1), (-2, 1), (2, -1), (-2, -1), (1, 2), (-1, 2), (1, -2), (-1, -2)] queue = deque([(0, 0, 0)]) visited = set() while queue: r, c, dist = queue.popleft() visited.add((r, c)) if (r, c) == (x, y): return dist for dr, dc in dirs: nr, nc = r + dr, c + dc if (nr, nc) not in visited: visited.add((nr, nc)) queue.append((nr, nc, dist + 1)) return -1 T: O(max(x,y)**2)) S: O(max(x,y)**2))

Answer 150

with product_first_year_cte as ( select product_id, year, quantity, price, rank() over (partition by product_id order by year) as rnum from Sales s ) select product_id, year as first_year, quantity, price from product_first_year_cte where rnum=1

Answer 151

1. BFS. Nothing fancy. Just keep track of the distance 2. Also keep "seen"

Answer 152

1. DP, call helper with left and right (0, N-1) 2. Inside helper - if l==r or l+1==r: return True 3. if k==0: return False (all k is elapsed) 4. Pick/skip 4. Pick: if s[left]==s[right], return self.helper(s,k, left+1, right-1) (no change in k) 5. Skip: skip_left or skip_right 6. skip_left = self.helper(s, k+1, left+1, right) 7. skip_right = self.helper(s, k+1, left, right-1) 8. return skip_left or skip_right

Answer 153

1. Both DFS and BFS can work. 2. For DFS, use helper with root, parent, gp (root, -1, -1) 3. if gp%2==0 result +=node.val 4. result+= dfs(node.left, node.val, parent) and for right 5. For BFS, start with root and -1 to the queue 6. If parent%2==0: if node.left, then add to result if node.right then add to result 7. if node.left: add to queue 8. if node.right: add to queue def sumEvenGrandparent(self, node: TreeNode) -> int: return self.dfs(node, -1, -1) def dfs(self, node, parent, gp): if not node: return 0 x = 0 if gp % 2 == 0: x += node.val x += self.dfs(node.left, node.val, parent) x += self.dfs(node.right, node.val, parent) return x def sumEvenGrandparent(self, node: TreeNode) -> int: queue = deque([(node, -1)]) result = 0 while queue: node, parent = queue.popleft() if parent % 2 == 0: if node.left: result += node.left.val if node.right: result += node.right.val if node.left: queue.append((node.left, node.val)) if node.right: queue.append((node.right, node.val)) return result T: O(n) S: O(n)

Answer 154

1. pick_left, pick_right and pick_both 2. use memo def longestCommonSubsequence(self, text1: str, text2: str) -> int: return self.longest_common_subsequence(text1, text2, 0, 0) def longest_common_subsequence(self, text1, text2, i, j): if i == len(text1) or j == len(text2): return 0 if text1[i] == text2[j]: return 1 + self.longest_common_subsequence(text1, text2, i + 1, j + 1) else: move_first = self.longest_common_subsequence(text1, text2, i + 1, j) move_second = self.longest_common_subsequence(text1, text2, i, j + 1) return max(move_first, move_second)

Answer 155

1. Decreasing mono stack 2. while nums[stack[-1]] List[int]: stack=[] result=[0]*len(heights) for i, h in enumerate(heights): while stack and heights[stack[-1]]

Answer 156

1. Use stack 2. If not stack or stack[-1][0]!=c, then append to stack 3. Else, increment to stack count stack[-1][1]. If stack[-1][1]==k: stack.pop() def removeDuplicates(self, s: str, k: int) -> str: stack=[] for c in s: if not stack or stack[-1][0]!=c: stack.append([c,1]) else: if stack[-1][0]==c: stack[-1][1]+=1 if stack[-1][1]==k: stack.pop() return ''.join([k*cnt for k,cnt in stack]) T: O(n) S: O(n)

Answer 157

1. Define an iter function that retrieves all previous nodes for a target. while l.next and l.next.val0.50: break 5. For erasure, start from top, gather all prevs. For each prevs, if it has next and next.val=target, prevs[i].next=prevs[i].next.next class Node: def __init__(self, val): self.val = val self.next = None self.down = None class Skiplist: def __init__(self, level_depth=16): self.levels = [] prev = None for i in range(level_depth): node = Node(float('-inf')) self.levels.append(node) if prev: prev.down = node prev = node def _iter(self, target): result = [] l = self.levels[0] while l: while l.next and l.next.val < target: l = l.next result.append(l) l = l.down return result def search(self, target: int) -> bool: all_prevs = self._iter(target) last_row_prev = all_prevs[-1] return last_row_prev.next and last_row_prev.next.val == target # only return if the value is the same as target def add(self, num: int) -> None: all_prevs = self._iter(num) prev = None for i in range(len(all_prevs) - 1, -1, -1): node = Node(num) node.next=all_prevs[i].next all_prevs[i].next=node node.down = prev prev = node if random.random() > 0.50: break def erase(self, num: int) -> bool: all_prevs = self._iter(num) found=False for prev in all_prevs: if prev.next and prev.next.val == num: prev.next = prev.next.next found = True return found

Answer 158

1. Convert string to stack and traverse through the string 2. If open, add index to stack 3. If close and stack, pop 4. If no stack, s[i]='' 5. Finally, iterate through stack and empty the string with the indexes in the stack. T: O(n) S: O(n)

Answer 159

1. Maintain a prefix product. Initialize to [1] 2. If while adding, we meet 0, reset the prefix_product to be [1] 3. offset = length-k-1 class ProductOfNumbers: def __init__(self): self.prefix_product = [1] def add(self, num: int) -> None: if num == 0: self.prefix_product = [1] else: self.prefix_product.append(self.prefix_product[-1] * num) def getProduct(self, k: int) -> int: length = len(self.prefix_product) if k >= length: return 0 else: offset = length - k - 1 return self.prefix_product[-1] // self.prefix_product[offset] T: O(n) - O(1) each S: O(n)

Answer 160

1. The requirement is to always traverse from bottom to top. (Also, the list has uneven sizes) 2. The trick is for r in range(R-1, -1, -1) and c is len(nums[r])

Answer 161

1. Undirected graph problem. DFS. 2. cost=self.dfs(child, parent, graph, hasApple). return cost 3. Within dfs, cost=0 and traverse through the neigbours 4. For each nei, if nei==parent (avoid cycle), continue 5. if not, child_cost = self.dfs(nei, child, graph, hasapple) 6. if child_cost>0 or has_apple(nei): then cost=child_cost+2 7 return cost

Answer 162

1. Keep track of result and running_sum 2. If '(', add running_sum+=2 3. If ')', running_sum-=1 4. Return result+running_sum. 5. During the '(', if running_sum&1, then it means that we need to add a closing parens (running_sum-=1 but result+=1) 6. During the ')', if running_sum==0, then there are no open parens and therefore need to insert (running_sum+=2, result+=1) Result keeps track of the net parens to be added. Running keeps track of the weighted values (+2 for open, -1 for closing)

Answer 163

1. In the init, have a store dictionary which holds just the numbers if it is not 0 2. In the dotProduct function, iterating through the store of the incoming 3. If i is in the self.store, then multiply. T: O(N) S: O(N)

Answer 164

1. Dijkstra's shortest path 2. PQ and dist=[[float('inf')] *C for _ in range(R)] 3. Pop from pq, look at the neighbours and compare curr_diff against new_diff 4. new_diff here is max(curr_diff, abs(heights[nr][nc]-heights[r][c]) 5. If new_diff is less than dist[nr][nc], then add to the queue and update dist T: O(ElogV) - E = 4*M*N, V = M*N S: O(M*N)

Answer 165

1. a and b are the places to insert and they are given. 2. while head, if count==a-1, then it's start. If count==b-1, then it's end 3. start.next=list2 4. while list2.next: forward 5. list2.next=end

Answer 166

1. Similar to meeting point of LinkedList 2. Find depth of both nodes using simple iteration (while node, node=node.parent) 3. Compare the longest and shortest. Move longest to the level of shortest (for _ in range(ldepth-sdepth), lnode=lnode.parent) 4. Move both lnode and snode up, lnode=lnode.parent, snode=snode.parent 5. If they are equal return T: O(N) S: O(1)

Answer 167

1. Similar to meeting point of LinkedList 2. Find depth of both nodes using simple iteration (while node, node=node.parent) 3. Compare the longest and shortest. Move longest to the level of shortest (for _ in range(ldepth-sdepth), lnode=lnode.parent) 4. Move both lnode and snode up, lnode=lnode.parent, snode=snode.parent 5. If they are equal return T: O(N) S: O(1)

Answer 168

1. What needs to be build is an array with decreasing values. 2. Monotonic stack where nums[stack[-1]]<=num 3. Remember the "while". while "stack" and nums[stack[-1]]<=num. Not if

Answer 169

1. Do a DFS and construct graph at that time. Identify target as well. 2. Do a BFS and find the shortest path to the target. def findShortestPath(self, master: 'GridMaster') -> int: start=(0,0) directions ={'U': (-1,0), 'D': (1,0), 'L': (0,-1), 'R': (0,1)} anti = {'L': 'R', 'R':'L', 'U':'D', 'D':'U'} graph=defaultdict(list) def dfs(r,c): nonlocal target if not target and master.isTarget(): target=(r,c) return seen.add((r,c)) for d in directions: if master.canMove(d): dr,dc=directions[d] nr,nc = r+dr, c+dc graph[(r,c)].append((nr,nc)) graph[(nr,nc)].append((r,c)) if (nr,nc) not in seen: master.move(d) dfs(nr,nc) master.move(anti[d]) def bfs(start, target): queue=deque([(start[0], start[1], 0)]) while queue: for _ in range(len(queue)): r,c,dist=queue.popleft() seen.add((r,c)) if (r,c)==target: return dist for nr,nc in graph[(r,c)]: if (nr,nc) not in seen: seen.add((nr,nc)) queue.append((nr,nc, dist+1)) return -1 target=None seen=set() dfs(0,0) seen=set() dist=bfs((0,0), target) return dist T: O(M*N) S: O(M*N)

Answer 170

1. Instantiate i, j, M, N and also keep fc and sc (tracks counts) outside the loop 2. Loop through i

Answer 171

1. BIt mask 2. Maintain a dictionary with count, initiliaze count[0]=1 3. Iterate each character, convert it to index (based on ord) 4. mask^=(1< int: mask =0 result=0 count=defaultdict(int) count[0]=1 for c in word: index=ord(c)-ord('a') mask^=(1<

Answer 172

select s.user_id, round(avg(case when action='confirmed' then 1.00 else 0.00 end), 2) as confirmation_rate from signups s left join confirmations c on s.user_id=c.user_id group by s.user_id

Answer 173

1. DFS but keep track of the max_r and max_c def findFarmland(self, land: List[List[int]]) -> List[List[int]]: result = [] R = len(land) C = len(land[0]) def dfs(r, c): land[r][c] = 0 nonlocal max_r, max_c neis = [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)] for nr, nc in neis: if -1 < nr < R and -1 < nc < C and land[nr][nc] == 1: dfs(nr, nc) max_r = max(max_r, nr) max_c = max(max_c, nc) for r in range(R): for c in range(C): if land[r][c] == 1: max_r = r max_c = c dfs(r, c) result.append([r, c, max_r, max_c]) return result T: O(M*N) S: O(M*N)

Answer 174

1. helper with node. return result 2. if not node: return 0, 0 3. lsum,lcount = dfs(node.left) -- rsum,rcount = dfs(node.right) 4. summ=node.val+lsum+rsum 5. count=lcount+rcount+1 6. if node.val == summ//count: result+=1 7. return summ, count class Solution: def averageOfSubtree(self, root: TreeNode) -> int: self.result=0 self.helper(root) return self.result def helper(self, node): if not node: return 0,0 lsum, lcount=self.helper(node.left) rsum, rcount=self.helper(node.right) count=1+lcount+rcount summ=node.val+lsum+rsum if node.val==(summ//count): self.result+=1 return summ,count T: O(n) S: O(n)

Answer 175

1. Maintain a dictionary next_available_day and days variable 2. Iterate through the dict 3. Within the iteration, days = max(next_available_day[task], days+1) #either next day or next available day. Day starts with 0 next_available_day[task]=days+1+space #days stores the current day. So, the least next day must be current_day+space + 1 4. If the task was finished on the first day, the next_available_day for that task must be the 5th day (with 3 spaces). So, 1+3+1 def taskSchedulerII(self, tasks: List[int], space: int) -> int: next_avbl={} days=0 for task in tasks: days=max(next_avbl.get(task, 0), days+1) next_avbl[task]=days+1+space return days T: O(n) S: O(n)

Answer 176

1. Use a counter to do counting on nums[:k] 2. Capture csum=sum(nums[:k]) 3. Short circut - if len(counter)==k: result=csum 4. Iterate from k to len(nums) 5. add current num to csum and mapp 6. remove window passed num (nums[i-k]) from csum and mapp 7. if mapp[nums[i-k]]==0, then delete from mapp 8. Check if the len(mapp)==k, If yes update result 9. return result def maximumSubarraySum(self, nums: List[int], k: int) -> int: mapp = Counter(nums[:k]) summ = sum(nums[:k]) result = 0 if len(mapp) == k: result = summ for i in range(k, len(nums)): # add current num summ += nums[i] mapp[nums[i]] += 1 # subtract num for window passed summ -= nums[i - k] mapp[nums[i - k]] -= 1 if mapp[nums[i - k]] == 0: del mapp[nums[i - k]] if len(mapp) == k: result = max(result, summ) return result T: O(n) S: O(k)

Answer 177

1. Form a min PQ and add reward2-reward1. Since it is a minPQ, all the bigger ones would come up on top. 2. Iterate until k and add the rewards1[index] to the result 3. Keep track of the popped index as visited 3. Iterate through rewards2 and append the ones which is not in visited. def miceAndCheese(self, reward1: List[int], reward2: List[int], k: int) -> int: N = len(reward1) pq = [] for i in range(N): pq.append((reward2[i] - reward1[i], i)) heapq.heapify(pq) result = 0 visited = set() for _ in range(k): r, i = heapq.heappop(pq) result += reward1[i] visited.add(i) for i, r in enumerate(reward2): if i in visited: continue result += reward2[i] return result T: O(nlogk) S: O(n)

Answer 178

1. DP. Initialize dp=[1]*N 2. Iterate from 1,N 3. If nums[i-1]!=nums[i], then dp[i]=dp[i-1]+1 def countAlternatingSubarrays(self, nums: List[int]) -> int: N = len(nums) dp = [1] * N for i in range(1, N): if nums[i] != nums[i - 1]: dp[i] = dp[i - 1] + 1 return sum(dp) T:O(N) S:O(N)

Answer 179

1. Iterate through the grumpy and add to the result customers where grump=0. Set customers to 0 2. Iterate through customers again and add to result. 3. If i>k, then curr_sat = curr_sat-customers[i-k] 4. set max_sat 5. Finally return already_sat with max_sat def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int: already_sat=0 for i,g in enumerate(grumpy): if g==0: already_sat+=customers[i] customers[i]=0 max_sat=0 curr_sat=0 for i, c in enumerate(customers): curr_sat+=c if i>=minutes: curr_sat-=customers[i-minutes] max_sat=max(max_sat, curr_sat) return max_sat+already_sat T: O(n) S: O(1)

Answer 180

1. DP - recursive 2. Either you break the egg or not. 3. If you dropped the egg and it broke, the number of eggs gets reduced by 1 and the floor is reduced by 1 4. If you didn't break the egg, the numebr of eggs remains the same but the floor is reduced by floors-f def twoEggDrop(self, floors: int) -> int: eggs=2 return self.two_egg_drop(floors, eggs) @cache def two_egg_drop(self, floors, eggs): if eggs==1 or floors<=1: return floors mini=float('inf') for f in range(1, floors+1): mini=min(mini, 1+max(self.two_egg_drop(f-1, eggs-1), self.two_egg_drop(floors-f, eggs))) return mini T:O(n^2) S:O(n)

Answer 181

1. Recursive solution. 2. If not grid, return None. 3. If leaf (every single element in the grid has the same value), then return the node. 4. Else, split into 4 recursive calls. def construct(self, grid: List[List[int]]) -> 'Node': if not grid: return None if self.is_leaf(grid): return Node(grid[0][0] == 1, True, None, None, None, None) n = len(grid) return Node('*', False, self.construct([row[:n // 2] for row in grid[:n // 2]]), self.construct([row[n // 2:] for row in grid[:n // 2]]), self.construct([row[:n // 2] for row in grid[n // 2:]]), self.construct([row[n // 2:] for row in grid[n // 2:]])) def is_leaf(self, grid): return len(set([cell for row in grid for cell in row])) == 1 T: O(n^2*log(n)) - At each iteration we do a (n*n)/4 and then do logn for each of them. S: O(logN) recursive calls.

Answer 182

1. Regular basic calculator 2. Create an opset 3. For digit. num*10+int(c) 4. For open parens, just append op to stack and reset op and num (this is for starting a new context) 5. For close parens or c in opset: self.update() set op=c num=0 if c==')': temp_num and while loop until stack[-1] is in opset self.update(temp_num, stack.pop()) - the previous op 6. for c in s+'+' def calculate(self, s: str) -> int: op='+' num=0 opset={'+','-','*','/'} stack=[] for c in s+'+': if c.isdigit(): num=num*10 + int(c) elif c==')' or c in opset: self.update(num, op, stack) op=c num=0 if c==')': tmp_num=0 while stack[-1] not in opset: tmp_num+=stack.pop() self.update(tmp_num, stack.pop(), stack) elif c=='(': stack.append(op) op='+' num=0 return sum(stack) def update(self, num, op, stack): if op=='+': stack.append(num) elif op=='-': stack.append(-num) elif op=='*': prev=stack.pop() stack.append(num*prev) elif op=='/': prev=stack.pop() stack.append(int(prev/num)) T: O(n) S: O(n)