https://leetcode.com/assessment/

### Big O#

• Neetcode
• Big O Cheat Sheet
• Recursive with multiple branches: O(branches^depth), if not repeated work, O(n).
• Fibonacci: O(2^n), with memoization: O(n)
• Permutations, TSP: O(n!)
• Binary search: O(log n) (divide search space)

## Arrays#

``````for n in nums:
# need to shrink?
if cur_sum+n < n: ...
# update result
if cur_sum > max_sum: ...
``````
``````for r in range(len(nums)):
if r-l+1 == k:
...
``````

### Basic & Hashing#

• 🅱️Contains Duplicate☀️: 💡
• `nums = [1,2,3,1]` => `true`
• Hashmap seen or sort
• O(n) time, O(n) space
• 🅱️Valid Anagram☀️: 💡
• `s = "anagram", t = "nagaram"` => `true`
• Counter for each string
• O(s+t) time, O(1) space
• 🅱️🇬Two Sum☀️: 💡
• `nums = [2,7,11,15], target = 9` => `[0,1]`
• Hashmap seen with index
• O(n) time, O(n) space
• 🅱️Group Anagrams⛅: 💡
• `strs = ["tea","tan","ate","nat"]` => `[["nat","tan"],["ate","tea"]]`
• Counter for each string, use tuple as key
• O(strings*average_lenth) time, O(strings) space
• 🅱️Top K Frequent Elements⛅: 💡
• `nums = [1,1,1,2,2,3], k = 2` => `[1,2]`
• Counter, list of frequencies (len(nums)), iterate from end
• O(n) time, O(n) space
• 🅱️Product of Array Except Self⛅: 💡
• `nums = [1,2,3,4]` => `[24,12,8,6]`
• Prefix product, Suffix product.
• O(n) time, O(1) space
• 🇳Valid Sudoku⛅: 💡
• partially filled 9x9 grid
• sets, `squares[(r // 3, c // 3)].add(board[r][c])`
• O(1) time, O(1) space
• 🅱️Encode and Decode Strings⛅: 💡
• Create single string and split it back
• Length + Separator
• O(n) encode, O(n) decode
• 🅱️Longest Consecutive Sequence⛅: 💡
• `nums = [100,4,200,1,3,2]` => `4`
• Set and start if n-1 not in set
• O(n) time, O(n) space

### Two Pointers#

• 🅱️Valid Palindrome☀️: 💡
• `s = "A man, a plan, a canal: Panama"` => `true`
• Two pointers, `if not s[i].isalnum(): i += 1`
• O(n) time, O(1) space
• 🇳Two Sum II⛅: 💡
• `numbers = [2,7,11,15], target = 9` => `[1,2]`
• 2 pointers.
• O(n) time, O(1) space
• 🅱️3Sum⛅: 💡
• `nums = [-1,0,1,2,-1,-4]` => `[[-1,-1,2],[-1,0,1]]`
• sort, 2 pointers
• O(n^2) time, O(n) space (sorting)
• 🅱️Container With Most Water⛅: 💡
• `height = [1,8,6,2,5,4,8,3,7]` => `49`
• start from both ends, move the smaller one
• O(n) time, O(1) space
• 🇳Trapping Rain Water⛈️: 💡
• `height = [0,1,0,2,1,0,1,3,2,1,2,1]` => `6`
• DP, can optimize to O(1) space by using 2 pointers (move `l` if leftmax < rightmax)
• O(n) time, O(n) space

### Sliding Window#

• 🅱️🇬Best Time to Buy and Sell Stock☀️: 💡
• 🅱️🇬Longest Substring Without Repeating Characters⛅: 💡
• `s = "abcabcbb"` => `3` (“abc”)
• Hashmap (seen, index), `ans = max(ans, i - start + 1)`, update start if < index+1
• O(n) time, O(1) space
• 🅱️Longest Repeating Character Replacement⛅: 💡
• `s = "ABAB", k = 2` => `4` (replace both A with B)
• Window with most repeating, shrink `if windowLen - max(count.values()) > k`
• O(n) time, O(1) space
• 🇳Permutation in String⛅: 💡
• `s1 = "ab" s2 = "eidbaooo"` => `true`
• Counter, sliding window of size len(s1)
• O(n) time, O(1) space
• 🅱️Minimum Window Substring⛈️: 💡
• `s = "ADOBECODEBANC", t = "ABC"` => `"BANC"`
• Counter, if all window counter >= counter, shrink
• O(n) time, O(1) space
• 🇳Sliding Window Maximum⛈️: 💡
• `nums = [1,3,-1,-3,5,3,6,7], k = 3` => `[3,3,5,5,6,7]`
• l, r pointers, Monotonic dec deque, store idx, pop everything smaller than current
• O(n) time, O(k) space

## Stack#

• 🅱️Valid Parentheses☀️: 💡
• `s = "()[]{}"` => `true`
• store last opened in stack
• O(n) time, O(n) space
• 🇳Min Stack⛅: 💡
• `push(val)`, `pop()`, `top()`, `getMin()`
• stack, append((min_so_far, val))
• O(1) time, O(n) space
• 🇳 🇬Reverse Polish Notation⛅: 💡
• `tokens = ["2","1","+","3","*"]` => `9`
• `b, a = stack.pop(), stack.pop()``return stack`
• O(2n) time, O(n) space
• 🇳Generate Parentheses⛅: 💡
• `n = 3` => `["((()))","(()())","(())()","()(())","()()()"]`
• stack, backtracking(opened, closed)
• Exponential
• 🇳Daily Temperatures⛅: 💡
• `T = [73,74,75,71,69,72,76,73]` => `[1,1,4,2,1,1,0,0]`
• stack of pending indices, while current > stack[-1], pop and update ans
• O(n) time, O(n) space
• 🇳Car fleet⛅: 💡
• `target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]` => `3`
• Sort by position, start from end, if time to reach is faster than prev, ignore
• O(nlogn) time, O(n) space
• 🇳Largest Rectangle in Histogram⛈️: 💡
• `heights = [2,1,5,6,2,3]` => `10`
• stack, pop bigger than current, calculate area
• O(n) time, O(n) space

