The Gauntlet: DSA

25 essential coding interview questions. Each question includes a full Python solution with step-by-step explanation and complexity analysis.

25Questions
9Topics
0Mastered
Progress0 / 25
01

Graphs

BFS/DFS, multi-source BFS, cycle detection, and flood-fill on graphs and grids.

Q01 Clone Graph — Deep-copy a graph that may contain cycles show ▾

Use BFS with a hash map from original node → clone. The map prevents revisiting nodes and stores the clone reference simultaneously.

Time: O(V + E)Space: O(V)

Key insight: The hash map does double duty — visited check AND original→clone mapping. Without it, cycles cause infinite recursion.

Practice on LeetCode →
Python Solution
from collections import deque def cloneGraph(node): if not node: return None clones = {node: Node(node.val)} # original → clone map queue = deque([node]) while queue: curr = queue.popleft() for neighbor in curr.neighbors: if neighbor not in clones: clones[neighbor] = Node(neighbor.val) queue.append(neighbor) clones[curr].neighbors.append(clones[neighbor]) return clones[node]
How it works: We seed the BFS with the input node and its clone. For each node we dequeue, we iterate over its neighbors. If a neighbor is new (not in clones), we create its clone and enqueue it. Either way, we append the neighbor's clone to the current node's clone's neighbor list. When BFS ends, every reachable node has been cloned with correct edges.
Q02 Course Schedule — Detect if a cycle exists in a directed graph show ▾

Build a directed prerequisite graph. Use Kahn's BFS topological sort — if all n nodes are processed, no cycle exists (can finish all courses).

Time: O(V + E)Space: O(V + E)

Key insight: If processed count == numCourses after BFS, no cycle. Any unprocessed node is part of a cycle.

Practice on LeetCode →
Python Solution
from collections import deque def canFinish(numCourses, prerequisites): in_degree = [0] * numCourses adj = [[] for _ in range(numCourses)] for course, pre in prerequisites: adj[pre].append(course) in_degree[course] += 1 # Start BFS with all nodes that have no prerequisites queue = deque(c for c in range(numCourses) if in_degree[c] == 0) processed = 0 while queue: node = queue.popleft() processed += 1 for neighbor in adj[node]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) return processed == numCourses
How it works: Kahn's algorithm repeatedly removes nodes with in-degree 0 (no pending prerequisites). Each removal decrements neighbors' in-degrees. If a neighbor's in-degree reaches 0, it becomes ready. If we process all n nodes, there's no cycle. If some remain, they form a cycle — their in-degrees never reach 0.
Q03 01 Matrix — Distance to nearest 0 for every cell show ▾

Seed a BFS queue with all 0-cells at once. Propagate distances outward — the first time BFS reaches a 1-cell is its shortest distance.

Time: O(m × n)Space: O(m × n)

Key insight: Multi-source BFS from all zeros simultaneously. BFS's layer-by-layer expansion guarantees the first visit = shortest path.

Practice on LeetCode →
Python Solution
from collections import deque def updateMatrix(mat): m, n = len(mat), len(mat[0]) dist = [[float('inf')] * n for _ in range(m)] queue = deque() # Seed: all 0-cells start at distance 0 for r in range(m): for c in range(n): if mat[r][c] == 0: dist[r][c] = 0 queue.append((r, c)) while queue: r, c = queue.popleft() for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nr, nc = r + dr, c + dc if 0 <= nr < m and 0 <= nc < n: if dist[r][c] + 1 < dist[nr][nc]: dist[nr][nc] = dist[r][c] + 1 queue.append((nr, nc)) return dist
How it works: All 0-cells are enqueued at distance 0. BFS expands layer by layer. When we reach neighbor (nr, nc), its distance is dist[r][c] + 1. Since BFS processes nodes in order of increasing distance, the first time we set dist[nr][nc] is optimal — we only update if we find a shorter path.
Q04 Number of Islands — Count connected land components show ▾

For each unvisited '1', increment the count and DFS to flood-fill the entire island, marking cells as visited.

