Revision cards: all 150 in one page
One card per problem: the key idea, the difficulty and the solution one tap away. Try to recall the approach before you open the code. Filter to what you have not solved yet, or to the problems you flagged for review.
Arrays & Hashing ·
- LeetCode 217Easy
Contains Duplicate
A set answers “have I seen this before?” in one step, so one pass over the list is enough: O(n) time instead of comparing every pair.
Show the Python solution
def contains_duplicate(nums): album = set() for x in nums: if x in album: return True album.add(x) return False - LeetCode 242Easy
Valid Anagram
Count letters with a dictionary (add for one word, subtract for the other). Equal counts mean an anagram, with no sorting needed.
Show the Python solution
def is_anagram(s, t): if len(s) != len(t): return False count = Counter() for ch in s: count[ch] += 1 for ch in t: count[ch] -= 1 if count[ch] < 0: return False return True - LeetCode 1Easy
Two Sum
For each number x, the partner you need is target − x. Store what you have seen in a dictionary and look the partner up in O(1).
Show the Python solution
def two_sum(nums, target): seen = {} # coat rack: number -> ticket for i, x in enumerate(nums): need = target - x if need in seen: return [seen[need], i] seen[x] = i return [] - LeetCode 49Medium
Group Anagrams
Give every word a “signature” that all its anagrams share (its sorted letters) and use it as a dictionary key.
Show the Python solution
def group_anagrams(words): jars = defaultdict(list) for w in words: key = "".join(sorted(w)) # same letters, same key jars[key].append(w) return list(jars.values()) - LeetCode 347Medium
Top K Frequent Elements
Count with a dictionary, then use “bucket by count”: no full sort needed, so it runs in O(n).
Show the Python solution
def top_k_frequent(nums, k): count = Counter(nums) heap = [] # (visits, value), fewest on top for x, c in count.items(): heappush(heap, (c, x)) if len(heap) > k: heappop(heap) return [x for c, x in heap] - LeetCode 271Medium
Encode and Decode Strings
Prefix each word with its length and a marker. Decoding reads the length first, so any character is safe inside the words.
Show the Python solution
def encode(words): return "".join(f"{len(w)}#{w}" for w in words) def decode(tape): out, i = [], 0 while i < len(tape): j = tape.index("#", i) # length ends at the first # n = int(tape[i:j]) out.append(tape[j + 1:j + 1 + n]) i = j + 1 + n return out - LeetCode 238Medium
Product of Array Except Self
Answer[i] = prefix product before i × suffix product after i. Two passes, no division, O(n) time.
Show the Python solution
def product_except_self(nums): n = len(nums) out = [1] * n left = 1 for i in range(n): out[i] = left # product of everything on the left left *= nums[i] right = 1 for i in range(n - 1, -1, -1): out[i] *= right # times everything on the right right *= nums[i] return out - LeetCode 36Medium
Valid Sudoku
Each cell belongs to exactly one row, one column and one box (box = (row//3, col//3)). Three families of sets catch every repeat in one pass.
Show the Python solution
def is_valid_sudoku(board): rows, cols, boxes = defaultdict(set), defaultdict(set), defaultdict(set) for r in range(9): for c in range(9): v = board[r][c] if v == ".": continue b = (r // 3, c // 3) if v in rows[r] or v in cols[c] or v in boxes[b]: return False rows[r].add(v); cols[c].add(v); boxes[b].add(v) return True - LeetCode 128Medium
Longest Consecutive Sequence
Put everything in a set. Only start counting from numbers whose (x − 1) is missing. Each number is visited a constant number of times: O(n).
Show the Python solution
def longest_consecutive(nums): s = set(nums) best = 0 for x in s: if x - 1 not in s: # x starts a run length = 1 while x + length in s: length += 1 best = max(best, length) return best
Two Pointers ·
- LeetCode 125Easy
Valid Palindrome
Two pointers from both ends, skipping non-letters, compare as you go: O(n) time, no extra copy of the string.
Show the Python solution
def is_palindrome(s): l, r = 0, len(s) - 1 while l < r: if not s[l].isalnum(): l += 1 elif not s[r].isalnum(): r -= 1 elif s[l].lower() != s[r].lower(): return False else: l, r = l + 1, r - 1 return True - LeetCode 167Medium
Two Sum II
Sorted input lets two pointers squeeze inward: sum too big → move right pointer left, too small → move left pointer right. O(n).
Show the Python solution
def two_sum(nums, target): l, r = 0, len(nums) - 1 while l < r: s = nums[l] + nums[r] if s == target: return [l + 1, r + 1] # 1-based if s < target: l += 1 else: r -= 1 return [] - LeetCode 15Medium
3Sum
Sort, fix one number, then solve Two Sum II on the rest with two pointers. Skip equal neighbours to avoid duplicates. O(n²).
Show the Python solution
def three_sum(nums): a = sorted(nums) res = [] for i in range(len(a) - 2): if i and a[i] == a[i - 1]: continue l, r = i + 1, len(a) - 1 while l < r: s = a[i] + a[l] + a[r] if s < 0: l += 1 elif s > 0: r -= 1 else: res.append([a[i], a[l], a[r]]) while l < r and a[l] == a[l+1]: l += 1 l, r = l + 1, r - 1 return res - LeetCode 11Medium
Container With Most Water
Area = min(h[l], h[r]) × (r − l). Always move the shorter side inward; you never skip a better pair. O(n).
Show the Python solution
def max_area(h): l, r, best = 0, len(h) - 1, 0 while l < r: best = max(best, (r - l) * min(h[l], h[r])) if h[l] < h[r]: l += 1 else: r -= 1 return best - LeetCode 42Hard
Trapping Rain Water
Water at i = min(maxLeft, maxRight) − height[i]. Two pointers know which side is the limit, so one pass with O(1) memory.
Show the Python solution
def trap(h): l, r = 0, len(h) - 1 left_max = right_max = water = 0 while l < r: if h[l] < h[r]: left_max = max(left_max, h[l]) water += left_max - h[l] l += 1 else: right_max = max(right_max, h[r]) water += right_max - h[r] r -= 1 return water
Sliding Window ·
- LeetCode 121Easy
Best Time to Buy and Sell Stock
Track the minimum price so far and the best (today − minimum). One pass, O(n).
Show the Python solution
def max_profit(prices): if not prices: return 0 # no days cheapest, best = prices[0], 0 for p in prices[1:]: # sell or rebuy? best = max(best, p - cheapest) cheapest = min(cheapest, p) return best - LeetCode 3Medium
Longest Substring Without Repeating Characters
Sliding window + “last seen position” dictionary: when a repeat appears, jump the left edge past the old copy. O(n).
Show the Python solution
def longest_unique(s): last = {} # letter -> last position left = best = 0 for right, ch in enumerate(s): if ch in last and last[ch] >= left: left = last[ch] + 1 last[ch] = right best = max(best, right - left + 1) return best - LeetCode 424Medium
Longest Repeating Character Replacement
A window is fine while (length − count of its most frequent letter) ≤ k. Grow right, shrink left when it breaks. O(n).
Show the Python solution
def character_replacement(s, k): count, left, top, best = Counter(), 0, 0, 0 for right, ch in enumerate(s): count[ch] += 1 top = max(top, count[ch]) # most common colour in window while (right - left + 1) - top > k: # too many planks to repaint count[s[left]] -= 1 left += 1 best = max(best, right - left + 1) return best - LeetCode 567Medium
Permutation in String
Fixed-size window with letter counts. Slide by adding one letter and removing one; compare counts. O(n).
Show the Python solution
def check_inclusion(s1, s2): m = len(s1) need, win = Counter(s1), Counter(s2[:m]) for i in range(m, len(s2)): if win == need: return True win[s2[i]] += 1 # letter enters win[s2[i - m]] -= 1 # letter leaves return win == need - LeetCode 76Hard
Minimum Window Substring
Expand right until the window is valid, then shrink left while it stays valid, tracking the smallest. A “have vs need” counter makes each check O(1). Each character of s enters and leaves the window at most once, so the whole thing is O(m + n) for m = len(s), n = len(t).
Show the Python solution
def min_window(s, t): need, have = Counter(t), Counter() missing = len(t) best, left = "", 0 for right, ch in enumerate(s): if have[ch] < need[ch]: missing -= 1 have[ch] += 1 while missing == 0: # net has all size = right - left + 1 if not best or size < len(best): best = s[left:right + 1] have[s[left]] -= 1 if have[s[left]] < need[s[left]]: missing += 1 left += 1 return best - LeetCode 239Hard
Sliding Window Maximum
A deque kept in decreasing order: the front is always the maximum. Each tower is added and removed at most once: O(n).
Show the Python solution
def max_window(h, k): dq, out = deque(), [] # positions, tallest at front for i, x in enumerate(h): while dq and h[dq[-1]] <= x: dq.pop() dq.append(i) if dq[0] <= i - k: dq.popleft() if i >= k - 1: out.append(h[dq[0]]) return out
Stack ·
- LeetCode 20Easy
Valid Parentheses
Last opened must be first closed, which is exactly what a stack (last in, first out) gives you. O(n).
Show the Python solution
def is_valid(s): pairs = {")": "(", "]": "[", "}": "{"} stack = [] for ch in s: if ch not in pairs: stack.append(ch) elif not stack or stack.pop() != pairs[ch]: return False return not stack - LeetCode 155Medium
Min Stack
Store (value, minimum so far) with every entry. The top entry always knows the current minimum: every operation is O(1).
Show the Python solution
class MinStack: def __init__(self): self.stack = [] # (value, min so far) def push(self, x): low = min(x, self.stack[-1][1]) if self.stack else x self.stack.append((x, low)) def pop(self): self.stack.pop() def top(self): return self.stack[-1][0] def get_min(self): return self.stack[-1][1] - LeetCode 150Medium
Evaluate Reverse Polish Notation
Numbers push; operators pop two, compute, push the result. One pass with a stack, O(n).
Show the Python solution
OPS = {"+": add, "-": sub, "*": mul, "/": lambda a, b: int(a / b)} def eval_rpn(tokens): stack = [] for t in tokens: if t in OPS: b = stack.pop() a = stack.pop() stack.append(OPS[t](a, b)) else: stack.append(int(t)) return stack[0] - LeetCode 22Medium
Generate Parentheses
Backtracking with two counts (open used, close used). Only add “)” when close < open, so every result is valid by construction.
Show the Python solution
def generate(n): out = [] def build(s, opened, closed): if len(s) == 2 * n: out.append(s) return if opened < n: build(s + "(", opened + 1, closed) if closed < opened: build(s + ")", opened, closed + 1) build("", 0, 0) return out - LeetCode 739Medium
Daily Temperatures
A “monotonic stack” keeps waiting days in decreasing temperature. Each day is pushed and popped once: O(n).
Show the Python solution
def daily_temperatures(temps): wait = [0] * len(temps) stack = [] # days still waiting, coolest on top for i, t in enumerate(temps): while stack and temps[stack[-1]] < t: j = stack.pop() wait[j] = i - j # day j finally got warmer stack.append(i) return wait - LeetCode 853Medium
Car Fleet
Sort by position (closest to the finish first) and compare arrival times; a new fleet starts only when a car is slower to arrive than the fleet ahead.
Show the Python solution
def car_fleet(target, position, speed): cars = sorted(zip(position, speed), reverse=True) # front first fleets = [] # arrival time of each fleet for pos, spd in cars: t = (target - pos) / spd if not fleets or t > fleets[-1]: fleets.append(t) # too slow to catch up: new fleet # else: catches the fleet ahead and joins it return len(fleets) - LeetCode 84Hard
Largest Rectangle in Histogram
Monotonic increasing stack: when a bar is popped, the current index is its right limit and the new stack top is its left limit. O(n).
Show the Python solution
def largest_rectangle(h): stack, best = [], 0 # positions with rising heights for i, x in enumerate(h + [0]): while stack and h[stack[-1]] >= x: height = h[stack.pop()] left = stack[-1] + 1 if stack else 0 best = max(best, height * (i - left)) stack.append(i) return best
Binary Search ·
- LeetCode 704Easy
Binary Search
Keep a range [lo, hi] that must contain the answer and halve it every step: O(log n).
Show the Python solution
def search(books, target): lo, hi = 0, len(books) - 1 while lo <= hi: mid = (lo + hi) // 2 if books[mid] == target: return mid if books[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1 - LeetCode 74Medium
Search a 2D Matrix
Treat the 2-D grid as one sorted 1-D list and binary search it: O(log(rows × cols)).
Show the Python solution
def search_matrix(m, target): rows, cols = len(m), len(m[0]) lo, hi = 0, rows * cols - 1 # treat it as one long sorted list while lo <= hi: mid = (lo + hi) // 2 r, c = divmod(mid, cols) # which floor, which door if m[r][c] == target: return True if m[r][c] < target: lo = mid + 1 else: hi = mid - 1 return False - LeetCode 875Medium
Koko Eating Bananas
Binary search on the answer: if a speed works, every faster speed works too. O(n · log(max pile)).
Show the Python solution
def min_eating_speed(piles, h): lo, hi = 1, max(piles) while lo < hi: k = (lo + hi) // 2 hours = sum(ceil(p / k) for p in piles) if hours <= h: hi = k # fast enough; try slower else: lo = k + 1 # too slow return lo - LeetCode 153Medium
Find Minimum in Rotated Sorted Array
Compare nums[mid] with nums[hi] to know which half holds the rotation point, and binary search into it.
Show the Python solution
def find_min(a): lo, hi = 0, len(a) - 1 while lo < hi: mid = (lo + hi) // 2 if a[mid] > a[hi]: lo = mid + 1 # the drop is to the right of mid else: hi = mid # mid..hi is sorted; min is at mid or left return a[lo] - LeetCode 33Medium
Search in Rotated Sorted Array
At every step one half is sorted. Test whether the target is inside that sorted range to choose a side.
Show the Python solution
def search(a, t): lo, hi = 0, len(a) - 1 while lo <= hi: mid = (lo + hi) // 2 if a[mid] == t: return mid if a[lo] <= a[mid]: # left half is in order if a[lo] <= t < a[mid]: hi = mid - 1 else: lo = mid + 1 else: # right half is in order if a[mid] < t <= a[hi]: lo = mid + 1 else: hi = mid - 1 return -1 - LeetCode 981Medium
Time Based Key-Value Store
Store (time, value) lists per key in time order; get = binary search for the last time ≤ t. O(log n) per get.
Show the Python solution
class TimeMap: def __init__(self): self.pages = defaultdict(list) # key -> [(time, value)] def set(self, key, value, time): self.pages[key].append((time, value)) # times only increase def get(self, key, time): pages, ans = self.pages[key], "" lo, hi = 0, len(pages) - 1 while lo <= hi: # last page with time <= t mid = (lo + hi) // 2 if pages[mid][0] <= time: ans, lo = pages[mid][1], mid + 1 else: hi = mid - 1 return ans - LeetCode 4Hard
Median of Two Sorted Arrays
Binary search a partition of the shorter list; check maxLeft ≤ minRight on both sides. O(log(min(m, n))).
Show the Python solution
def median(a, b): if len(a) > len(b): a, b = b, a m, n = len(a), len(b) lo, hi, half = 0, m, (m + n + 1) // 2 while lo <= hi: i = (lo + hi) // 2 # cut in a j = half - i # matching cut in b a_left = a[i - 1] if i > 0 else -inf a_right = a[i] if i < m else inf b_left = b[j - 1] if j > 0 else -inf b_right = b[j] if j < n else inf if a_left <= b_right and b_left <= a_right: if (m + n) % 2: return max(a_left, b_left) return (max(a_left, b_left) + min(a_right, b_right)) / 2 if a_left > b_right: hi = i - 1 else: lo = i + 1
Linked List ·
- LeetCode 206Easy
Reverse Linked List
Remember next, point curr back at prev, then move both forward. O(n) time, O(1) extra space.
Show the Python solution
def reverse(head): prev, curr = None, head while curr: nxt = curr.next curr.next = prev prev = curr curr = nxt return prev - LeetCode 21Easy
Merge Two Sorted Lists
Always take the smaller front node; a dummy head avoids special cases. O(m + n).
Show the Python solution
def merge(a, b): dummy = tail = Node(0) while a and b: if a.val <= b.val: tail.next, a = a, a.next else: tail.next, b = b, b.next tail = tail.next tail.next = a or b return dummy.next - LeetCode 143Medium
Reorder List
Find the middle, reverse the second half, merge alternately. O(n) time, O(1) space.
Show the Python solution
def reorder_list(head): slow = fast = head while fast.next and fast.next.next: # 1. find the middle slow, fast = slow.next, fast.next.next prev, curr = None, slow.next # 2. reverse the back half slow.next = None while curr: curr.next, prev, curr = prev, curr, curr.next a, b = head, prev # 3. zip the halves while b: a.next, a = b, a.next b.next, b = a, b.next - LeetCode 19Medium
Remove Nth Node From End of List
Keep a gap of n between two pointers; when the leader reaches the end, the follower is just before the target. One pass.
Show the Python solution
def remove_nth(head, n): dummy = Node(0, head) fast = slow = dummy for _ in range(n + 1): fast = fast.next while fast: fast, slow = fast.next, slow.next slow.next = slow.next.next return dummy.next - LeetCode 138Medium
Copy List with Random Pointer
A dictionary from old node to new node lets you wire every pointer in a second pass. O(n).
Show the Python solution
def copy_random(head): clone = {None: None} node = head while node: clone[node] = Node(node.val) node = node.next node = head while node: clone[node].next = clone[node.next] clone[node].random = clone[node.random] node = node.next return clone[head] - LeetCode 2Medium
Add Two Numbers
Column addition walking both lists at once, carrying as you go. O(max(m, n)).
Show the Python solution
def add(l1, l2): # digits stored backwards dummy = tail = Node(0) carry = 0 while l1 or l2 or carry: s = carry + (l1.val if l1 else 0) + (l2.val if l2 else 0) carry, digit = divmod(s, 10) tail.next = Node(digit) tail = tail.next l1 = l1.next if l1 else None l2 = l2.next if l2 else None return dummy.next - LeetCode 141Easy
Linked List Cycle
Floyd’s fast/slow pointers: they meet if and only if there is a cycle. O(n) time, O(1) space.
Show the Python solution
def has_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: return True return False - LeetCode 287Medium
Find the Duplicate Number
Treat values as “next” pointers; the duplicate is the start of a cycle. Floyd’s algorithm finds it in O(n) time, O(1) space.
Show the Python solution
def find_duplicate(nums): # box i holds a note: "go to box nums[i]" slow = fast = 0 while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break slow = 0 while slow != fast: slow, fast = nums[slow], nums[fast] return slow # two notes point here: the duplicate - LeetCode 146Medium
LRU Cache
Hash map for O(1) lookup + doubly linked list for O(1) reordering and eviction.
Show the Python solution
class LRUCache: def __init__(self, capacity): self.cap, self.data = capacity, OrderedDict() # oldest first def get(self, key): if key not in self.data: return -1 self.data.move_to_end(key) # just used: now newest return self.data[key] def put(self, key, value): self.data[key] = value self.data.move_to_end(key) if len(self.data) > self.cap: self.data.popitem(last=False) # evict the oldest - LeetCode 23Hard
Merge k Sorted Lists
A min-heap of the k front nodes gives the next smallest in O(log k): total O(N log k).
Show the Python solution
def merge_k(lists): heap = [(l.val, i, l) for i, l in enumerate(lists) if l] heapify(heap) dummy = tail = Node(0) while heap: val, i, node = heappop(heap) tail.next = node tail = node if node.next: heappush(heap, (node.next.val, i, node.next)) return dummy.next - LeetCode 25Hard
Reverse Nodes in k-Group
Count k ahead, reverse that segment in place, stitch it back, repeat. O(n) time, O(1) space.
Show the Python solution
def reverse_k(head, k): dummy = group_prev = Node(0, head) while True: kth = group_prev for _ in range(k): kth = kth.next if not kth: return dummy.next nxt = kth.next prev, curr = nxt, group_prev.next while curr is not nxt: curr.next, prev, curr = prev, curr, curr.next first = group_prev.next group_prev.next = kth group_prev = first
Trees ·
- LeetCode 226Easy
Invert Binary Tree
Recursion: invert the left subtree, invert the right subtree, swap them. Every node is visited once: O(n).
Show the Python solution
def invert_tree(node): if not node: return None invert_tree(node.left) invert_tree(node.right) node.left, node.right = node.right, node.left # swing the two arms return node - LeetCode 104Easy
Maximum Depth of Binary Tree
depth(node) = 1 + max(depth(left), depth(right)). O(n).
Show the Python solution
def max_depth(node): if not node: return 0 left = max_depth(node.left) right = max_depth(node.right) return 1 + max(left, right) - LeetCode 543Easy
Diameter of Binary Tree
One DFS returning height; at each node update best = max(best, leftHeight + rightHeight). O(n).
Show the Python solution
def diameter(root): best = 0 def depth(node): nonlocal best if not node: return 0 l, r = depth(node.left), depth(node.right) best = max(best, l + r) # path that bends at this node return 1 + max(l, r) depth(root) return best - LeetCode 110Easy
Balanced Binary Tree
Compute heights bottom-up and return −1 as soon as a node is unbalanced. One pass, O(n).
Show the Python solution
def is_balanced(root): def height(node): if not node: return 0 l = height(node.left) r = height(node.right) if l < 0 or r < 0 or abs(l - r) > 1: return -1 # unbalanced below return 1 + max(l, r) return height(root) >= 0 - LeetCode 100Easy
Same Tree
Recursive lockstep walk: same(p, q) = values equal and same(left, left) and same(right, right). O(n).
Show the Python solution
def is_same(p, q): if not p and not q: return True if not p or not q or p.val != q.val: return False return is_same(p.left, q.left) and is_same(p.right, q.right) - LeetCode 572Easy
Subtree of Another Tree
For every node in the big tree, run isSameTree against the small tree. O(m × n) in the worst case.
Show the Python solution
def is_subtree(root, sub): if not root: return False if is_same(root, sub): # stencil fits? return True return (is_subtree(root.left, sub) or is_subtree(root.right, sub)) def is_same(a, b): if not a or not b: return a is b # both empty? return (a.val == b.val and is_same(a.left, b.left) and is_same(a.right, b.right)) - LeetCode 235Medium
Lowest Common Ancestor of a Binary Search Tree
Use the BST ordering: walk down while p and q are on the same side. O(height).
Show the Python solution
def lca(root, p, q): node = root while node: if p < node.val and q < node.val: node = node.left # both are smaller: go left elif p > node.val and q > node.val: node = node.right # both are bigger: go right else: return node # they split here - LeetCode 102Medium
Binary Tree Level Order Traversal
Breadth-first search with a queue, processing one level (queue length) at a time. O(n).
Show the Python solution
def level_order(root): if not root: return [] q, out = deque([root]), [] while q: level = [] for _ in range(len(q)): node = q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) out.append(level) return out - LeetCode 199Medium
Binary Tree Right Side View
BFS by levels and keep the last value of each level. O(n).
Show the Python solution
def right_side_view(root): view, q = [], deque([root] if root else []) while q: view.append(q[-1].val) # last in the row is visible for _ in range(len(q)): node = q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) return view - LeetCode 1448Medium
Count Good Nodes in Binary Tree
DFS carrying the max value on the path; a node is good if its value ≥ that max. O(n).
Show the Python solution
def good_nodes(root): def walk(node, tallest): if not node: return 0 good = 1 if node.val >= tallest else 0 tallest = max(tallest, node.val) return good + walk(node.left, tallest) + walk(node.right, tallest) return walk(root, root.val) - LeetCode 98Medium
Validate Binary Search Tree
Pass (low, high) bounds down the tree and tighten them at each step. O(n).
Show the Python solution
def is_valid_bst(root): def check(node, lo, hi): if not node: return True if not (lo < node.val < hi): return False return check(node.left, lo, node.val) and check(node.right, node.val, hi) return check(root, -inf, inf) - LeetCode 230Medium
Kth Smallest Element in a BST
Inorder traversal of a BST is sorted; stop after k visits. O(height + k).
Show the Python solution
def kth_smallest(root, k): stack, node = [], root while stack or node: while node: # slide down to the smallest stack.append(node) node = node.left node = stack.pop() k -= 1 if k == 0: return node.val node = node.right - LeetCode 105Medium
Construct Binary Tree from Preorder and Inorder Traversal
Preorder gives the root; its position in inorder splits left and right subtrees. With a value→index map: O(n).
Show the Python solution
def build(preorder, inorder): where = {v: i for i, v in enumerate(inorder)} nxt = iter(preorder) # preorder gives roots in order def make(lo, hi): # inorder[lo..hi] if lo > hi: return None root = Node(next(nxt)) mid = where[root.val] # splits left and right root.left = make(lo, mid - 1) root.right = make(mid + 1, hi) return root return make(0, len(inorder) - 1) - LeetCode 124Hard
Binary Tree Maximum Path Sum
DFS returns the best downward gain; update best with left + node + right, clamping negative gains to 0. O(n).
Show the Python solution
def max_path_sum(root): best = -inf def gain(node): nonlocal best if not node: return 0 l = max(gain(node.left), 0) # ignore losing branches r = max(gain(node.right), 0) best = max(best, node.val + l + r) return node.val + max(l, r) gain(root) return best - LeetCode 297Hard
Serialize and Deserialize Binary Tree
Preorder with null markers makes the encoding unambiguous; decoding reads the tokens back in the same order. O(n).
Show the Python solution
def serialize(root): out = [] def walk(n): if not n: out.append("#"); return # mark empty spots out.append(str(n.val)); walk(n.left); walk(n.right) walk(root) return ",".join(out) def deserialize(data): tokens = iter(data.split(",")) def make(): t = next(tokens) if t == "#": return None n = Node(int(t)); n.left = make(); n.right = make() return n return make()
Tries ·
- LeetCode 208Medium
Implement Trie (Prefix Tree)
Each node holds children by letter plus an end-of-word flag. Every operation costs O(length of the word).
Show the Python solution
class Trie: def __init__(self): self.root = {} def insert(self, word): node = self.root for ch in word: node = node.setdefault(ch, {}) # grow a branch if missing node["$"] = True # mark: a word ends here def search(self, word, prefix=False): node = self.root for ch in word: if ch not in node: return False node = node[ch] return prefix or "$" in node def starts_with(self, prefix): return self.search(prefix, prefix=True) - LeetCode 211Medium
Design Add and Search Words Data Structure
Trie + depth-first search: branch over all children on “.”. Plain letters stay O(length).
Show the Python solution
class WordDictionary: def __init__(self): self.root = {} def add_word(self, word): node = self.root for ch in word: node = node.setdefault(ch, {}) node["$"] = True def search(self, word, node=None, i=0): node = self.root if node is None else node if i == len(word): return "$" in node if word[i] == ".": # try every branch return any(self.search(word, kid, i + 1) for ch, kid in node.items() if ch != "$") return word[i] in node and self.search(word, node[word[i]], i + 1) - LeetCode 212Hard
Word Search II
Build a trie of all words and run one backtracking search over the grid, pruned by the trie.
Show the Python solution
def find_words(board, words): trie = build_trie(words) # "$" = end found = [] def dfs(r, c, node): ch = board[r][c] if ch not in node: return # dead end node = node[ch] if "$" in node: found.append(node.pop("$")) board[r][c] = "#" # in use for nr, nc in nbrs(board, r, c): if board[nr][nc] != "#": dfs(nr, nc, node) board[r][c] = ch for r, c in all_cells(board): dfs(r, c, trie) return found def build_trie(words): root = {} for w in words: node = root for ch in w: node = node.setdefault(ch, {}) node["$"] = w return root def all_cells(g): return [(r, c) for r in range(len(g)) for c in range(len(g[0]))] def nbrs(g, r, c): # in-grid neighbours R, C = len(g), len(g[0]) for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)): if 0 <= nr < R and 0 <= nc < C: yield nr, nc
Heap / Priority Queue ·
- LeetCode 703Easy
Kth Largest Element in a Stream
Keep a min-heap of size k; its top is the k-th largest. Each add costs O(log k).
Show the Python solution
class KthLargest: def __init__(self, k, nums): self.k, self.heap = k, [] for x in nums: self.add(x) def add(self, x): heappush(self.heap, x) if len(self.heap) > self.k: heappop(self.heap) # weakest of the top k leaves return self.heap[0] # the k-th largest so far - LeetCode 1046Easy
Last Stone Weight
A max-heap hands over the two largest in O(log n) each; repeat until at most one rock remains.
Show the Python solution
def last_stone_weight(stones): heap = [-s for s in stones] # max-heap via negatives heapify(heap) while len(heap) > 1: a = -heappop(heap) # heaviest b = -heappop(heap) # second heaviest if a != b: heappush(heap, -(a - b)) # what’s left of the bigger rock return -heap[0] if heap else 0 - LeetCode 973Medium
K Closest Points to Origin
Compare squared distances; keep a max-heap of size k (or heapify and pop k). O(n log k).
Show the Python solution
def k_closest(points, k): heap = [] # max-heap of the k closest (negated) for x, y in points: d = x * x + y * y heappush(heap, (-d, x, y)) if len(heap) > k: heappop(heap) # drop the farthest return [[x, y] for _, x, y in heap] - LeetCode 215Medium
Kth Largest Element in an Array
Min-heap of size k: the top is the answer. O(n log k).
Show the Python solution
def find_kth_largest(nums, k): heap = [] # min-heap of the k largest so far for x in nums: heappush(heap, x) if len(heap) > k: heappop(heap) # the weakest leaves return heap[0] - LeetCode 621Medium
Task Scheduler
Greedy: always run the most frequent available task; a queue holds tasks in cooldown. (Formula version: (maxCount − 1) × (n + 1) + number of tasks with maxCount.)
Show the Python solution
def least_interval(tasks, n): heap = [-c for c in Counter(tasks).values()] heapify(heap) cooling, time = deque(), 0 # (count left, ready time) while heap or cooling: time += 1 if heap: c = heappop(heap) + 1 # do the most-needed task if c: cooling.append((c, time + n)) if cooling and cooling[0][1] == time: heappush(heap, cooling.popleft()[0]) return time - LeetCode 355Medium
Design Twitter
Merge k sorted lists with a heap, stopping after 10 posts. Follow sets are hash sets.
Show the Python solution
class Twitter: def __init__(self): self.time = 0 self.posts = defaultdict(list) # user -> [(time, id)] self.follows = defaultdict(set) def postTweet(self, user, tweet): self.time += 1 self.posts[user].append((self.time, tweet)) def getNewsFeed(self, user): people = self.follows[user] | {user} heap = [(-t, id) for p in people for t, id in self.posts[p][-10:]] return [id for _, id in nsmallest(10, heap)] # newest first def follow(self, a, b): self.follows[a].add(b) def unfollow(self, a, b): self.follows[a].discard(b) - LeetCode 295Hard
Find Median from Data Stream
Two heaps split the data into halves; rebalance after each insert. Add O(log n), median O(1).
Show the Python solution
class MedianFinder: def __init__(self): self.low, self.high = [], [] # max-heap (negated), min-heap def add_num(self, x): heappush(self.low, -x) heappush(self.high, -heappop(self.low)) if len(self.high) > len(self.low): heappush(self.low, -heappop(self.high)) def find_median(self): if len(self.low) > len(self.high): return -self.low[0] return (-self.low[0] + self.high[0]) / 2
Backtracking ·
- LeetCode 78Medium
Subsets
Backtracking: at each index branch “include” and “exclude”. 2ⁿ subsets.
Show the Python solution
def subsets(nums): res, pick = [], [] def dfs(i): if i == len(nums): res.append(pick[:]) # a finished pizza return pick.append(nums[i]) # take topping i dfs(i + 1) pick.pop() # leave topping i dfs(i + 1) dfs(0) return res - LeetCode 39Medium
Combination Sum
Backtracking with a start index (to avoid reorderings) and reuse allowed: recurse with the same index after choosing a coin.
Show the Python solution
def combination_sum(coins, target): coins.sort(); res = [] def dfs(start, left, path): if left == 0: res.append(path[:]); return for i in range(start, len(coins)): if coins[i] > left: break # too big, and so is everything after dfs(i, left - coins[i], path + [coins[i]]) # same coin may repeat dfs(0, target, []) return res - LeetCode 46Medium
Permutations
Backtracking with a “used” set: choose, recurse, un-choose. n! orderings.
Show the Python solution
def permute(nums): res, seat = [], [] def dfs(): if len(seat) == len(nums): res.append(seat[:]); return for x in nums: if x not in seat: # guest still standing seat.append(x) dfs() seat.pop() # stand up again, try someone else dfs() return res - LeetCode 90Medium
Subsets II
Sort, then skip nums[i] when i > start and nums[i] == nums[i−1]. This removes duplicate branches.
Show the Python solution
def subsets_with_dup(nums): nums.sort(); res = [] def dfs(start, pick): res.append(pick[:]) for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: continue # same topping, same branch: skip dfs(i + 1, pick + [nums[i]]) dfs(0, []) return res - LeetCode 40Medium
Combination Sum II
Sort + backtracking moving to i + 1 (no reuse) + skip equal neighbours at the same level.
Show the Python solution
def combination_sum2(coins, target): coins.sort(); res = [] def dfs(start, left, path): if left == 0: res.append(path[:]); return for i in range(start, len(coins)): if i > start and coins[i] == coins[i - 1]: continue # same value at this level: skip if coins[i] > left: break dfs(i + 1, left - coins[i], path + [coins[i]]) # each coin once dfs(0, target, []) return res - LeetCode 79Medium
Word Search
Depth-first search with backtracking: mark, explore 4 neighbours, unmark. Stop as soon as the whole word is matched.
Show the Python solution
def exist(board, word): R, C = len(board), len(board[0]) def dfs(r, c, i): if i == len(word): return True if not (0 <= r < R and 0 <= c < C): return False if board[r][c] != word[i]: return False board[r][c] = "#" # mark: in use found = any(dfs(r+dr, c+dc, i+1) for dr, dc in DIRS) board[r][c] = word[i] # unmark return found return any(dfs(r, c, 0) for r in range(R) for c in range(C)) DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)] - LeetCode 131Medium
Palindrome Partitioning
Backtracking: try every end position for the next piece, recurse only if that piece is a palindrome.
Show the Python solution
def partition(s): out, parts = [], [] def cut(start): if start == len(s): out.append(parts[:]) return for end in range(start + 1, len(s) + 1): piece = s[start:end] if piece == piece[::-1]: parts.append(piece) cut(end) parts.pop() cut(0) return out - LeetCode 17Medium
Letter Combinations of a Phone Number
Backtracking over digits; at each level loop over that digit’s letters. 3ⁿ–4ⁿ results.
Show the Python solution
KEYS = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"} def letter_combinations(digits): res = [] def dfs(i, word): if i == len(digits): res.append(word); return for ch in KEYS[digits[i]]: dfs(i + 1, word + ch) if digits: dfs(0, "") return res - LeetCode 51Hard
N-Queens
Backtrack row by row; three sets (columns, r−c diagonals, r+c diagonals) make each safety check O(1).
Show the Python solution
def solve_n_queens(n): cols, d1, d2, res, board = set(), set(), set(), [], [] def place(r): if r == n: res.append(["." * c + "Q" + "." * (n - c - 1) for c in board]); return for c in range(n): if c in cols or r - c in d1 or r + c in d2: continue # attacked: skip this square cols.add(c); d1.add(r - c); d2.add(r + c); board.append(c) place(r + 1) cols.remove(c); d1.remove(r - c); d2.remove(r + c); board.pop() place(0) return res
Graphs ·
- LeetCode 200Medium
Number of Islands
For each unvisited land cell: count + 1, then DFS/BFS to mark its whole island. O(rows × cols).
Show the Python solution
def num_islands(grid): count = 0 for r in range(len(grid)): for c in range(len(grid[0])): if grid[r][c] == "1": count += 1 flood(grid, r, c) return count def flood(grid, r, c): q = deque([(r, c)]); grid[r][c] = "0" while q: r, c = q.popleft() for nr, nc in nbrs(grid, r, c): if grid[nr][nc] == "1": grid[nr][nc] = "0" q.append((nr, nc)) def nbrs(g, r, c): # in-grid neighbours R, C = len(g), len(g[0]) for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)): if 0 <= nr < R and 0 <= nc < C: yield nr, nc - LeetCode 133Medium
Clone Graph
BFS/DFS with an old→new dictionary so each node is copied once and cycles don’t loop forever. O(V + E).
Show the Python solution
def clone_graph(node): if not node: return None copies = {node: Node(node.val)} q = deque([node]) while q: cur = q.popleft() for nb in cur.neighbors: if nb not in copies: copies[nb] = Node(nb.val) q.append(nb) copies[cur].neighbors.append(copies[nb]) return copies[node] - LeetCode 695Medium
Max Area of Island
Flood fill each island, returning its size. O(rows × cols).
Show the Python solution
def max_area(grid): best = 0 for r, c in all_cells(grid): if grid[r][c] == 1: size = flood(grid, r, c) best = max(best, size) return best def flood(grid, r, c): # paint, count q, size = deque([(r, c)]), 1 grid[r][c] = 0 while q: r, c = q.popleft() for nr, nc in nbrs(grid, r, c): if grid[nr][nc] == 1: grid[nr][nc] = 0 size += 1 q.append((nr, nc)) return size def all_cells(g): return [(r, c) for r in range(len(g)) for c in range(len(g[0]))] def nbrs(g, r, c): # in-grid neighbours R, C = len(g), len(g[0]) for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)): if 0 <= nr < R and 0 <= nc < C: yield nr, nc - LeetCode 417Medium
Pacific Atlantic Water Flow
Reverse the flow: BFS/DFS uphill from each ocean’s border, then intersect. O(rows × cols).
Show the Python solution
def pacific_atlantic(h): R, C = len(h), len(h[0]) def climb(starts): # walk uphill seen, q = set(starts), deque(starts) while q: r, c = q.popleft() for nr, nc in nbrs(h, r, c): if (nr, nc) in seen: continue if h[nr][nc] >= h[r][c]: seen.add((nr, nc)) q.append((nr, nc)) return seen top = [(0, c) for c in range(C)] left = [(r, 0) for r in range(R)] bot = [(R - 1, c) for c in range(C)] right = [(r, C - 1) for r in range(R)] pac = climb(top + left) atl = climb(bot + right) return sorted(pac & atl) def nbrs(g, r, c): # in-grid neighbours R, C = len(g), len(g[0]) for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)): if 0 <= nr < R and 0 <= nc < C: yield nr, nc - LeetCode 130Medium
Surrounded Regions
Flood fill from border O cells to mark the survivors, then flip the rest. O(rows × cols).
Show the Python solution
def solve(board): R, C = len(board), len(board[0]) q = deque() # edge cells for r, c in all_cells(board): if r in (0, R-1) or c in (0, C-1): q.append((r, c)) while q: # edge-linked: safe r, c = q.popleft() if board[r][c] == "O": board[r][c] = "S" q.extend(nbrs(board, r, c)) for r, c in all_cells(board): if board[r][c] == "O": board[r][c] = "X" # captured if board[r][c] == "S": board[r][c] = "O" def all_cells(g): return [(r, c) for r in range(len(g)) for c in range(len(g[0]))] def nbrs(g, r, c): # in-grid neighbours R, C = len(g), len(g[0]) for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)): if 0 <= nr < R and 0 <= nc < C: yield nr, nc - LeetCode 994Medium
Rotting Oranges
Multi-source BFS: all starting points enter the queue at once, and each level is one minute. O(rows × cols).
Show the Python solution
def oranges_rotting(grid): q, fresh = deque(), 0 for r, c in all_cells(grid): if grid[r][c] == 2: q.append((r, c)) if grid[r][c] == 1: fresh += 1 minutes = 0 while q and fresh: for _ in range(len(q)): r, c = q.popleft() for nr, nc in nbrs(grid, r, c): if grid[nr][nc] == 1: grid[nr][nc] = 2 fresh -= 1 q.append((nr, nc)) minutes += 1 return minutes if fresh == 0 else -1 def all_cells(g): return [(r, c) for r in range(len(g)) for c in range(len(g[0]))] def nbrs(g, r, c): # in-grid neighbours R, C = len(g), len(g[0]) for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)): if 0 <= nr < R and 0 <= nc < C: yield nr, nc - LeetCode 286Medium
Walls and Gates
Multi-source BFS from all gates; first arrival = shortest distance. O(rows × cols).
Show the Python solution
def walls_and_gates(rooms): q = deque() for r, c in all_cells(rooms): if rooms[r][c] == 0: # a gate q.append((r, c)) while q: # gates spread together r, c = q.popleft() d = rooms[r][c] + 1 for nr, nc in nbrs(rooms, r, c): if rooms[nr][nc] == INF: rooms[nr][nc] = d q.append((nr, nc)) INF = 2**31 - 1 # empty room def all_cells(g): return [(r, c) for r in range(len(g)) for c in range(len(g[0]))] def nbrs(g, r, c): # in-grid neighbours R, C = len(g), len(g[0]) for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)): if 0 <= nr < R and 0 <= nc < C: yield nr, nc - LeetCode 207Medium
Course Schedule
Kahn’s topological sort: count incoming arrows, repeatedly take courses with count 0. All taken ⇔ no cycle.
Show the Python solution
def can_finish(n, prerequisites): indeg = [0] * n; nxt = defaultdict(list) for course, need in prerequisites: nxt[need].append(course); indeg[course] += 1 q = deque(c for c in range(n) if indeg[c] == 0) taken = [] while q: c = q.popleft() taken.append(c) for d in nxt[c]: indeg[d] -= 1 if indeg[d] == 0: q.append(d) return len(taken) == n - LeetCode 210Medium
Course Schedule II
Topological order from Kahn’s algorithm; length < n means a cycle.
Show the Python solution
def find_order(n, prerequisites): indeg = [0] * n; nxt = defaultdict(list) for course, need in prerequisites: nxt[need].append(course); indeg[course] += 1 q = deque(c for c in range(n) if indeg[c] == 0) taken = [] while q: c = q.popleft() taken.append(c) for d in nxt[c]: indeg[d] -= 1 if indeg[d] == 0: q.append(d) return taken if len(taken) == n else [] - LeetCode 684Medium
Redundant Connection
Union-find: for each edge, if find(a) == find(b) it is the extra edge; otherwise union them.
Show the Python solution
def find_redundant(edges): n = len(edges) + 1 parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x for a, b in edges: ra, rb = find(a), find(b) if ra == rb: return [a, b] # closes a loop parent[rb] = ra - LeetCode 323Medium
Number of Connected Components in an Undirected Graph
Union-find: components = n − (number of successful unions).
Show the Python solution
def count_components(n, edges): parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x groups = n for a, b in edges: ra, rb = find(a), find(b) if ra != rb: parent[rb] = ra groups -= 1 return groups - LeetCode 261Medium
Graph Valid Tree
A tree ⇔ exactly n − 1 edges and no union fails (no cycle).
Show the Python solution
def valid_tree(n, edges): if len(edges) != n - 1: return False parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x for a, b in edges: ra, rb = find(a), find(b) if ra == rb: return False # a loop parent[rb] = ra # union return True # n-1 edges, no loop - LeetCode 127Hard
Word Ladder
BFS over words (neighbours = one-letter changes found in the dictionary). The first time you reach the end word is the shortest.
Show the Python solution
def ladder_length(begin, end, words): words, q, steps = set(words), deque([begin]), 1 while q: for _ in range(len(q)): w = q.popleft() if w == end: return steps for i in range(len(w)): for ch in "abcdefghijklmnopqrstuvwxyz": nxt = w[:i] + ch + w[i + 1:] if nxt in words: words.remove(nxt); q.append(nxt) steps += 1 return 0
Advanced Graphs ·
- LeetCode 332Hard
Reconstruct Itinerary
Hierholzer’s algorithm for an Eulerian path: DFS with sorted tickets, append a node when stuck, reverse at the end.
Show the Python solution
def find_itinerary(tickets): out = defaultdict(list) for a, b in sorted(tickets, reverse=True): out[a].append(b) # pop() gives the smallest route = [] def fly(airport): while out[airport]: fly(out[airport].pop()) # use a ticket route.append(airport) # stuck here: finalise this stop fly("JFK") return route[::-1] - LeetCode 1584Medium
Min Cost to Connect All Points
Prim’s algorithm for a minimum spanning tree: grow from one point, always taking the cheapest edge to a new point.
Show the Python solution
def min_cost_connect(points): n, done, cost = len(points), set(), 0 heap = [(0, 0)] # (cable length, house) while len(done) < n: d, i = heappop(heap) if i in done: continue done.add(i); cost += d for j in range(n): if j not in done: dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]) heappush(heap, (dist, j)) return cost - LeetCode 743Medium
Dijkstra
Dijkstra: a min-heap of (time, junction); pop the closest, relax its roads. Works when no road has negative time.
Show the Python solution
def network_delay_time(times, n, k): roads = defaultdict(list) for u, v, w in times: # one-way roads[u].append((v, w)) dist = {k: 0} pq = [(0, k)] while pq: d, u = heappop(pq) # closest if d > dist[u]: continue for v, w in roads[u]: if d + w < dist.get(v, inf): dist[v] = d + w heappush(pq, (dist[v], v)) if len(dist) < n: return -1 # someone never hears return max(dist.values()) - LeetCode 778Hard
Swim in Rising Water
Dijkstra-style search where a path’s cost is its maximum height, not its sum.
Show the Python solution
def swim_in_water(grid): n = len(grid) heap = [(grid[0][0], 0, 0)] seen = {(0, 0)} while heap: t, r, c = heappop(heap) # lowest if (r, c) == (n - 1, n - 1): return t for nr, nc in nbrs(grid, r, c): if (nr, nc) not in seen: seen.add((nr, nc)) tt = max(t, grid[nr][nc]) heappush(heap, (tt, nr, nc)) def nbrs(g, r, c): # in-grid neighbours R, C = len(g), len(g[0]) for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)): if 0 <= nr < R and 0 <= nc < C: yield nr, nc - LeetCode 269Hard
Alien Dictionary
Build “a before b” edges from adjacent words, then topologically sort. A cycle (or a longer word before its own prefix) means invalid.
Show the Python solution
def alien_order(words): after = {ch: set() for w in words for ch in w} for a, b in zip(words, words[1:]): for x, y in zip(a, b): if x != y: after[x].add(y) # x comes before y break else: if len(a) > len(b): return "" # "abc" before "ab" is impossible indeg = {ch: 0 for ch in after} for x in after: for y in after[x]: indeg[y] += 1 q = deque(ch for ch in after if indeg[ch] == 0) order = "" while q: ch = q.popleft(); order += ch for y in after[ch]: indeg[y] -= 1 if indeg[y] == 0: q.append(y) return order if len(order) == len(after) else "" - LeetCode 787Medium
Cheapest Flights Within K Stops
Bellman–Ford limited to k + 1 rounds, using last round’s prices (a copy) for each relaxation.
Show the Python solution
def find_cheapest_price(n, flights, src, dst, k): price = [inf] * n price[src] = 0 for _ in range(k + 1): # at most k stops = k+1 flights nxt = price[:] # only build on last round’s prices for a, b, cost in flights: if price[a] + cost < nxt[b]: nxt[b] = price[a] + cost price = nxt return -1 if price[dst] == inf else price[dst]
1-D DP ·
- LeetCode 70Easy
Climbing Stairs
ways[i] = ways[i − 1] + ways[i − 2]: the Fibonacci pattern. Only the last two numbers are needed. O(n).
Show the Python solution
def climb(n): ways = [1, 1] + [0] * (n - 1) for i in range(2, n + 1): ways[i] = ways[i - 1] + ways[i - 2] return ways[n] - LeetCode 746Easy
Min Cost Climbing Stairs
best[i] = min(best[i − 1] + cost[i − 1], best[i − 2] + cost[i − 2]). O(n).
Show the Python solution
def min_cost_climbing_stairs(cost): n = len(cost) best = [0] * (n + 1) # cheapest way to stand on step i for i in range(2, n + 1): best[i] = min(best[i - 1] + cost[i - 1], # one step from i-1 best[i - 2] + cost[i - 2]) # or two from i-2 return best[n] # the top is just past the last step - LeetCode 198Medium
House Robber
best[i] = max(best[i − 1], best[i − 2] + money[i]). O(n), O(1) memory.
Show the Python solution
def rob(houses): skip, take = 0, 0 # best total if the last house was skipped / robbed for loot in houses: skip, take = max(skip, take), skip + loot return max(skip, take) - LeetCode 213Medium
House Robber II
answer = max(rob(houses[1:]), rob(houses[:-1])). Two linear passes.
Show the Python solution
def rob_circle(houses): if len(houses) == 1: return houses[0] def rob_line(hs): skip, take = 0, 0 for loot in hs: skip, take = max(skip, take), skip + loot return max(skip, take) return max(rob_line(houses[1:]), # leave the first house alone rob_line(houses[:-1])) # or leave the last one - LeetCode 5Medium
Longest Palindromic Substring
Expand around 2n − 1 centres. O(n²) time, O(1) memory.
Show the Python solution
def longest_palindrome(s): best = "" for c in range(len(s)): for l, r in ((c, c), (c, c + 1)): # odd, even while l >= 0 and r < len(s) and s[l] == s[r]: l, r = l - 1, r + 1 if r - l - 1 > len(best): best = s[l + 1:r] return best - LeetCode 647Medium
Palindromic Substrings
Expand around every centre and count each successful step. O(n²).
Show the Python solution
def count_substrings(s): count = 0 for c in range(len(s)): for l, r in ((c, c), (c, c + 1)): # odd and even centres while l >= 0 and r < len(s) and s[l] == s[r]: count += 1 l, r = l - 1, r + 1 return count - LeetCode 91Medium
Decode Ways
ways[i] = (ways[i − 1] if s[i−1] ≠ 0) + (ways[i − 2] if 10 ≤ s[i−2:i] ≤ 26). O(n).
Show the Python solution
def num_decodings(s): # 1 = A … 26 = Z ways = [1] + [0] * len(s) # ways[i]: ways to read the first i digits for i in range(1, len(s) + 1): if s[i - 1] != "0": ways[i] += ways[i - 1] # read one digit if i > 1 and 10 <= int(s[i - 2:i]) <= 26: ways[i] += ways[i - 2] # read two digits return ways[len(s)] - LeetCode 322Medium
Coin Change
best[x] = 1 + min(best[x − c]) over coins c. O(amount × coins).
Show the Python solution
def coin_change(coins, amount): fewest = [0] + [inf] * amount for a in range(1, amount + 1): for c in coins: if c <= a: n = fewest[a - c] + 1 fewest[a] = min(fewest[a], n) best = fewest[amount] return -1 if best == inf else best - LeetCode 152Medium
Maximum Product Subarray
Track both max and min product ending at i; cur_max = max(x, x·prev_max, x·prev_min). O(n).
Show the Python solution
def max_product(nums): hi = lo = best = nums[0] for x in nums[1:]: if x < 0: hi, lo = lo, hi # a negative swaps big and small hi = max(x, hi * x) lo = min(x, lo * x) best = max(best, hi) return best - LeetCode 139Medium
Word Break
ok[i] is True if some word w ends at position i and ok[i − len(w)] is True. This loop tries all W words at each of the n positions, comparing up to L letters each time: O(n · W · L). (The other common version tries every split point j < i and looks s[j:i] up in a set: O(n²) substring checks, each costing up to O(L) once pieces longer than the longest word L are skipped, so O(n² · L) at most.)
Show the Python solution
def word_break(s, words): ok = [True] + [False] * len(s) # s[:i]? for i in range(1, len(s) + 1): for w in words: j = i - len(w) # w = s[j:i]? if j >= 0 and ok[j] and s[j:i] == w: ok[i] = True break return ok[len(s)] - LeetCode 300Medium
Longest Increasing Subsequence
Patience sorting: keep pile tops (always sorted) and binary search where each card goes. O(n log n).
Show the Python solution
def length_of_lis(nums): piles = [] # top card of each pile, increasing for x in nums: i = bisect_left(piles, x) # leftmost pile whose top is >= x if i == len(piles): piles.append(x) # bigger than every top: new pile else: piles[i] = x # place it on that pile return len(piles) - LeetCode 416Medium
Partition Equal Subset Sum
Subset-sum: a set (or boolean row) of reachable sums, updated per weight. O(n × total/2).
Show the Python solution
def can_partition(nums): total = sum(nums) if total % 2: return False half = total // 2 reach = {0} # sums one pan can hold so far for x in nums: reach |= {r + x for r in reach if r + x <= half} return half in reach
2-D DP ·
- LeetCode 62Medium
Unique Paths
paths[r][c] = paths[r − 1][c] + paths[r][c − 1]. Fill in row order. O(m × n).
Show the Python solution
def unique_paths(m, n): ways = [[1] * n for _ in range(m)] # first row and column: one way for r in range(1, m): for c in range(1, n): ways[r][c] = ways[r - 1][c] + ways[r][c - 1] # from above + from the left return ways[m - 1][n - 1] - LeetCode 1143Medium
Longest Common Subsequence
dp[i][j] = dp[i−1][j−1] + 1 if A[i] == B[j], else max(dp[i−1][j], dp[i][j−1]). O(m × n).
Show the Python solution
def lcs(a, b): t = [[0] * (len(b) + 1) for _ in range(len(a) + 1)] for i in range(1, len(a) + 1): for j in range(1, len(b) + 1): if a[i - 1] == b[j - 1]: t[i][j] = t[i - 1][j - 1] + 1 # letters pair up else: t[i][j] = max(t[i - 1][j], t[i][j - 1]) return t[len(a)][len(b)] - LeetCode 309Medium
Best Time to Buy and Sell Stock with Cooldown
State machine DP: hold = max(hold, rest − price); sold = hold + price; rest = max(rest, sold). O(n).
Show the Python solution
def max_profit(prices): hold, sold, rest = -inf, 0, 0 for p in prices: hold, sold, rest = (max(hold, rest - p), # keep, or buy (only after resting) hold + p, # sell today max(rest, sold)) # do nothing (cooldown ends) return max(sold, rest) - LeetCode 518Medium
Coin Change II
ways[x] += ways[x − c], looping coins on the outside and amounts on the inside. O(amount × coins).
Show the Python solution
def change(amount, coins): ways = [1] + [0] * amount for c in coins: # one coin type at a time: no reorderings for a in range(c, amount + 1): ways[a] += ways[a - c] return ways[amount] - LeetCode 494Medium
Target Sum
DP over sums: a dictionary position → count, updated for each number with ±. O(n × range).
Show the Python solution
def find_target_sum_ways(nums, target): ways = {0: 1} # total -> number of sign choices for x in nums: nxt = defaultdict(int) for total, w in ways.items(): nxt[total + x] += w nxt[total - x] += w ways = nxt return ways.get(target, 0) - LeetCode 97Medium
Interleaving String
dp[i][j] = (dp[i−1][j] and A[i−1] == C[i+j−1]) or (dp[i][j−1] and B[j−1] == C[i+j−1]). O(m × n).
Show the Python solution
def is_interleave(a, b, c): if len(a) + len(b) != len(c): return False ok = [[False] * (len(b) + 1) for _ in range(len(a) + 1)] ok[0][0] = True for i in range(len(a) + 1): for j in range(len(b) + 1): k = i + j - 1 # next letter of c to explain if i and a[i - 1] == c[k] and ok[i - 1][j]: ok[i][j] = True if j and b[j - 1] == c[k] and ok[i][j - 1]: ok[i][j] = True return ok[len(a)][len(b)] - LeetCode 329Hard
Longest Increasing Path in a Matrix
DFS with memoisation; the strict increase rule means there are no cycles. O(rows × cols).
Show the Python solution
def longest_increasing_path(h): memo = {} def climb(r, c): # best hike from here if (r, c) not in memo: up = [0] for nr, nc in nbrs(h, r, c): if h[nr][nc] > h[r][c]: up.append(climb(nr, nc)) memo[(r, c)] = 1 + max(up) return memo[(r, c)] return max(climb(r, c) for r, c in all_cells(h)) def all_cells(g): return [(r, c) for r in range(len(g)) for c in range(len(g[0]))] def nbrs(g, r, c): # in-grid neighbours R, C = len(g), len(g[0]) for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)): if 0 <= nr < R and 0 <= nc < C: yield nr, nc - LeetCode 115Hard
Distinct Subsequences
dp[i][j] = dp[i−1][j] + (dp[i−1][j−1] if s[i−1] == t[j−1]). O(m × n).
Show the Python solution
def num_distinct(s, t): ways = [[0] * (len(t) + 1) for _ in range(len(s) + 1)] for i in range(len(s) + 1): ways[i][0] = 1 # empty t: cross out everything for i in range(1, len(s) + 1): for j in range(1, len(t) + 1): ways[i][j] = ways[i - 1][j] # skip s[i-1] if s[i - 1] == t[j - 1]: ways[i][j] += ways[i - 1][j - 1] # or use it return ways[len(s)][len(t)] - LeetCode 72Medium
Edit Distance
Classic edit distance DP. O(m × n).
Show the Python solution
def min_distance(a, b): d = [[0] * (len(b) + 1) for _ in range(len(a) + 1)] for i in range(len(a) + 1): d[i][0] = i # delete everything for j in range(len(b) + 1): d[0][j] = j # type everything for i in range(1, len(a) + 1): for j in range(1, len(b) + 1): if a[i - 1] == b[j - 1]: d[i][j] = d[i - 1][j - 1] # letters already agree else: d[i][j] = 1 + min(d[i - 1][j], # delete d[i][j - 1], # insert d[i - 1][j - 1]) # replace return d[len(a)][len(b)] - LeetCode 312Hard
Burst Balloons
Interval DP: dp[l][r] = max over k of dp[l][k] + dp[k][r] + v[l]·v[k]·v[r]. O(n³).
Show the Python solution
def max_coins(nums): b = [1] + nums + [1] # imaginary 1-balloons at the ends n = len(b) best = [[0] * n for _ in range(n)] # best[l][r]: pop everything strictly between for gap in range(2, n): for l in range(n - gap): r = l + gap for k in range(l + 1, r): # k is the LAST balloon popped in (l, r) best[l][r] = max(best[l][r], best[l][k] + b[l] * b[k] * b[r] + best[k][r]) return best[0][n - 1] - LeetCode 10Hard
Regular Expression Matching
dp over (text prefix, pattern prefix); handle “*” as zero uses (j − 2) or one more use (i − 1). O(m × n).
Show the Python solution
def is_match(s, p): m, n = len(s), len(p) ok = [[False] * (n + 1) for _ in range(m + 1)] ok[0][0] = True for i in range(m + 1): for j in range(1, n + 1): if p[j - 1] == "*": # x* : zero copies, or one more ok[i][j] = ok[i][j - 2] or (i > 0 and p[j - 2] in (s[i - 1], ".") and ok[i - 1][j]) elif i > 0 and p[j - 1] in (s[i - 1], "."): ok[i][j] = ok[i - 1][j - 1] return ok[m][n]
Greedy ·
- LeetCode 53Medium
Maximum Subarray (Kadane)
Kadane: cur = max(x, cur + x); best = max(best, cur). O(n).
Show the Python solution
def max_subarray(days): cur = best = days[0] for x in days[1:]: cur = max(x, cur + x) # keep the streak or start fresh best = max(best, cur) return best - LeetCode 55Medium
Jump Game
Greedy: reach = max(reach, i + nums[i]); fail if i > reach. O(n).
Show the Python solution
def can_jump(pads): reach = 0 for i, jump in enumerate(pads): if i > reach: return False # this pad can never be reached reach = max(reach, i + jump) return True - LeetCode 45Medium
Jump Game II
BFS by ranges: when i reaches the end of the current wave, jumps += 1 and the wave end becomes the farthest reach. O(n).
Show the Python solution
def jump(pads): hops, end, far = 0, 0, 0 for i in range(len(pads) - 1): far = max(far, i + pads[i]) # best reach from this wave if i == end: # finished the current wave hops += 1 end = far return hops - LeetCode 134Medium
Gas Station
One pass: reset the start to i + 1 whenever the running tank drops below 0. O(n).
Show the Python solution
def can_complete_circuit(gas, cost): if sum(gas) < sum(cost): return -1 # not enough fuel in total tank, start = 0, 0 for i in range(len(gas)): tank += gas[i] - cost[i] if tank < 0: # ran dry: no start up to i works start, tank = i + 1, 0 return start - LeetCode 846Medium
Hand of Straights
Count cards; always start a run at the smallest remaining value and consume the following values. O(n log n).
Show the Python solution
def is_n_straight_hand(hand, size): count = Counter(hand) for start in sorted(count): need = count[start] # runs that must start at this card if need: for v in range(start, start + size): if count[v] < need: return False count[v] -= need return True - LeetCode 1899Medium
Merge Triplets to Form Target Triplet
Ignore triplets exceeding the target anywhere; the rest must cover each target value. O(n).
Show the Python solution
def merge_triplets(triplets, target): got = set() for t in triplets: if any(t[i] > target[i] for i in range(3)): continue # would overshoot: never use it for i in range(3): if t[i] == target[i]: got.add(i) # this pot supplies slot i exactly return len(got) == 3 - LeetCode 763Medium
Partition Labels
end = max(end, last[c]); cut when i == end. O(n).
Show the Python solution
def partition_labels(s): last = {ch: i for i, ch in enumerate(s)} sizes, start, end = [], 0, 0 for i, ch in enumerate(s): end = max(end, last[ch]) # this piece must reach ch’s last copy if i == end: sizes.append(end - start + 1) # safe to cut here start = i + 1 return sizes - LeetCode 678Medium
Valid Parenthesis String
Greedy with (lo, hi) open-count bounds. O(n), O(1) memory.
Show the Python solution
def check_valid_string(s): lo = hi = 0 # range of possible open brackets for ch in s: if ch == "(": lo, hi = lo + 1, hi + 1 elif ch == ")": lo, hi = lo - 1, hi - 1 else: lo, hi = lo - 1, hi + 1 # * could be ), nothing, or ( if hi < 0: return False # too many ) whatever the stars are lo = max(lo, 0) return lo == 0
Intervals ·
- LeetCode 57Medium
Insert Interval
Three phases: before, overlapping (merge), after. O(n).
Show the Python solution
def insert(intervals, new): out, i, n = [], 0, len(intervals) while i < n and intervals[i][1] < new[0]: out.append(intervals[i]); i += 1 # ends before: keep while i < n and intervals[i][0] <= new[1]: new = [min(new[0], intervals[i][0]), # overlaps: absorb it max(new[1], intervals[i][1])] i += 1 out.append(new) out.extend(intervals[i:]) # starts after: keep return out - LeetCode 56Medium
Merge Intervals
Sort by start, then extend or start a new block. O(n log n).
Show the Python solution
def merge(intervals): intervals.sort() out = [intervals[0]] for start, end in intervals[1:]: if start <= out[-1][1]: out[-1][1] = max(out[-1][1], end) # overlaps: stretch the block else: out.append([start, end]) # gap: a new block return out - LeetCode 435Medium
Non-overlapping Intervals
Greedy by earliest end; count clashes. O(n log n).
Show the Python solution
def erase_overlap_intervals(intervals): intervals.sort(key=lambda x: x[1]) # earliest finish first removed, free_at = 0, -inf for start, end in intervals: if start >= free_at: free_at = end # keep it else: removed += 1 # clashes with a kept booking return removed - LeetCode 252Easy
Meeting Rooms
Sort by start and compare each start with the previous end. O(n log n).
Show the Python solution
def can_attend_meetings(intervals): intervals.sort() for i in range(1, len(intervals)): if intervals[i][0] < intervals[i - 1][1]: return False # starts before the last one ends return True - LeetCode 253Medium
Meeting Rooms II
Sort by start + min-heap of end times. O(n log n).
Show the Python solution
def min_meeting_rooms(intervals): intervals.sort() ends = [] # min-heap of when each room frees up for start, end in intervals: if ends and ends[0] <= start: heappop(ends) # reuse the room that frees first heappush(ends, end) return len(ends) - LeetCode 1851Hard
Minimum Interval to Include Each Query
Sort intervals and queries; min-heap by size, discarding expired intervals. O(n log n + q log q).
Show the Python solution
def min_interval(intervals, queries): intervals.sort() heap, ans, i = [], {}, 0 # heap of (length, end) for q in sorted(queries): while i < len(intervals) and intervals[i][0] <= q: a, b = intervals[i] heappush(heap, (b - a + 1, b)); i += 1 # started by now while heap and heap[0][1] < q: heappop(heap) # already over ans[q] = heap[0][0] if heap else -1 return [ans[q] for q in queries]
Math & Geometry ·
- LeetCode 48Medium
Rotate Image
Transpose, then reverse each row. O(n²), O(1) extra space.
Show the Python solution
def rotate(m): n = len(m) for i in range(n): for j in range(i + 1, n): m[i][j], m[j][i] = m[j][i], m[i][j] # flip over the diagonal for row in m: row.reverse() # then mirror left-right - LeetCode 54Medium
Spiral Matrix
Four boundaries that shrink after each side. O(rows × cols).
Show the Python solution
def spiral_order(m): out = [] top, bottom, left, right = 0, len(m) - 1, 0, len(m[0]) - 1 while top <= bottom and left <= right: for c in range(left, right + 1): out.append(m[top][c]) top += 1 for r in range(top, bottom + 1): out.append(m[r][right]) right -= 1 if top <= bottom: for c in range(right, left - 1, -1): out.append(m[bottom][c]) bottom -= 1 if left <= right: for r in range(bottom, top - 1, -1): out.append(m[r][left]) left += 1 return out - LeetCode 73Medium
Set Matrix Zeroes
Record zero rows/columns first (or use the first row and column as markers), then apply. O(rows × cols).
Show the Python solution
def set_zeroes(m): rows, cols = set(), set() for r in range(len(m)): for c in range(len(m[0])): if m[r][c] == 0: rows.add(r); cols.add(c) # remember first, change later for r in range(len(m)): for c in range(len(m[0])): if r in rows or c in cols: m[r][c] = 0 - LeetCode 202Easy
Happy Number
Detect a cycle with a set (or fast/slow pointers). Numbers shrink quickly, so it’s fast.
Show the Python solution
def is_happy(n): seen = set() while n != 1 and n not in seen: seen.add(n) n = sum(int(d) ** 2 for d in str(n)) return n == 1 - LeetCode 66Easy
Plus One
Walk from the right, turning 9s into 0s until a digit can be incremented. O(n).
Show the Python solution
def plus_one(digits): for i in range(len(digits) - 1, -1, -1): if digits[i] < 9: digits[i] += 1 return digits digits[i] = 0 # 9 rolls over to 0, carry on return [1] + digits - LeetCode 50Medium
Pow(x, n)
Fast exponentiation by squaring: O(log n) multiplications.
Show the Python solution
def my_pow(x, n): if n < 0: x, n = 1 / x, -n result = 1 while n: if n & 1: result *= x # this power of two is in n x *= x # square: x, x², x⁴, x⁸ … n >>= 1 return result - LeetCode 43Medium
Multiply Strings
An array of n + m slots; add every digit product into slot i + j + 1 and carry. O(n × m).
Show the Python solution
def multiply(a, b): res = [0] * (len(a) + len(b)) for i in range(len(a) - 1, -1, -1): for j in range(len(b) - 1, -1, -1): p = int(a[i]) * int(b[j]) + res[i + j + 1] res[i + j + 1] = p % 10 # keep the ones digit res[i + j] += p // 10 # carry to the left s = "".join(map(str, res)).lstrip("0") return s or "0" - LeetCode 2013Medium
Detect Squares
Count points in a dictionary; for each diagonal candidate, multiply the counts of the other two corners.
Show the Python solution
class DetectSquares: def __init__(self): self.count = Counter() # (x, y) -> pegs there def add(self, p): self.count[tuple(p)] += 1 def count_squares(self, q): qx, qy = q total = 0 for (x, y), c in list(self.count.items()): if abs(x - qx) != abs(y - qy) or x == qx: continue # not a diagonal corner total += c * self.count[(x, qy)] * self.count[(qx, y)] return total
Bit Manipulation ·
- LeetCode 136Easy
Single Number
a ^ a = 0 and a ^ 0 = a, so XOR of everything is the single number. O(n), O(1).
Show the Python solution
def single_number(nums): acc = 0 for x in nums: acc ^= x # a pair flips a switch twice: back off return acc - LeetCode 191Easy
Number of 1 Bits
Repeat n &= n − 1, counting iterations: one step per 1 bit.
Show the Python solution
def hamming_weight(n): count = 0 while n: n &= n - 1 # switches off the lowest light count += 1 return count - LeetCode 338Easy
Counting Bits
bits[i] = bits[i >> 1] + (i & 1). O(n).
Show the Python solution
def count_bits(n): ans = [0] * (n + 1) for i in range(1, n + 1): ans[i] = ans[i >> 1] + (i & 1) # i = (i // 2) shifted, plus last bit return ans - LeetCode 190Easy
Reverse Bits
For each bit: result = (result << 1) | (n & 1); n >>= 1.
Show the Python solution
def reverse_bits(n, width=32): # this scene uses width = 8 out = 0 for _ in range(width): out = (out << 1) | (n & 1) # take n’s last switch n >>= 1 return out - LeetCode 268Easy
Missing Number
n(n + 1)/2 − sum(nums) (or XOR indices and values). O(n), O(1).
Show the Python solution
def missing_number(nums): n = len(nums) total = n * (n + 1) // 2 # roll call should add up to this for x in nums: total -= x return total - LeetCode 371Medium
Sum of Two Integers
sum = a ^ b, carry = (a & b) << 1; repeat until carry is 0. Python integers have no fixed width, so a negative number acts like endless 1-bits and the carry never dies out: mask every step with M = 0xFFFFFFFF to stay in 32 bits, and at the end turn a pattern with the top bit on back into a negative with ~(a ^ M).
Show the Python solution
def get_sum(a, b): M = 0xFFFFFFFF # 32 one-bits a, b = a & M, b & M # 32-bit view while b: carry = ((a & b) << 1) & M a = (a ^ b) & M # add, no carry b = carry if a > 0x7FFFFFFF: # top bit on: a = ~(a ^ M) # it is negative return a - LeetCode 7Medium
Reverse Integer
Pop and push digits with % and //, checking against 2³¹ − 1 before each push.
Show the Python solution
def reverse(x): sign = -1 if x < 0 else 1 x, out = abs(x), 0 while x: out = out * 10 + x % 10 # move the last digit over x //= 10 out *= sign return out if -2**31 <= out < 2**31 else 0