Some notes about DSA
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
- Kadane’s algorithm: grow and check when to shrink
for n in nums:
# need to shrink?
if cur_sum+n < n: ...
# update result
if cur_sum > max_sum: ...
- Sliding window fixed size: l, r pointers and current window set
for r in range(len(nums)):
if r-l+1 == k:
...
- Sliding window variable size: l, r pointers, iterate over r, grow while possible and shrink
- Two pointers: Palindrome, l, r extreme, choose which to move
- Prefix Sums: Get sum of any subarray in O(1), prefix / suffix products, etc
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☀️:
💡
prices = [7,1,5,3,6,4]
=>5
- Kadane’s algorithm
- O(n) time, O(1) space
- 🅱️🇬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[0]
- 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
Binary Search
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[0])
,col = mid % len(matrix[0])
- 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]
, movel
ifnums[mid] >= nums[l]
- O(logn) time, O(1) space
- 🇳Time Based Key-Value Store⛅:
💡
set(k, v, time)
,get(k, time)
if values[m][1] <= timestamp: res = values[m][0], 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
Linked List
- 🅱️Reverse Linked List☀️:
💡
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
- 🅱️Linked List Cycle☀️:
💡
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]
=>[[3],[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[0]) 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)
anddeserialize(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
, rightif 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
, children2i+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[0]
- 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
- 🇳Task Scheduler⛅:
💡
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
- 🇳Design Twitter⛅:
💡
postTweet
,getNewsFeed
,follow
,unfollow
- heap([count, tweetid, foloweeid, index-1])
- O(nlogn) time, O(n) space
- 🅱️Find Median from Data Stream⛈️
💡
addNum(num)
andfindMedian()
- 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]
=>[[3],[1],[2],[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
=>[[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]
=>[[2],[1],[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 for d, w2 in adj[node]: if d not in shortest: heapq.heappush(heap, (w + w2, d))
Prim’s Algorithm: MST, O(ElogV) time, O(V) space
heap = [] for n, w in adj[0]: 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)) visited.add(d) for n, w2 in adj[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 visited.add(node) for n in adj[node]: 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 ifrooms[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
- 🇳Word Ladder⛈️:
💡
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
Advanced
- 🇳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
anddistances = tmp_dist
at the end - O(k*e) time, O(k*e) space
Dynamic Programming
- Fibonacci:
dp[i] = dp[i-1] + dp[i-2]
- Zero / One Knapsack:
- Unbounded Knapsack:
- Longest Common Subsequence:
- Palindromes:
1D
- 🅱️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[0], 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]
adddp[i+2]
ifdp[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)- cache[i, can_buy], handle cooldown, can_buy and not can_buy
- 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)))
- assign + or -
- 🇳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)
elsedfs(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 = [1] + nums + [1]
,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[1] < interval[0]
,if newInterval[0] > interval[1]
, 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][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 [1]+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)
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
andn >> 1
or justn = n & (n-1)
andres += 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
- 🇬First Bad Version:
💡
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[0] = 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[0],x[1]
, 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/swap-adjacent-in-lr-string/?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
- 🇬https://leetcode.com/problems/expression-add-operators/?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/
Find the Index of the First Occurrence in a String: [💡]
- 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: