LeetCode Warm-Ups

A gym workout has a shape. You warm up the joints, you load up the compound lifts, you finish on accessories. Same shape every session. The order is what makes the work add up. LeetCode-style problems use the same shape: read the problem, write the brute-force solution that proves you understand it, name the bottleneck that makes brute force too slow, replace it with a better data structure or algorithm. Every problem on this page follows that order.

The format goes back to the ACM International Collegiate Programming Contest, which started at Texas A&M in 1970 and went global in 1977. By the late 1990s the problems had standardized into "input, output, time limit." TopCoder launched in 2001 with the addition of cash prizes and ranked competitive coders like chess players. By 2010 every Silicon Valley company had picked the format for engineering interviews — partly because it scales, partly because it filters for one specific kind of thinking. The controversy is real. The format favors people who have done a lot of these problems and tells you very little about whether someone can ship a real product. It is also the way the gate is staffed at every company that pays well, so you learn it. Open leetcode.py.

Two Sum is the canonical first problem. You get a list of integers and a target. Return the indices of the two numbers in the list that add up to the target. The brute-force version checks every pair.

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []
 
assert two_sum_brute([2, 7, 11, 15], 9) == [0, 1]

Two nested loops. O(n²). For a list of 1000 numbers it does 500000 comparisons. The bottleneck: for each nums[i] you are scanning the whole rest of the list to find target - nums[i]. A hash map can answer "is this number in here?" in O(1). Build the map as you go and the algorithm becomes one pass.

def two_sum(nums, target):
    seen = {}
    for i, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            print(f"found pair: {seen[complement]} + {i} -> {complement} + {value}")
            return [seen[complement], i]
        seen[value] = i
    return []
 
assert two_sum([2, 7, 11, 15], 9) == [0, 1]

found pair: 0 + 1 -> 2 + 7

The print shows the invariant: at every step, seen holds every number to the left of i. When you find that target - nums[i] is already in seen, you have found your pair. O(n) time, O(n) memory. The trade you make in nearly every interview problem.

Valid Parentheses is the stack problem. Given a string of brackets like "({[]})", decide whether they are properly matched. The brute-force version tries to repeatedly find and remove the innermost matched pair until nothing is left. It works but it is O(n²). The stack version is O(n).

def is_valid(s):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{"}
    for char in s:
        if char in "([{":
            stack.append(char)
        else:
            if not stack or stack.pop() != pairs[char]:
                return False
    print(f"final stack: {stack}")
    return not stack
 
assert is_valid("({[]})") is True
assert is_valid("(]") is False

final stack: []

The invariant: the stack always holds the open brackets you have not yet closed, in the order you opened them. Every closing bracket must match the most recent open bracket. If the stack is empty when a closing bracket arrives, or the top of the stack does not match, the string is invalid. After scanning a valid string the stack is empty.

Best Time to Buy and Sell Stock gives you a list of daily prices and asks for the maximum profit you could have made buying once and selling later. Brute force tries every (buy, sell) pair: O(n²).

def max_profit_brute(prices):
    best = 0
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            best = max(best, prices[j] - prices[i])
    return best

The bottleneck: for each day j, you only need the minimum price seen up to day j-1. Track that minimum as you scan once.

def max_profit(prices):
    min_so_far = float("inf")
    best = 0
    for i, price in enumerate(prices):
        if price < min_so_far:
            min_so_far = price
        elif price - min_so_far > best:
            best = price - min_so_far
            print(f"day {i}: new best profit {best} (buy at {min_so_far}, sell at {price})")
    return best
 
assert max_profit([7, 1, 5, 3, 6, 4]) == 5

day 2: new best profit 4 (buy at 1, sell at 5)
day 4: new best profit 5 (buy at 1, sell at 6)

The print shows when the answer improved and why. O(n) time, O(1) memory.

Reverse a Linked List is the classic pointer-juggling problem. Given the head of a singly linked list, return the head of the same list reversed. The technique: walk the list with three pointers — prev, current, next — and at each step rewire current.next to point at prev.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
 
def reverse_list(head):
    prev = None
    current = head
    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    return prev
 
def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out
 
original = Node(1, Node(2, Node(3, Node(4))))
reversed_head = reverse_list(original)
print(to_list(reversed_head))
assert to_list(reversed_head) == [4, 3, 2, 1]

[4, 3, 2, 1]

There is no brute-force version of this — the in-place reverse is the natural shape. The trap is forgetting to save next before you overwrite current.next, because you would lose the rest of the list. The print catches the result so you know the rewiring worked.

Number of Islands gives you a 2D grid of '1' for land and '0' for water and asks how many connected land masses there are. This is graph traversal in disguise — every cell is a vertex, and adjacent land cells are connected by edges. Run DFS from each unvisited land cell and count.

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])
    visited = set()
    count = 0
 
    def dfs(r, c):
        if (r, c) in visited or r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == "0":
            return
        visited.add((r, c))
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)
 
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in visited:
                dfs(r, c)
                count += 1
                print(f"island {count} starts at ({r}, {c})")
    return count
 
grid = [
    ["1", "1", "0", "0"],
    ["1", "1", "0", "1"],
    ["0", "0", "0", "1"],
    ["1", "0", "0", "0"],
]
assert num_islands(grid) == 3

island 1 starts at (0, 0)
island 2 starts at (1, 3)
island 3 starts at (3, 0)

The brute force here would be union-find or repeated BFS — both still O(rows × cols), so the DFS version is the natural choice. The print shows where each island was first hit.

Climbing Stairs is the friendliest dynamic programming problem. You can take 1 or 2 steps at a time. How many distinct ways are there to climb n stairs? The recursive insight: the number of ways to reach step n equals ways(n-1) + ways(n-2). That is Fibonacci with different starting values, so the answer is the bottom-up loop you already know.

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n + 1):
        a, b = b, a + b
    return b
 
assert climb_stairs(5) == 8
print(f"5 stairs: {climb_stairs(5)} ways")

5 stairs: 8 ways

O(n) time, O(1) memory. The brute-force recursive version is O(2^n) and you saw it last lesson under the name fib.

The pattern across all six problems is the same. Brute force first, because it proves you understand the problem. Name the wasted work — you re-scanned the list, you re-paired the brackets, you re-checked every (buy, sell) day. Replace the wasted work with a data structure (hash map, stack) or a one-pass invariant (running min, two pointers). The optimization is rarely original. It is the same handful of moves applied to a different surface.

You finished the algorithms section. The functions you wrote so far are loose — they take inputs and return outputs without holding any state between calls. Real programs need state that belongs together: a deck of cards that knows how many it has dealt, a game that knows whose turn it is. The next section gives that state a class.