Remember it can be used on a range.

• 🇳Binary Search☀️: 💡
• `nums = [-1,0,3,5,9,12], target = 9` => `4`
• while l <= r, mid = (l+r)//2
• O(logn) time, O(1) space
• 🇳Search a 2D Matrix⛅: 💡
• `matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3` => `true`
• `row = mid // len(matrix)`, `col = mid % len(matrix)`
• O(logmn) time, O(1) space
• 🇳Koko Eating Bananas⛅: 💡
• `piles = [3,6,7,11], H = 8` => `4`
• `l, r = 1, max(piles)`, `sum(math.ceil(p/mid) for p in piles) <= h`
• O(nlogm) time, O(1) space
• 🅱️Search in Rotated Sorted Array⛅: 💡
• `nums = [4,5,6,7,0,1,2], target = 0` => `4`
• see which side is sorted and then `if target > nums[mid] or target < nums[l]`
• O(logn) time, O(1) space
• 🅱️Find Minimum in Rotated Sorted Array⛅: 💡
• `nums = [3,4,5,1,2]` => `1`
• stop `if nums[l] < nums[r]`, move `l` if `nums[mid] >= nums[l]`
• O(logn) time, O(1) space
• 🇳Time Based Key-Value Store⛅: 💡
• `set(k, v, time)`, `get(k, time)`
• `if values[m] <= timestamp: res = values[m], l = m + 1`
• O(logn) time, O(n) space
• 🇳 🇬Median of Two Sorted Arrays⛈️: 💡
• `nums1 = [1,2], nums2 = [3,4]` => `2.5`
• Binary search on the shorter array until `Aleft <= Bright and Bleft <= Aright`.
• O(log(m+n)) time, O(1) space

• `head = [1,2]` => `[2,1]`
• while cur: …, tmp, update prev and cur, return prev
• O(n) time, O(1) space
• 🅱️Merge Two Sorted Lists☀️: 💡
• `l1 = [1,2,4], l2 = [1,3,4]` => `[1,1,2,3,4,4]`
• dummy first node, curr node, while l1 and l2, add remaining
• O(n) time, O(1) space
• 🅱️Reorder List💡
• `head = [1,2,3,4]` => `[1,4,2,3]` (L0 -> Ln -> L1 -> Ln-1 -> L2…)
• find mid, reverse second half, merge two lists
• O(n) time, O(1) space
• 🅱️Remove Nth Node From End of List⛅: 💡
• `head = [1,2,3,4,5], n = 2` => `[1,2,3,5]`
• Two pointers, move one n steps ahead.
• O(n) time, O(1) space
• 🇳Copy List with Random Pointer⛅: 💡
• `head = [[3,null],[3,0],[3,null]]` => `[[3,null],[3,0],[3,null]]`
• two passes, copy and then update next and random, `old_to_new = {None: None}`
• O(n) time, O(n) space
• 🇳 🇬Add Two Numbers⛅: 💡
• `l1 = [2,4,3], l2 = [5,6,4]` => `[7,0,8]`
• carry = sum_ // 10, remain = p1 or p2, etc.
• O(max(m,n)) time, O(max(m,n)) space
• `head = [3,2,0,-4], -4 -> 2` => `true`
• slow = fast = head, while fast and fast.next:
• O(n) time, O(1) space
• 🇳Find The Duplicate Number⛅: 💡
• `nums = [1,3,4,2,2]` => `2`
• Floyd’s cycle detection, `slow = nums[slow]; fast = nums[nums[fast]]`, slow2
• O(n) time, O(1) space
• 🇳LRU Cache⛅: 💡
• `LRUCache(int capacity)`, `get(int key)`, `put(int key, int value)`
• double linked list, cache of key to node, dummy head and tail
• O(1) time, O(capacity) space
• 🅱️Merge K Sorted Lists⛈️: 💡
• `lists = [[1,4,5],[1,3,4],[2,6]]` => `[1,1,2,3,4,4,5,6]`
• Merge two lists at a time.
• O(nlogk) time, O(1) space
• 🇳Reverse Nodes in k-Group⛈️: 💡
• `head = [1,2,3,4,5], k = 2` => `[2,1,4,3,5]`
• groupPrev, groupNext, reverse `while curr != groupNext`
• O(n) time, O(1) space

## Trees#

Careful with recursion limit (bound to the application stack)

• 🅱️Invert Binary Tree☀️: 💡
• `root = [4,2,7,1,3,6,9]` => `[4,7,2,9,6,3,1]`
• `r.right, r.left = self.invert(r.left), self.invert(r.right)` or stack
• O(n) time, O(height) space
• 🅱️Maximum Depth of Binary Tree☀️: 💡
• `root = [3,9,20,null,null,15,7]` => `3`
• `return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1`
• O(n) time, O(height) space
• 🇳Diameter of Binary Tree☀️: 💡
• `root = [1,2,3,4,5]` => `3`
• dfs, path: `res = max(res, left+right)`, max length: `return max(left, right) + 1`
• O(n) time, O(height) space
• 🇳Balanced Binary Tree☀️: 💡
• `root = [3,9,20,null,null,15,7]` => `true`
• recursive, `abs(height(left)-height(right)) <= 1`
• O(n) time, O(height) space
• 🅱️Same Tree☀️: 💡
• `p = [1,2,3], q = [1,2,3]` => `true`
• `isSameTree(p.left, q.left) and isSameTree(p.right, q.right)`
• O(n) time, O(height) space
• 🅱️Subtree of Another Tree☀️: 💡
• `s = [3,4,5,1,2], t = [4,1,2]` => `true`
• `isSameTree(s, t) or isSubtree(s.left, t) or isSubtree(s.right, t)`
• O(nm) time, O(n+m) space
• 🅱️Binary Tree Level Order Traversal⛅: 💡
• `root = [3,9,20,null,null,15,7]` => `[,[9,20],[15,7]]`
• `while level: ans.append([node.val for node in level]); level = [...]` or queue
• O(n) time, O(n) space
• 🇳Binary Tree Right Side View⛅: 💡
• `root = [1,2,3,null,5,null,4]` => `[1,3,4]`
• Level order, right most
• O(n) time, O(n) space
• 🇳Count Good Nodes in Binary Tree⛅: 💡
• `root = [3,1,4,3,null,1,5]` => `4`
• dfs, stack = [(node, max_so_far)]
• O(n) time, O(height) space
• 🅱️Construct Binary Tree from Preorder and Inorder Traversal⛅: 💡
• `preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]` => `[3,9,20,null,null,15,7]`
``````root = TreeNode(preorder)
i = inorder.index(root.val)
root.left = self.buildTree(preorder[1:i+1], inorder[:i])
root.right = self.buildTree(preorder[i+1:], inorder[i+1:])
``````
• O(n) time, O(n) space
• 🅱️Binary Tree Maximum Path Sum⛈️: 💡
• `root = [1,2,3]` => `6`
• dfs, allow split or not, nonlocal max
• O(n) time, O(height) space
• 🅱️Serialize and Deserialize Binary Tree⛈️: 💡
• `serialize(self, root)` and `deserialize(self, data)`
• Preorder travelsal, `"1,2,N,N,3,4,N,N,5,N,N"`
• O(n) time, O(n) space

BST: nodes left < node < nodes right

• 🅱️Lowest Common Ancestor of a Binary Search Tree⛅: 💡
• `root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8` => `6`
• cur, left `if p<cur and q<cur`, right `if p>cur and q>cur` else return
• O(n) time, O(1) space
• 🅱️Validate Binary Search Tree⛅: 💡
• `root = [2,1,3]` => `true`
• `validate(n.left, min_val, n.val) and validate(n.right, n.val, max_val)`
• O(n) time, O(height) space
• 🅱️Kth Smallest Element in a BST💡
• `root = [3,1,4,null,2], k = 1` => `1`
• inorder traversal, return res[k-1] (or iterative inorder with stack)
• O(n) time, O(height) space

## Tries#

• 🅱️Implement Trie (Prefix Tree)⛅: 💡
• `insert(word)`, `search(word)`, `startsWith(prefix)`
• node with dict[char, node] and a bool isWord.
• O(n) time, O(n) space
• 🅱️Design Add And Search Words Data Structure⛅: 💡
• `addWord(word)`, `search(word)`
• trie, recursive dfs(idx, node) for “.”
• O(n) time, O(n) space
• 🅱️Word Search II⛈️ 💡
• `board, words = ["oath","pea","eat","rain"]` => `["eat","oath"]`
• build words trie from each cell, dfs
• O(mn*4^mn) time, O(n) space (brute force O(wmn*4^mn))

## Heap & Priority Queue#

• Binary Tree
• Heap invariant: each node is <= than its children.
• Implemented as array: root at `0`, children `2i+1` & `2i+2`, parent at `(i-1)//2`
• 🇳Kth Largest Element in a Stream☀️: 💡
• `KthLargest(int k, int[] nums)`, `add(num) -> int`
• simple minheap, pop if len > k, return heap
• O(logk) time, O(k) space
• 🇳Last Stone Weight☀️: 💡
• `stones = [2,7,4,1,8,1]` => `1`
• Heapify, pop 2 largest, push diff, repeat while len > 1
• O(nlogn) time, O(n) space
• 🇳K Closests Points to Origin⛅: 💡
• `points = [[1,3],[-2,2]], K = 1` => `[[-2,2]]`
• simple maxheap (-dist, x, y), pop if len > k
• O(nlogk) time, O(k) space
• 🇳Kth Largest Element in an Array⛅: 💡
• `nums = [3,2,1,5,6,4], k = 2` => `5`
• quickselect,
• O(2n) average, O(n^2) worst case time, O(1) space
• `tasks = ["A","A","A","B","B","B"], n = 2` => `8`
• max_heap of times, queue, `while max_heap or q`, increase time
• O(n) time, O(1) space
• `postTweet`, `getNewsFeed`, `follow`, `unfollow`
• heap([count, tweetid, foloweeid, index-1])
• O(nlogn) time, O(n) space
• 🅱️Find Median from Data Stream⛈️ 💡
• `addNum(num)` and `findMedian()`
• 2 heaps, max heap for left, min heap for right, balance
• O(logn) time, O(n) space

## Backtracking#

• Subsets:
• append to path, dfs, pop, dfs
• if don’t want duplicates while loop to increase idx before second dfs
• Combinations:
``````for j in range(i, n+1):
path.append(j)
dfs(j+1)
path.pop()
``````
• Permutations:
``````def backtrack(first = 0):
if first == n:
output.append(nums[:])
for i in range(first, n):
nums[first], nums[i] = nums[i], nums[first]
backtrack(first + 1)
nums[first], nums[i] = nums[i], nums[first]
``````

• 🇳Subsets⛅: 💡
• `nums = [1,2,3]` => `[,,,[1,2,3],[1,3],[2,3],[1,2],[]]`
• dfs with backtracking, result and path
• O(n * 2^n) time, O(n) space (recursion stack)
• 🅱️Combination Sum💡
• `candidates = [2,3,6,7], target = 7` => `[,[2,2,3]]`
• dfs, backtracking, append path to global res
• O(2^target) time, O(target) space
• 🇳Permutations⛅: 💡
• `nums = [1,2,3]` => `[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]`
• divide and conquer, remove first, recursive, add back
• O(n^2*n!) time, O(n) space
• 🇳Subsets II⛅: 💡
• `nums = [1,2,2]` => `[,,[1,2,2],[2,2],[1,2],[]]`
• sort, `while i+1 < len(nums) and nums[i] == nums[i+1]:`
• O(n * 2^n) time, O(n) space
• 🇳Combination Sum II⛅: 💡
• `candidates = [10,1,2,7,6,1,5], target = 8` => `[[1,1,6],[1,2,5],[1,7],[2,6]]`
• dfs(pos, target), path = [], top if target <= 0
• O(2^n) time, O(n) space
• 🅱️Word Search💡
• `board = [["A","B","C","E"],["S","F","C","S"],...], word = "ABCCED"` => `true`
• dfs, backtracking, mark visited
• O(mn*4^l) time, O(l) space
• 🇳Palindrome Partitioning⛅: 💡
• `s = "aab"` => `[["a","a","b"],["aa","b"]]`
• res = [], path = [], dfs(pos), for j in range(i, len(s))
• O(n*2^n) time, O(n) space
• 🇳Letter Combinations of a Phone Number⛅: 💡
• `digits = "23"` => `["ad","ae","af","bd","be","bf","cd","ce","cf"]`
• digit_to_char map, dfs, backtracking
• O(n * 4^n) time, O(n) space
• 🇳N Queens⛈️: 💡
• `n = 4` => `[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]`
• dfs(row): for c in range(n), col, pos_diag, neg_diag sets
• O(n!) time, O(n²) space

## Graphs#

• Dijkstra’s Algorithm: shortest path algo, greedy, O(ElogV) time

``````shortest = {}
heap = [(0, src)]
while heap:
w, node = heapq.heappop(heap)
if node in shortest:
continue
shortest[node] = w
if d not in shortest:
heapq.heappush(heap, (w + w2, d))
``````
• Prim’s Algorithm: MST, O(ElogV) time, O(V) space

``````heap = []
heapq.heappush(heap, (w, 0, n))
visited = set()
while heap:
w, s, d = heapq.heappop(heap)
if d in visited:
continue
mst.append((s, d))
if n not in visited:
heapq.heappush(heap, (w2, d, n))
``````
• Kruskal: Union Find

• Topological Sort: Alien dict, dfs to the end and reverse, O(V+E) time, O(V) space

``````result = []
#cycle = set()
visited = set()
def dfs(node):
if node in visited:
return
dfs(n)
result.append(node)
#cycle.remove(node)
for i in range(...):
dfs(i)
return result[::-1]
``````

### Basic#

• 🅱️🇬Number of Islands⛅: 💡
• `grid = [["1", "0"], ["0", "1"]]` => `2`
• skip visited (mark 0 or set), dfs (4 directions) on 1s.
• O(cells) time, O(cells) space
• 🅱️Clone Graph⛅: 💡
• Node with val, neighbors.
• cache[old] = copy, for n in neighbors: copy.neighbors.append(dfs(n))).
• O(v+e) time, O(v) space
• 🇳 🇬Max Area of Island⛅: 💡
• `grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],...,[0,0,0,0,0,0,0,1,1,1,0,0,0]]` => `6`
• return 1 + dfs(4 directions), max_area = max(max_area, dfs)
• O(mn) time, O(mn) space
• 🅱️🇬Pacific Atlantic Water Flow⛅: 💡
• grid of heights.
• start from edge and dfs(x, y, ocean, last_height) to higher, return set intersection
• O(mn) time, O(mn) space
• 🇳Surrounded Regions⛅: 💡
• `board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]`
• dfs regions connected to edge, mark temporary, flip rest.
• O(mn) time, O(1) space
• 🇳Rotting Oranges⛅: 💡
• `grid = [[2,1,1],[1,1,0],[0,1,1]]` => `4`
• BFS, `while queue: minutes+=1 for i in range(len(queue))`, check if any remain
• O(nm) time, O(nm) space
• 🇳Walls and Gates⛅: 💡
• `rooms = [[2147483647,-1,0,2147483647],...,[2147483647,2147483647,2147483647,-1]]`
• BFS, `while queue` pop left, add to queue if `rooms[r][c] > rooms[i][j]+1`
• O(nm) time, O(nm) space
• 🅱️Course Schedule⛅: 💡
• DFS cycle detection (visited set, cycle set).
• O(v+e) time, O(v) space
• 🇳 🇬Course Schedule II⛅: 💡
• `numCourses = 2, prerequisites = [[1,0]]` => `[0,1]`
• DFS topological sort, return [] if cycle, visited and cycle set
• O(v+e) time, O(v) space
• 🇳Redundant Connection⛅: 💡
• `edges = [[1,2], [1,3], [2,3]]` => `[2,3]`
• union find, return edge if cycle (parent == parent[y])
• O(n+m) time, O(n) space
• 🅱️Number of Connected Components in an Undirected Graph⛅: 💡
• `n = 5, edges = [[0, 1], [1, 2], [3, 4]]` => `2`
• union find
• O(n+m) time, O(n) space
• 🅱️Graph Valid Tree⛅: 💡
• `n = 5, edges = [[0, 1], [0, 2], [0, 3], [1, 4]]` => `true`
• adj list, DFS cycle detection, `dfs(0, prev=-1) and n == len(visit)`
• O(e+v) time, O(e+v) space
• `beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]` => `5`
• BFS, queue, create adj list with patterns `pattern = word[:i] + '*' + word[i+1:]`
• O(m^2n) time, O(m^2n) space

