LeetCode Roadmap

# ===== The five-step framework =====
# 1) Restate the problem in your own words
# 2) Spot the pattern (sliding window, two pointers, DP, BFS, ...)
# 3) Brute force first; state its complexity
# 4) Optimise toward the target complexity
# 5) Code, then test on edge cases

# ===== Pattern recognition cheat =====
# - Subarray / substring with constraint           -> sliding window
# - Sorted input, find pair / triple                 -> two pointers
# - Find shortest path on unweighted graph          -> BFS
# - Weighted shortest path                           -> Dijkstra
# - Topological order / build sequence              -> Kahn or DFS topo sort
# - Cycle detection in linked list                   -> Floyd's fast/slow
# - All subsets / permutations                       -> backtracking
# - 'Can I reach target with these choices?'         -> DP
# - 'Optimal substructure + overlapping subproblems' -> DP
# - 'Local optimum is global optimum'                -> greedy
# - 'Range query + point update'                     -> Fenwick / segment tree
# - 'Lots of small strings, prefix queries'          -> trie

# ===== Pacing on a 45-min interview =====
# 5 min  -> restate + ask clarifying questions
# 5 min  -> brute force + complexity
# 10 min -> optimise + complexity
# 20 min -> code (out loud)
# 5 min  -> test edge cases

# ===== Example walkthrough: two-sum =====
# Restate: array nums + target. Return indices of two elements summing to target.
# Brute force: O(n^2) double loop.
# Optimise: hash map of value -> index. O(n) time, O(n) space.
def two_sum(nums, target):
    seen = {}
    for i, v in enumerate(nums):
        if target - v in seen:
            return [seen[target - v], i]
        seen[v] = i
    return []
# Edge cases: empty, duplicate values, negative numbers, no solution.

# ===== Example: longest substring without repeating chars =====
# Pattern: variable-size sliding window.
def length_of_longest_substring(s):
    last = {}
    left = 0
    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
# O(n) time, O(min(n, alphabet)) space.

# ===== Example: number of islands =====
# Pattern: BFS / DFS on a grid.
from collections import deque
def num_islands(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    seen = set()
    count = 0
    def bfs(r, c):
        q = deque([(r, c)])
        seen.add((r, c))
        while q:
            cr, cc = q.popleft()
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr, nc = cr + dr, cc + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen and grid[nr][nc] == '1':
                    seen.add((nr, nc)); q.append((nr, nc))
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1' and (r, c) not in seen:
                bfs(r, c)
                count += 1
    return count
# O(R*C) time and space.

# ===== Edge cases to ALWAYS check =====
# - Empty input
# - Single element
# - All same elements
# - Already sorted / reverse sorted
# - Maximum size (n = 10^5 or 10^6)
# - Negative numbers / overflow
# - Floats / NaN
# - Unicode / emoji in strings

# ===== Grokking pattern checklist (study list) =====
# 1) Sliding window
# 2) Two pointers
# 3) Fast / slow pointers
# 4) Merge intervals
# 5) Cyclic sort
# 6) In-place linked list reversal
# 7) Tree BFS / DFS
# 8) Two heaps
# 9) Subsets / backtracking
# 10) Modified binary search
# 11) Top-K
# 12) K-way merge
# 13) 0/1 knapsack
# 14) Unbounded knapsack
# 15) Fibonacci-style DP
# 16) Palindromic subsequence DP
# 17) Longest common subsequence DP
# 18) Topological sort
# 19) Union-Find
# 20) Bitwise XOR

# If you can spot the pattern in < 60 seconds, the implementation is 30 lines
# of templated code; you've already won.

# ===== Pitfalls =====
# - Jumping to code without restating the problem
# - Forgetting to state complexity
# - Writing 200 lines for a 30-line problem (use templates)
# - Skipping edge cases
# - 'I memorised this answer' panic when the question is a variation

// Start with Easy → 1-2 of each pattern.
// Mediums become the bulk by week 3.
// Spaced-repetition revisits are the unlock.