Time: O(m × n)Space: O(m × n) stack

Key insight: Modify the grid in-place (set '1' → '0') as the visited marker. No extra space needed.

Practice on LeetCode →
Python Solution
def numIslands(grid): m, n = len(grid), len(grid[0]) count = 0 def dfs(r, c): # Out of bounds or already water/visited — stop if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != '1': return grid[r][c] = '0' # mark visited dfs(r+1, c); dfs(r-1, c) dfs(r, c+1); dfs(r, c-1) for r in range(m): for c in range(n): if grid[r][c] == '1': count += 1 dfs(r, c) # consume the entire island return count
How it works: We scan every cell. When we hit a '1', we found a new island — increment count, then call DFS to sink all connected land. DFS marks cells '0' in-place so they won't be counted again. After DFS returns, the entire island is consumed. We continue scanning for the next unvisited island.
Q05 Rotting Oranges — Minimum minutes for all oranges to rot show ▾

Multi-source BFS from all rotten oranges. Each BFS level = 1 minute. Track fresh count — if any fresh remain after BFS, return -1.

Time: O(m × n)Space: O(m × n)

Key insight: BFS models simultaneous spread — all sources expand in the same round. Count fresh oranges upfront and decrement during BFS.

Practice on LeetCode →
Python Solution
from collections import deque def orangesRotting(grid): m, n = len(grid), len(grid[0]) queue = deque() fresh = 0 for r in range(m): for c in range(n): if grid[r][c] == 2: queue.append((r, c, 0)) elif grid[r][c] == 1: fresh += 1 max_time = 0 while queue: r, c, t = queue.popleft() for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: nr, nc = r+dr, c+dc if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1: grid[nr][nc] = 2 # infect fresh -= 1 max_time = t + 1 queue.append((nr, nc, t + 1)) return max_time if fresh == 0 else -1
How it works: We seed BFS with all initially rotten oranges at time 0. Each time we infect a fresh orange, we enqueue it with time t + 1. We track max_time (the last infection timestamp) and fresh (decrement on each infection). If fresh == 0 after BFS, all oranges rotted — return max_time.
02

Arrays

Interval merging, two-pointer k-sum, prefix products, backtracking, and greedy overlap detection.

Q06 Insert Interval — Insert into sorted non-overlapping interval list show ▾

Single linear pass: collect intervals before the new one, merge all overlapping ones, then collect those after.

Time: O(n)Space: O(n)

Key insight: Three phases in one pass. Once the new interval is flushed, all remaining intervals are untouched — just extend with a slice.

Practice on LeetCode →
Python Solution
def insert(intervals, newInterval): result = [] i = 0 n = len(intervals) # Phase 1: intervals entirely before newInterval while i < n and intervals[i][1] < newInterval[0]: result.append(intervals[i]) i += 1 # Phase 2: merge all overlapping intervals while i < n and intervals[i][0] <= newInterval[1]: newInterval[0] = min(newInterval[0], intervals[i][0]) newInterval[1] = max(newInterval[1], intervals[i][1]) i += 1 result.append(newInterval) # Phase 3: intervals entirely after newInterval result.extend(intervals[i:]) return result
How it works: Phase 1 appends intervals whose end is before the new start (no overlap). Phase 2 merges all intervals whose start is ≤ the new end (overlap possible) by expanding the new interval's bounds. Phase 3 appends the rest unchanged. The three-phase structure handles all edge cases cleanly.
Q07 3Sum — All unique triplets summing to zero show ▾

Sort + for each element use a two-pointer search for a pair summing to its negation. Skip duplicates at every level.

Time: O(n²)Space: O(1) extra

Key insight: Sorting makes duplicate-skipping trivial. Two pointers give O(n) inner loop, giving O(n²) overall.