• 🇳Reconstruct Itinerary⛈️: 💡
• `tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]` => `["JFK","MUC","LHR","SFO","SJC"]`
• adj list, sort (lexico), dfs
• O(n_flights^max_airport_f) time, O(n_airports+n_flights) space
• 🇳Min Cost to Connect All Points⛅: 💡
• `points = [[0,0],[2,2],[3,10],[5,2],[7,0]]` => `20`
• Prim’s algorithm, `weigth, s, d = heapq.heappop(heap)`
• O(n^2) time, O(n) space
• 🇳Network delay time⛅: 💡
• `times = [[2,1,1],[2,3,1],[3,4,1]]`, `N = 4`, `K = 2` => `2`
• Dijkstra’s algorithm, visited set instead of dist
• O(elogv) time, O(e+v) space
• 🇳 🇬Swim in Rising Water⛈️: 💡
• `grid = [[0,2],[1,3]]` => `3`
• Simple Dijkstra, `heapq.heappush(heap, (max(t, grid[r][c]), r, c))`
• O(n^2 log n) time, O(n^2) space
• 🅱️Alien Dictionary⛈️: 💡
• topological sort, DFS cycle detection.
• 🇳Cheapest Flights Within K Stops⛅: 💡
• `n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]`, `src = 0`, `dst = 2`, `k = 1` => `200`
• BellmanFord, BFS (k+1 times), create `tmp_dist` and `distances = tmp_dist` at the end
• O(k*e) time, O(k*e) space

## Dynamic Programming#

https://youtu.be/mBNrRy2_hVs

• Fibonacci: `dp[i] = dp[i-1] + dp[i-2]`
• Zero / One Knapsack:
• Unbounded Knapsack:
• Longest Common Subsequence:
• Palindromes:

### 1D#

https://youtu.be/_i4Yxeh5ceQ

• 🅱️Climbing Stairs☀️: 💡 Fibonacci
• `n = 2` => `2`, `n = 3` => `3`
• `temp = n1 + n2`
• O(n) time, O(1) space
• 🇳Min cost climbing stairs☀️: 💡
• `cost = [10, 15, 20]` => `15` (start from 0 or 1, 1 or 2 steps)
• `new = min(prev1+c[i-2], prev2+c[i-1]); prev1 = prev2; prev2 = new`
• O(n) time, O(1) space
• 🅱️House Robber⛅: 💡
• `nums = [2,7,9,3,1]` => `12` (2, 9, 1)
• `rob1, rob2 = 0, 0`, `tmp = max(rob1 + n, rob2)`, `return rob2`
• O(n) time, O(1) space
• 🅱️House Robber II⛅: 💡
• `nums = [2,3,2]` => `3` (circular)
• `max(nums, rob1(nums[1:]), rob1(nums[:-1]))`
• O(n) time, O(1) space
• 🅱️🇬Longest Palindromic Substring⛅: 💡
• `s = "babad"` => `"bab"` or `"aba"`
• for i in range(len(s)): expand around l, r = 1, 1 and l, r = i, i+1
• O(n^2) time, O(1) space
• 🅱️Palindrome Substrings⛅: 💡
• `s = "abc"` => `3` (a, b, c)
• similar to the preview one, expand and add to count
• O(n^2) time, O(1) space
• 🅱️Decode Ways⛅: 💡
• `s = "12"` => `2` (“AB” or “L”)
• start from end, `dp[i] = dp[i+1]` add `dp[i+2]` if `dp[i:i+2]` is valid
• O(n) time, O(n) space
• 🅱️Coin Change⛅: 💡 Unbounded Knapsack
• `coins = [1,2,5], amount = 11` => `3`
• Cache and iterate `range(amount+1)`, recursive is O(coins^amount)
• O(coins*amount) time, O(amount) space
• 🅱️Maximum Product Subarray⛅: 💡
• `nums = [2,3,-2,4]` => `6` (2, 3)
• `cur_max, cur_min, max_prod = 1, 1, float('-inf')`, reset if n == 0
• O(n) time, O(1) space
• 🅱️Word Break⛅: 💡
• `s = "leetcode", words = ["leet", "code"]` => `true`
• start from end, `dp[i] = any(dp[i+len(w)] for w in words if s[i:i+len(w)] == w)`
• O(n^2) time, O(n) space
• 🅱️Longest Increasing Subsequence⛅: 💡
• `nums = [10,9,2,5,3,7,101,18]` => `4` (2, 3, 7, 101) strict
• start from end, `if nums[i] < nums[j]: dp[i] = max(dp[i], dp[j] + 1)`
• O(n^2) time, O(n) space
• 🇳Partition Equal Subset Sum⛅: 💡
• `nums = [1,5,11,5]` => `true` (1, 5, 5) and (11)
• target is sum//2, `possible = possible.union({p+n for p in possible})`
• O(n*target) time, O(target) space

### 2D#

• 🅱️🇬Unique Paths💡
• `m = 3, n = 2` => `3`
• `cache[0, 0] = 1; cache[i, j] = cache.get((i-1, j), 0) + cache.get((i, j-1), 0)`
• O(m*n) time, O(m*n) space
• 🅱️Longest Common Subsequence💡
• `text1 = "abcde", text2 = "ace"` => `3` (“ace”)
• dp/recursive, add one and increase both if equal, else get the max of i+1 and j+1
• O(m*n) time, O(m*n) space (can be reduced)
• 🇳Best Time to Buy and Sell Stock with Cooldown⛅: 💡
• `prices = [1,2,3,0,2]` => `3` (buy at 1, sell at 3, buy at 0, sell at 2)
• O(n) time, O(n) space
• 🇳Coin Change 2⛅: 💡
• `amount = 5, coins = [1, 2, 5]` => `4`
• Unbounded Knapsack, dfs(i, amount) = dfs(i+1, amount) + dfs(i, amount-coins[i])
• O(n*amount) time, O(n*amount) space
• 🇳Target Sum⛅: 💡
• assign + or - `nums = [1, 1, 1, 1, 1], target = 3` => `5`
• 0/1 Knapsack, O(2^n) -> O(n*sum(nums)))
• 🇳Interleaving String⛅: 💡
• `s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbc`
• check lengths, `if i < len(s1) and s1[i] == s3[i+j] and dfs(i+1, j): True`
• O(n*m) time, O(n*m) space
• 🇳 🇬Longest Increasing Path in a Matrix⛈️: 💡
• `matrix = [[9,9,4],[6,6,8],[2,1,1]]` => `4` (1, 2, 6, 9)
• `result = max(result, 1+dfs(ii, jj))`, dfs every cell
• O(m*n) time, O(m*n) space
• 🇳Distinct Subsequences⛈️: 💡
• `s = "rabbbit", t = "rabbit"` => `3` (rabbbit, rabbbit, rabbbit)
• `if same: dfs(i+1, j+1) + dfs(i+1, j)` else `dfs(i+1, j)`
• O(n*m) time, O(n*m) space
• 🇳Edit Distance⛈️: 💡
• `word1 = "horse", word2 = "ros"` => `3`
• lru_cache, `dp(len(s1), len(s2))`
• O(m*n) time, O(m*n) space
• 🇳Burst Balloons⛈️: 💡
• `nums = [3,1,5,8]` => `167` (3*1*5 + 3*5*8 + 1*3*8 + 1*8*1)
• `nums =  + nums + `, `dfs(1, lens(nums)-2)`
• O(n^3) time, O(n^2) space
• 🇳Regular Expression Matching⛈️: 💡
• `s = "aa", p = "a"` => `false`
• `match = s[i] == p[j] or p[j] == '.'`, handle `*`, recursive
• O(m*n) time, O(m*n) space (with cache)

## Greedy#

• 🅱️🇬Maximum Subarray⛅: 💡
• `nums = [-2,1,-3,4,-1,2,1,-5,4]` => `6` (`[4,-1,2,1]`)
• `current_sum = max(current_sum+n, n)`, Kadane.
• O(n) time, O(1) space
• 🅱️Jump Game⛅: 💡
• `nums = [2,3,1,1,4]` => `true` (can reach last index)
• start from end, `if i + nums[i] >= target: target = i`.
• O(n) time, O(1) space
• 🇳Jump Game II⛅: 💡
• `nums = [2,3,1,1,4]` => `2` (jump 1 step from index 0 to 1, then 3 steps to the last index)
• l = r = 0, farthest, l = r+1, r = farthest, count += 1
• O(n) time, O(1) space
• 🇳Gas Station⛅: 💡
• `gas = [1,2,3,4,5], cost = [3,4,5,1,2]` => `3` (start at index 3)
• check `sum(gas) >= sum(cost)`, if total is negative, reset and start from next index.
• O(n) time, O(1) space
• 🇳Hand of Straights⛅: 💡
• `hand = [1,2,3,6,2,3,4,7,8], W = 3` => `true`
• counter, iterate keys
• O(n+klogk) time, O(n) space
• 🇳Merge Triplets to Form Target Triplet⛅: 💡
• `triplets = [[2,5,3],[1,8,4],[1,7,5]], target = [2,7,5]` => `true`
• `if any(triplet[i] > target[i] for i in range(3)):` continue, update found[i]
• O(n) time, O(1) space
• 🇳Partition Labels💡
• `s = "ababcbacadefegdehijhklij"` => `[9,7,8]`
• last_idx = {}, end = max(idx, last_idx[c]), if idx == end, add to result.
• O(n) time, O(1) space
• 🇳Valid Parenthesis String⛅: 💡
• `s = "(*)"` => `true`
• left_min, left_max, `if l_max < 0: return False`, `if l_min < 0: l_min = 0`.
• O(3^n)->O(n³)->O()

## Intervals#

• 🅱️🇬Insert Interval⛅: 💡
• `intervals = [[1,3],[6,9]], newInterval = [2,5]` => `[[1,5],[6,9]]` (sorted)
• `if newInterval < interval`, `if newInterval > interval`, else merge
• O(n) time, O(n) space
• 🅱️🇬Merge Intervals⛅: 💡
• `intervals = [[1,3],[2,6],[8,10],[15,18]]` => `[[1,6],[8,10],[15,18]]`
• Sort by start, append to result and merge `if start <= result[-1]`
• O(nlogn) time, O(n) space
• 🅱️Non-overlapping Intervals⛅: 💡
• `intervals = [[1,2],[2,3],[3,4],[1,3]]` => `1` (number of intervals to remove)
• sort, update if start >= prev.end, else increase count
• O(nlogn) time, O(1) space
• 🅱️Meeting Rooms☀️: 💡
• `intervals = [(0,30),(5,10),(15,20)]` => `false`
• sort, if start < prev.end, return false
• O(nlogn) time, O(n) space
• 🅱️🇬Meeting Rooms II⛅: 💡 min number of conference rooms.
• `intervals = [(0,30),(5,10),(15,20)]` => `2`
• sorted starts and ends, s and e pointers, increment count `if start[s] < end[e]`
• O(nlogn) time, O(n) space
• 🇳Minimum Interval to Include Each Query⛈️: 💡
• `intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]` => `[3,-1,3,4]`
• sort intervals & queries, heap (length, end), pop if end < query, dict[query] = length
• O(nlogn + qlogq) time, O(n+q) space

## Math & Geometry#

• 🅱️Rotate Image⛅: 💡
• `matrix = [[1,2,3],[4,5,6],[7,8,9]]` => `[[7,4,1],[8,5,2],[9,6,3]]`
• while l < r, swap 4 corners, move inwards
• O(n^2) time, O(1) space
• 🅱️Spiral Matrix⛅: 💡
• `matrix = [[1,2,3],[4,5,6],[7,8,9]]` => `[1,2,3,6,9,8,7,4,5]`
• 4 pointers, left, right, top, bottom, while l <= r and t <= b
• O(n^2) time, O(1) space
• 🅱️Set Matrix Zeroes⛅: 💡
• `matrix = [[1,1,1],[1,0,1],[1,1,1]]` => `[[1,0,1],[0,0,0],[1,0,1]]`
• use first row and column to store if row or column should be zeroed
• O(mn) time, O(1) space
• 🇳 🇬Happy Number☀️: 💡
• `n = 19` => `true` (`12 + 92 = 82 |...| 12 + 02 + 02 = 1`)
• Hashset seen or Floyd’s cycle detection
• 🇳Plus One☀️: 💡
• `digits = [1,2,3]` => `[1,2,4]`
• carry = (digits[i]+carry) // 10, return +result if carry
• O(n) time, O(n) space
• 🇳Pow(x, n)⛅: 💡
• `x = 2.00000, n = 10` => `1024.00000`
• `helper(x, abs(n))`, recursive helper
• O(n) time, O(n) space
• 🇳Multiply Strings⛅: 💡
• `num1 = "2", num2 = "3"` => `"6"`
• Manual multiplication, reverse, for in for
• O(nm) time, O(n+m) space
• 🇳 🇬Detect Squares⛅: 💡
• `points = [[3,10],[11,5],[11,10]]` => `[true,false,true]`
• `res += self.points_count[x, py] * self.points_count[px, y]`
• O(n) time, O(n) space

## Bit Manipulation (rare)#

Summary

Click to expand
• 🇳Single Number☀️: 💡
• `nums = [2,2,1]` => `1`
• result ^= n
• O(n) time, O(1) space
• 🅱️Number of 1 Bits☀️: 💡
• `n = 11` => `3` (1011)
• either `res += n & 1` and `n >> 1` or just `n = n & (n-1)` and `res += 1`
• O(logn) time, O(1) space
• 🅱️Counting Bits☀️: 💡
• `n = 2` => `[0,1,1]`
• `if offset * 2 == i: offset *= i`, `dp[i] = dp[i-offset] + 1`
• O(n) time, O(n) space
• 🅱️Reverse Bits☀️: 💡
• `00000000000000000000000000000110` => `01100000000000000000000000000000`
• `for i in range(32): bit = (n >> i) & 1`, `res |= bit << (31-i)`
• O(1) time, O(1) space (32 bit)
• 🅱️Missing Number☀️: 💡
• `nums = [3,0,1]` => `2`
• `for i, n in enumerate(nums): res ^= n; res ^= i+1`
• O(n) time, O(1) space
• 🅱️Sum of Two Integers⛅: 💡
• `a = 1, b = 2` => `3`
• `return a if b == 0 else getSum(a^b, (a&b)<<1)`
• 🇳Reverse Integer⛅: 💡
• `x = 123` => `321`
• TODO

## Extra#

Sorting:

Easy:

• 🇬Logger Rate Limiter: 💡
• `shouldPrintMessage(1, "foo"), shouldPrintMessage(3, "foo")` => `true, false`
• Hashmap `{message: timestamp}`, `if self.cache[message] + 10 > timestamp`
• O(1) time, O(n) space
• `n = 5`, `isBadVersion(3) = false`, `isBadVersion(4) = true`
• binary search.
• O(logn) time, O(1) space
• 🇬Longest Common Prefix: 💡
• `strs = ["flower","flow","flight"]` => `"fl"`
• iterate first word and compare
• O(n) time, O(1) space
• 🇬Tic tac toe: 💡
• `moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]` => `"A"`
• 🇬Palindrome Number: 💡
• `x = 121` => `true`
• calculate divider, use mod
• O(logn) time, O(1) space
• 🇬Roman to Integer: 💡
• `s = "III"` => `3`
• iterate, roman_dict, if roman[i] < roman[i+1]: res -= roman[i]
• O(n) time, O(1) space

Medium:

• 🇬Range Sum Query - Mutable: 💡
• `update(i, val)`, `sumRange(i, j)`
• Segment tree
``````class Node(object):
def __init__(self, start, end):
self.start = start
self.end = end
self.total = 0
self.left = None
self.right = None
``````
• O(logn) time, O(n) space
• 🇬Subarray Sum Equals K: 💡
• `nums = [1,1,1], k = 2` => `2` ([1, 1] and [1, 1])
• prefix sum, if increase by k, found (subarray in between), initialize `d = 1`
• O(n) time, O(n) space
• 🇬Find original array from doubled array: 💡
• `changed = [1,3,4,2,6,8]` => `[1,3,4]`
• iterate sorted count, `if count[2*x] >= count[x]`, handle 0, `cnt[2*x] -= cnt[x]`
• O(n + mlogm) time, O(m) space (m = unique elements)
• 🇬Decode String: 💡
• `s = "3[a]2[bc]"` => `"aaabcbc"`
• append to stack `if != ']'`, pop and multiply
• O(n_output) time, O(n_output) space
• 🇬My Calendar I: 💡
• `book(start, end)`, `book(10, 20)`, `book(15, 25)`, `book(20, 30)`
• List (deque) + binary search
• O(n) time, O(n) space
• 🇬Random Pick with Weight: 💡
• `[1,3]`, `pickIndex()` => `0` with 25% probability, `1` with 75% probability
• binary search (random (1, total)) on the prefix sum.
• O(n) time, O(n) space
• 🇬Number of matching subsequences: 💡
• `s = "abcde", words = ["a","bb","acd","ace"]` => `3`
• Hashmap `{char: [(word_idx, current_idx)]}`
• O(s.length+sumcharwords) time, O(#words) space
• 🇬Longest String Chain: 💡
• `words = ["a","b","ba","bca","bda","bdca"]` => `4` (a, b, ba, bda)
• start with shortest, for each word, check if word[:i]+word[i+1:] in dp
• O(nlog(n) + nll) time, O(ns) space
• 🇬Step-By-Step Directions From a Binary Tree Node to Another: [💡]
• TODO
• 🇬The Number of Weak Characters in the Game: 💡
• `properties = [[5,5],[6,3],[3,6]]` => `0`
• sort by `-x,x`, then iterate and keep max y
• O(nlogn) time, O(1) space
• 🇬Maximum Points You Can Obtain from Cards: 💡
• `cardPoints = [1,2,3,4,5,6,1], k = 3` => `12`
• Sliding window, minimum subarray of size n-k.
• O(n) time, O(1) space
• 🇬Stock Price Fluctuation: 💡
• `update(int timestamp, int price)`, `current()`, `maximum()`, `minimum()`
• 2 heaps, timestamps[time, price], self.highest_timestamp.
• 🇬Find Leaves of Binary Tree: [💡]
• dfs, post-order, return layer.
• 🇬Snapshot Array: 💡
• `SnapshotArray(int length)`, `set(index, val)`, `snap()`, `get(index, snap_id)`
• Dict[int, array], binary search on the list of snapshots.
• 🇬Minimum Time Difference: 💡
• `timePoints = ["23:59","00:00"]` => `1`
• map to minutes & sort, `(time[i]-time[i-1])%(24*60)`
• O(nlogn) time, O(n) space
• 🇬Find All Possible Recipes from Given Supplies: 💡
• TODO
• 🇬https://leetcode.com/problems/battleships-in-a-board/?md
• 🇬https://leetcode.com/problems/find-and-replace-in-string/?md
• 🇬https://leetcode.com/problems/the-earliest-moment-when-everyone-become-friends/?md
• 🇬https://leetcode.com/problems/sort-integers-by-the-power-value/?md
• 🇬https://leetcode.com/problems/maximum-number-of-points-with-cost/?md
• 🇬https://leetcode.com/problems/detonate-the-maximum-bombs/?md
• 🇬https://leetcode.com/problems/filling-bookcase-shelves/?md
• 🇬https://leetcode.com/problems/shortest-way-to-form-string/?md
• 🇬https://leetcode.com/problems/rle-iterator/?md
• 🇬https://leetcode.com/problems/check-if-word-can-be-placed-in-crossword/?md
• 🇬https://leetcode.com/problems/sentence-screen-fitting/?md
• 🇬https://leetcode.com/problems/parallel-courses/?md
• 🇬https://leetcode.com/problems/longest-line-of-consecutive-one-in-matrix/?md
• 🇬https://leetcode.com/problems/find-duplicate-subtrees/?md
• 🇬https://leetcode.com/problems/bulls-and-cows/?md
• 🇬https://leetcode.com/problems/time-needed-to-inform-all-employees/?md

Hard:

• 🇬Race Car: 💡
• TODO
• 🇬Text Justification: 💡
• `words = ["This", "is", "an", "example", "of", "text", "justification."] w = 16` => `["This is an", "example of text", "justification. "]`
• `if num_of_letters + len(w) + len(cur) > maxWidth:`, round robin
• 🇬Shortest Path in a Grid with Obstacles Elimination: 💡
• TODO
• 🇬Poor Pigs: 💡
• `buckets = 1000, minutesToDie = 15, minutesToTest = 60` => `5`
• TODO
• 🇬https://leetcode.com/problems/maximum-number-of-visible-points/?hd
• 🇬Range Module 💡
• TODO
• 🇬https://leetcode.com/problems/robot-room-cleaner/?hd
• 🇬https://leetcode.com/problems/employee-free-time/?hd
• 🇬Student Attendance Record II: Fewer than 2 A, no 3 or more consecutive L. [💡]
• `n = 2` => `8` (“PP”, “AP”, “PA”, “LP”, “PL”, “AL”, “LA”, “LL”)
• 🇬https://leetcode.com/problems/meeting-rooms-iii/?hd
• 🇬https://leetcode.com/problems/amount-of-new-area-painted-each-day/?hd
• 🇬https://leetcode.com/problems/number-of-atoms/?hd
• 🇬https://leetcode.com/problems/number-of-good-paths/?hd
• 🇬https://leetcode.com/problems/guess-the-word/?hd
• 🇬https://leetcode.com/problems/shortest-distance-from-all-buildings/?hd
• 🇬https://leetcode.com/problems/maximum-and-sum-of-array/?hd
• 🇬https://leetcode.com/problems/sum-of-prefix-scores-of-strings/?hd
• 🇬https://leetcode.com/problems/basic-calculator/

• KMP pattern matching, O(m+n).
• Maximum Length of Repeated Subarray: Rabin–Karp algorithm / Rolling Hash.

• Longest Duplicate Substring / s: Rabin Karp + Binary Search.

• `set(w1) == set(w2) and Counter(Counter(w1).values()) == Counter(Counter(w2).values()`
• String Compression: 2 pointers, slow and fast.

• `1->2->3->4->5` => `3`
• slow = fast = head, while fast and fast.next: …, return slow
• O(n) time, O(1) space
• `head = [3,2,0,-4], -4 -> 2` => `2`
• dist(intersect, cycle) == dist(head, cycle)
• O(n) time, O(1) space
• Sudoku Solver: `if board[3 * (i // 3) + k // 3][ 3 * (j // 3) + k % 3] == n:`