Practice on LeetCode →
Python Solution
def threeSum(nums): nums.sort() result = [] for i in range(len(nums) - 2): if i > 0 and nums[i] == nums[i-1]: continue # skip duplicate at outer level left, right = i + 1, len(nums) - 1 while left < right: total = nums[i] + nums[left] + nums[right] if total == 0: result.append([nums[i], nums[left], nums[right]]) while left < right and nums[left] == nums[left+1]: left += 1 while left < right and nums[right] == nums[right-1]: right -= 1 left += 1; right -= 1 elif total < 0: left += 1 else: right -= 1 return result
How it works: Fix element nums[i], then find pairs summing to -nums[i] using two pointers converging from both ends. If sum is too small, advance left; too large, retreat right; equal, record and skip duplicates. The duplicate-skipping after finding a valid triplet ensures unique results.
Q08 Product of Array Except Self — O(n) without division show ▾

Two passes: left→right builds prefix products into output. Right→left multiplies by running suffix. No division, O(1) extra space.

Time: O(n)Space: O(1) extra

Key insight: result[i] = prefix[i] × suffix[i]. Second pass uses a running variable — no separate suffix array needed.

Practice on LeetCode →
Python Solution
def productExceptSelf(nums): n = len(nums) result = [1] * n # Pass 1: result[i] = product of all elements to the LEFT prefix = 1 for i in range(n): result[i] = prefix prefix *= nums[i] # Pass 2: multiply by product of all elements to the RIGHT suffix = 1 for i in range(n - 1, -1, -1): result[i] *= suffix suffix *= nums[i] return result
How it works: After pass 1, result[i] holds the product of everything to the left of index i (prefix). Pass 2 multiplies each position by the running suffix (product of everything to the right). The final result[i] = left-product × right-product = product of all except nums[i].
Q09 Combination Sum — All combinations summing to target (with reuse) show ▾

Backtracking: pick from start index onward (allowing reuse), recurse, undo. Prune when sum exceeds target.

Time: O(N^(T/M))Space: O(T/M)

Key insight: Passing start (not start+1) allows reuse of the same candidate. The start index prevents reversed duplicates like [2,3] vs [3,2].

Practice on LeetCode →
Python Solution
def combinationSum(candidates, target): result = [] def backtrack(start, path, remaining): if remaining == 0: result.append(path[:]) # found a valid combination return for i in range(start, len(candidates)): c = candidates[i] if c > remaining: continue # prune: this candidate is too large path.append(c) backtrack(i, path, remaining - c) # i (not i+1): allow reuse path.pop() # undo (backtrack) backtrack(0, [], target) return result
How it works: At each call we try every candidate from start onwards. We append the candidate, recurse to try combinations for the reduced remainder, then pop it (undo). Using i (not i+1) in the recursive call allows reusing the same element. Candidates equal to remaining are valid; those larger are skipped (pruning).
Q10 Merge Intervals — Combine all overlapping intervals show ▾

Sort by start time, then one pass: if current interval overlaps the last merged one, extend it. Otherwise push as new.

Time: O(n log n)Space: O(n)

Key insight: Sorting guarantees overlapping intervals are adjacent. One comparison per interval is sufficient — no look-back needed.

Practice on LeetCode →
Python Solution
def merge(intervals): intervals.sort(key=lambda x: x[0]) merged = [intervals[0]] for start, end in intervals[1:]: if start <= merged[-1][1]: # Overlap: extend the last merged interval's end merged[-1][1] = max(merged[-1][1], end) else: # No overlap: start a new merged group merged.append([start, end]) return merged
How it works: After sorting, no non-adjacent interval can overlap with a later one. So we only ever compare the current interval against merged[-1] (the last merged entry). If start <= merged[-1][1], they overlap — we take the max of the two ends. Otherwise, append the current interval as a new group.
03

Stacks

Postfix evaluation, O(1) minimum retrieval, and two-pointer rain water.

Q11 Evaluate Reverse Polish Notation — Evaluate postfix expression show ▾

Push numbers onto a stack. On operator: pop two operands (order matters!), apply op, push result.

Time: O(n)Space: O(n)

Key insight: b = pop(), a = pop() → compute a op b. Reversing a and b gives wrong results for subtraction/division.

Practice on LeetCode →
Python Solution
def evalRPN(tokens): stack = [] for token in tokens: if token not in {'+', '-', '*', '/'}: stack.append(int(token)) else: b = stack.pop() # right operand a = stack.pop() # left operand if token == '+': stack.append(a + b) elif token == '-': stack.append(a - b) elif token == '*': stack.append(a * b) else: stack.append(int(a / b)) # truncate toward zero return stack[0]
How it works: Numbers are pushed directly. When we see an operator, the top two stack elements are the operands — pop them (b first, then a), apply the operation, and push the result back. The final stack element is the answer. Using int(a / b) (not a // b) correctly truncates toward zero for negative numbers.
Q12 Min Stack — O(1) minimum retrieval at all times show ▾

Store (value, current_min) pairs. Each push records the minimum at that point in time.

Time: O(1) all opsSpace: O(n)

Key insight: Each entry snapshots the minimum including itself. When it's popped, the previous minimum is restored at the new top.

Practice on LeetCode →
Python Solution
class MinStack: def __init__(self): # Store (value, current_min_at_this_point) pairs self.stack = [] def push(self, val: int) -> None: curr_min = min(val, self.stack[-1][1]) if self.stack else val self.stack.append((val, curr_min)) def pop(self) -> None: self.stack.pop() def top(self) -> int: return self.stack[-1][0] def getMin(self) -> int: return self.stack[-1][1]
How it works: Each push stores a pair: the value and the running minimum at that stack depth (the smaller of the new value and the current stack top's min). getMin() just peeks stack[-1][1]. When we pop, the previous minimum is automatically restored because it was saved in the new top entry.
Q13 Trapping Rain Water — Total water trapped between bars show ▾

Two pointers: always process the shorter boundary. Water = shorter boundary height − current bar height.

Time: O(n)Space: O(1)

Key insight: Process the shorter side because you know its limiting wall. The taller opposite side can only be ≥ our current max — so the water calculation is guaranteed safe.

Practice on LeetCode →
Python Solution
def trap(height): left, right = 0, len(height) - 1 max_left = max_right = water = 0 while left < right: if height[left] <= height[right]: if height[left] >= max_left: max_left = height[left] # update wall else: water += max_left - height[left] # water fills the dip left += 1 else: if height[right] >= max_right: max_right = height[right] else: water += max_right - height[right] right -= 1 return water
How it works: We pick the shorter side (height[left] <= height[right]) and process it. If it's taller than max_left, update the max (no water here — it's a wall). Otherwise, water fills the dip: max_left - height[left]. Processing the shorter side is safe because the other side is guaranteed to be at least as tall as our current max — the limiting factor is our current side's max.
04

Binary Trees

BFS level-order, LCA via recursive DFS, and preorder serialize/deserialize.

Q14 Binary Tree Level Order Traversal — Collect nodes level by level show ▾

BFS with queue. Snapshot queue size at each round to separate levels.

Time: O(n)Space: O(n)

Key insight: level_size = len(queue) before the inner loop. Process exactly that many nodes — their children are for the next level.

Practice on LeetCode →
Python Solution
from collections import deque def levelOrder(root): if not root: return [] result = [] queue = deque([root]) while queue: level_size = len(queue) # snapshot: nodes on this level level = [] for _ in range(level_size): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result
How it works: Before each inner loop, we snapshot len(queue) — that's exactly how many nodes belong to the current level. We dequeue exactly that many, collect their values, and enqueue their children. The children are added to the queue but only processed in the next outer iteration. This cleanly separates levels without sentinel markers.
Q15 Lowest Common Ancestor of a Binary Tree — Find LCA recursively show ▾

DFS: return node if it's null/p/q. If both left and right return non-null, the current node is the LCA.

Time: O(n)Space: O(h)

Key insight: "Both children return non-null" = p and q found on opposite sides = this node is the split point = LCA.

Practice on LeetCode →
Python Solution
def lowestCommonAncestor(root, p, q): # Base case: reached null, or found p or q if not root or root == p or root == q: return root left = lowestCommonAncestor(root.left, p, q) right = lowestCommonAncestor(root.right, p, q) if left and right: return root # p and q in different subtrees → current is LCA return left or right # propagate the non-null side upward
How it works: We recurse into both subtrees. If a node equals p or q, we return it immediately. If both left and right return something, p and q were found on opposite sides — the current node is their LCA. If only one side found something (the other returned None), we bubble that result up. This also handles the ancestor case: if p is an ancestor of q, p is returned before q is ever reached.
Q16 Serialize and Deserialize Binary Tree — Convert to string and reconstruct show ▾

Preorder DFS with '#' as null marker. Deserialize by consuming tokens with an iterator.

Time: O(n)Space: O(n)

Key insight: Null markers are essential — without them the same preorder sequence can describe many different trees.

Practice on LeetCode →
Python Solution
class Codec: def serialize(self, root) -> str: if not root: return '#' return f"{root.val},{self.serialize(root.left)},{self.serialize(root.right)}" def deserialize(self, data: str): tokens = iter(data.split(',')) def build(): val = next(tokens) if val == '#': return None node = TreeNode(int(val)) node.left = build() # consume left subtree tokens node.right = build() # consume right subtree tokens return node return build()
How it works: Serialization is preorder DFS — we visit the node, recurse left, recurse right. Null nodes are written as '#'. Deserialization uses an iterator over the comma-split tokens. Each recursive build() call consumes exactly one token. If it's '#', return None. Otherwise create the node and build its left then right subtrees recursively — the iterator naturally tracks position.
05

Dynamic Programming

Kadane's algorithm for max subarray, and bottom-up coin change (unbounded knapsack).

Q17 Maximum Subarray — Kadane's algorithm show ▾

At each element: curr = max(num, curr + num). Extend the run or restart — whichever is larger.

Time: O(n)Space: O(1)

Key insight: If the running sum becomes negative, it's a drag — start fresh at the current element. Track the global max separately.

Practice on LeetCode →
Python Solution
def maxSubArray(nums): curr_sum = nums[0] max_sum = nums[0] for num in nums[1:]: # Extend the current run, or start a new subarray here curr_sum = max(num, curr_sum + num) max_sum = max(max_sum, curr_sum) return max_sum
How it works: curr_sum tracks the best subarray ending at the current index. If curr_sum + num < num, then curr_sum is negative — it's better to discard the previous run and start fresh at num. We update max_sum after every step to capture the global best. Both are initialized with nums[0] to handle all-negative arrays.
Q18 Coin Change — Minimum coins to make an amount show ▾

Bottom-up DP. dp[i] = min(dp[i - c] + 1) for each coin c. Build from 0 up to amount.

Time: O(amount × coins)Space: O(amount)

Key insight: Unbounded knapsack pattern — coins can be reused. Each dp[i] represents the minimum coins for that sub-amount. Build up from the base case dp[0] = 0.

Practice on LeetCode →
Python Solution
def coinChange(coins, amount): INF = float('inf') dp = [INF] * (amount + 1) dp[0] = 0 # base case: 0 coins needed for amount 0 for i in range(1, amount + 1): for coin in coins: if coin <= i: dp[i] = min(dp[i], dp[i - coin] + 1) return dp[amount] if dp[amount] != INF else -1
How it works: We fill the DP table from 1 to amount. For each amount i, we try using each coin c. The cost is 1 (for coin c) plus the minimum coins needed for the remainder i - c. Since we've already computed all smaller amounts, dp[i - c] is ready. If dp[amount] is still infinity after filling the table, the amount is unreachable — return -1.
06

Binary Search

Modified binary search on rotated arrays, and floor search for timestamped lookups.

Q19 Search in Rotated Sorted Array — Binary search after unknown rotation show ▾

At each step, determine which half is sorted (compare mid vs left). If target in the sorted half, search it; otherwise search the other half.

Time: O(log n)Space: O(1)

Key insight: One half is ALWAYS fully sorted after any rotation. Identify it in O(1), check if target is within its range, binary search accordingly.

Practice on LeetCode →
Python Solution
def search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: return mid # Left half is sorted if nums[left] <= nums[mid]: if nums[left] <= target < nums[mid]: right = mid - 1 # target in sorted left half else: left = mid + 1 # target in right half # Right half is sorted else: if nums[mid] < target <= nums[right]: left = mid + 1 # target in sorted right half else: right = mid - 1 # target in left half return -1
How it works: Standard binary search with one extra check. At each step, compare nums[left] to nums[mid]: if nums[left] <= nums[mid], the left half is sorted (no rotation in it). We then check if target lies within its range — if yes, search left; if no, search right. The right half check is symmetric.
Q20 Time-Based Key-Value Store — Retrieve value at or before a timestamp show ▾

Store sorted (timestamp, value) pairs per key. Use bisect_right - 1 (floor search) for O(log n) get.

Time: O(log n) getSpace: O(n)

Key insight: bisect_right(timestamps, target) - 1 gives the largest timestamp ≤ target — the "floor" pattern.

Practice on LeetCode →
Python Solution
import bisect from collections import defaultdict class TimeMap: def __init__(self): # key → list of (timestamp, value), always in sorted order self.store = defaultdict(list) def set(self, key: str, value: str, timestamp: int) -> None: self.store[key].append((timestamp, value)) def get(self, key: str, timestamp: int) -> str: pairs = self.store.get(key, []) if not pairs: return "" # Floor search: largest timestamp <= query timestamp idx = bisect.bisect_right(pairs, (timestamp, chr(127))) - 1 return pairs[idx][1] if idx >= 0 else ""
How it works: set appends to the list — since timestamps are strictly increasing, the list stays sorted. For get, we use bisect_right to find the insertion point for (timestamp, chr(127)) (a sentinel that sorts after any value string at that timestamp). Subtracting 1 gives the index of the largest timestamp ≤ query — the floor. If idx is -1, no valid timestamp exists.
07

Strings

Sliding window — no-repeat substring and minimum window with full character matching.

Q21 Longest Substring Without Repeating Characters show ▾

Sliding window + hash map (char → last index). Jump left past the duplicate in O(1).

Time: O(n)Space: O(k) alphabet

Key insight: Store the character's index, not just a boolean. This lets you jump left directly past the duplicate — avoiding O(n) shrinking.

Practice on LeetCode →
Python Solution
def lengthOfLongestSubstring(s): last_seen = {} # char → last seen index left = max_len = 0 for right, char in enumerate(s): # If char was seen and is still inside the current window if char in last_seen and last_seen[char] >= left: left = last_seen[char] + 1 # jump past the duplicate last_seen[char] = right max_len = max(max_len, right - left + 1) return max_len
How it works: last_seen[char] stores where we last saw a character. If we see a duplicate that's still inside [left, right], we jump left to last_seen[char] + 1 — shrinking the window in one step. The window invariant is: no duplicate characters in s[left..right]. We update last_seen every visit and track the max window size.
Q22 Minimum Window Substring — Smallest window containing all chars of t show ▾

Expand right until valid (all t chars covered), then shrink left to minimize. Track formed counter for O(1) validity.

Time: O(|s| + |t|)Space: O(|t|)

Key insight: formed increments only when a char's count crosses its required threshold. This gives O(1) validity check without scanning the full frequency map.

Practice on LeetCode →
Python Solution
from collections import Counter def minWindow(s, t): need = Counter(t) have = {} formed = 0 required = len(need) # distinct chars needed left = 0 best = (float('inf'), 0, 0) # (length, left, right) for right, char in enumerate(s): have[char] = have.get(char, 0) + 1 if char in need and have[char] == need[char]: formed += 1 # this char is now fully satisfied while formed == required: # window is valid — try to shrink if right - left + 1 < best[0]: best = (right - left + 1, left, right) lc = s[left] have[lc] -= 1 if lc in need and have[lc] < need[lc]: formed -= 1 # window no longer satisfies this char left += 1 _, l, r = best return s[l:r+1] if best[0] != float('inf') else ""
How it works: We expand right, adding characters. When a char's count hits the required count, formed increments. When formed == required, the window is valid. We then shrink from the left — updating the best window if it's smaller — until the window becomes invalid (removing left char causes formed to drop). Then we expand right again.
08

Heap

Max-heap of size k for top-K selection, and two-heap technique for streaming medians.

Q23 K Closest Points to Origin — Find K nearest points show ▾

Max-heap of size k. Push (dist², x, y). When size exceeds k, pop the max (farthest). Heap always holds the k closest.

Time: O(n log k)Space: O(k)

Key insight: Negate distance for max-heap behavior in Python (min-heap by default). Use dist² to skip sqrt.

Practice on LeetCode →
Python Solution
import heapq def kClosest(points, k): heap = [] # max-heap via negated distances for x, y in points: dist_sq = x*x + y*y # no sqrt needed — monotonic heapq.heappush(heap, (-dist_sq, x, y)) if len(heap) > k: heapq.heappop(heap) # evict farthest point return [[x, y] for _, x, y in heap]
How it works: Python's heapq is a min-heap. To get max-heap behavior, we negate the distance. We push (-dist, x, y) for every point. When the heap grows beyond k, we pop — which removes the most negative value, i.e., the largest (farthest) distance. After processing all points, the heap contains exactly the k closest.
Q24 Find Median from Data Stream — Running median in O(log n) show ▾

Two heaps: max-heap lo (lower half), min-heap hi (upper half). Keep sizes balanced. Median = top(s).

Time: O(log n) addSpace: O(n)

Key insight: Two heaps split the stream at the median. Their tops are always the two middle values — median is O(1).

Practice on LeetCode →
Python Solution
import heapq class MedianFinder: def __init__(self): self.lo = [] # max-heap for lower half (negate values) self.hi = [] # min-heap for upper half def addNum(self, num: int) -> None: heapq.heappush(self.lo, -num) # Ensure lo.top <= hi.top (all of lo must be ≤ all of hi) if self.hi and -self.lo[0] > self.hi[0]: heapq.heappush(self.hi, -heapq.heappop(self.lo)) # Balance: lo can have at most 1 extra element if len(self.lo) > len(self.hi) + 1: heapq.heappush(self.hi, -heapq.heappop(self.lo)) elif len(self.hi) > len(self.lo): heapq.heappush(self.lo, -heapq.heappop(self.hi)) def findMedian(self) -> float: if len(self.lo) == len(self.hi): return (-self.lo[0] + self.hi[0]) / 2.0 return -self.lo[0] # lo has the extra middle element
How it works: lo stores the lower half (max-heap via negation), hi stores the upper half (min-heap). After each push, two invariants are maintained: (1) every element in lo ≤ every element in hi (corrected by moving lo's max to hi), and (2) sizes differ by at most 1. The median is either the average of both tops (even count) or lo's top (odd count — lo gets the extra).
09

Recursion

Backtracking with in-place swaps to enumerate all permutations.

Q25 Permutations — Generate all permutations via backtracking show ▾

At each level, swap each element into the "decided" position, recurse, then swap back (undo).

Time: O(n × n!)Space: O(n)

Key insight: Array is split into "decided" (0..start-1) and "choosing" (start..end). Each undecided element gets a turn at position start. Swap back restores state for the next iteration.

Practice on LeetCode →
Python Solution
def permute(nums): result = [] def backtrack(start): if start == len(nums): result.append(nums[:]) # snapshot of current permutation return for i in range(start, len(nums)): nums[start], nums[i] = nums[i], nums[start] # choose backtrack(start + 1) nums[start], nums[i] = nums[i], nums[start] # undo backtrack(0) return result
How it works: backtrack(start) generates all permutations of nums[start:]. We try each element from start to end as the next element at position start by swapping it into that position. After recursing, we swap back (undo) to restore the original state for the next iteration. When start == len(nums), all positions are decided — we've built a complete permutation.
Quiz

Random Question Mode

Try answering before revealing — fastest way to find gaps.

Click "Next Question" to begin.