Blind 75 Solutions: Interview Reference

The Blind 75 is the classic list of 75 LeetCode problems chosen to cover every pattern interviewers actually test — arrays, strings, binary search, linked lists, trees, graphs, DP, intervals, and heaps. Work through them and you've seen the shape of almost any coding question they can ask.

Each problem has two solutions:

Brute force: naive, easy-to-see approach
Optimal: the actual interview answer

Language: Python 3.

Array

1. Two Sum

Given nums and target, return indices of two numbers that add to target.

Predict the pattern

Brute force: O(n²) / O(1) Check every pair.

def twoSum(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]

Optimal: O(n) / O(n) Hash map: for each x, look up target - x.

def twoSum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i

2. Best Time to Buy and Sell Stock

Max profit from one buy + one sell.

Brute force: O(n²) / O(1) Try every (buy, sell) pair.

def maxProfit(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

Optimal: O(n) / O(1) Track running min price; profit = price − min so far.

def maxProfit(prices):
    lo, best = float('inf'), 0
    for p in prices:
        lo = min(lo, p)
        best = max(best, p - lo)
    return best

3. Contains Duplicate

Return True if any value appears at least twice.

Brute force: O(n²) / O(1)

def containsDuplicate(nums):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

Optimal: O(n) / O(n)

def containsDuplicate(nums):
    return len(set(nums)) != len(nums)

4. Product of Array Except Self

output[i] = product of all elements except nums[i]. No division.

Brute force: O(n²) / O(n)

def productExceptSelf(nums):
    n = len(nums)
    out = [1] * n
    for i in range(n):
        for j in range(n):
            if i != j:
                out[i] *= nums[j]
    return out

Optimal: O(n) / O(1) extra Two passes: prefix products, then multiply by suffix on the fly.

def productExceptSelf(nums):
    n = len(nums)
    out = [1] * n
    for i in range(1, n):
        out[i] = out[i - 1] * nums[i - 1]
    right = 1
    for i in range(n - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out

5. Maximum Subarray

Largest sum of a contiguous subarray.

Brute force: O(n²) / O(1)

def maxSubArray(nums):
    best = float('-inf')
    for i in range(len(nums)):
        s = 0
        for j in range(i, len(nums)):
            s += nums[j]
            best = max(best, s)
    return best

Optimal: Kadane, O(n) / O(1) At each index, either extend or start fresh.

def maxSubArray(nums):
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

6. Maximum Product Subarray

Largest product of a contiguous subarray.

Brute force: O(n²) / O(1)

def maxProduct(nums):
    best = nums[0]
    for i in range(len(nums)):
        p = 1
        for j in range(i, len(nums)):
            p *= nums[j]
            best = max(best, p)
    return best

Optimal: O(n) / O(1) Track min and max ending here (negatives flip them).

def maxProduct(nums):
    cur_max = cur_min = best = nums[0]
    for x in nums[1:]:
        cands = (x, x * cur_max, x * cur_min)
        cur_max, cur_min = max(cands), min(cands)
        best = max(best, cur_max)
    return best

7. Find Minimum in Rotated Sorted Array

Brute force: O(n) / O(1)

def findMin(nums):
    return min(nums)

Optimal: Binary search, O(log n) / O(1)

def findMin(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

8. Search in Rotated Sorted Array

Brute force: O(n) / O(1)

def search(nums, target):
    for i, x in enumerate(nums):
        if x == target:
            return i
    return -1

Optimal: Binary search, O(log n) / O(1)

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:          # left half sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                               # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

9. 3 Sum

All unique triplets that sum to 0.

Brute force: O(n³) / O(n)

def threeSum(nums):
    res = set()
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    res.add(tuple(sorted((nums[i], nums[j], nums[k]))))
    return [list(t) for t in res]

Optimal: Sort + two pointers, O(n²) / O(1)

def threeSum(nums):
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if i and nums[i] == nums[i - 1]:
            continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s == 0:
                res.append([nums[i], nums[l], nums[r]])
                l += 1; r -= 1
                while l < r and nums[l] == nums[l - 1]: l += 1
                while l < r and nums[r] == nums[r + 1]: r -= 1
            elif s < 0:
                l += 1
            else:
                r -= 1
    return res

10. Container With Most Water

Max area between two vertical lines.

Brute force: O(n²) / O(1)

def maxArea(height):
    best = 0
    for i in range(len(height)):
        for j in range(i + 1, len(height)):
            best = max(best, (j - i) * min(height[i], height[j]))
    return best

Optimal: Two pointers, O(n) / O(1) Move the shorter side inward.

def maxArea(height):
    l, r, best = 0, len(height) - 1, 0
    while l < r:
        best = max(best, (r - l) * min(height[l], height[r]))
        if height[l] < height[r]:
            l += 1
        else:
            r -= 1
    return best

Binary

11. Sum of Two Integers (no `+`/`-`)

Predict the pattern

Brute force: built-in

def getSum(a, b):
    return a + b

Optimal: bit manipulation, O(1) XOR is sum without carry; AND<<1 is the carry.

def getSum(a, b):
    mask = 0xFFFFFFFF
    while b & mask:
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask
    return a if a <= 0x7FFFFFFF else ~(a ^ mask)

12. Number of 1 Bits

Brute force: O(32)

def hammingWeight(n):
    return bin(n).count('1')

Optimal: Brian Kernighan, O(set-bits) n & (n-1) clears the lowest set bit.

def hammingWeight(n):
    c = 0
    while n:
        n &= n - 1
        c += 1
    return c

13. Counting Bits

For 0..n, return list of popcount(i).

Brute force: O(n log n)

def countBits(n):
    return [bin(i).count('1') for i in range(n + 1)]

Optimal: DP, O(n) dp[i] = dp[i >> 1] + (i & 1).

def countBits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

14. Missing Number

Array contains n distinct values in [0, n]; find the missing one.

Brute force: O(n log n) sort, or O(n)/O(n) set

def missingNumber(nums):
    s = set(nums)
    for i in range(len(nums) + 1):
        if i not in s:
            return i

Optimal: sum or XOR, O(n) / O(1)

def missingNumber(nums):
    n = len(nums)
    return n * (n + 1) // 2 - sum(nums)

15. Reverse Bits

Brute force: string flip

def reverseBits(n):
    return int(bin(n)[2:].zfill(32)[::-1], 2)

Optimal: bit shift, O(32) / O(1)

def reverseBits(n):
    res = 0
    for _ in range(32):
        res = (res << 1) | (n & 1)
        n >>= 1
    return res

Dynamic Programming

16. Climbing Stairs

Take 1 or 2 steps; count ways to reach n.

Predict the pattern

Brute force: recursion, O(2ⁿ)

def climbStairs(n):
    if n <= 2: return n
    return climbStairs(n - 1) + climbStairs(n - 2)

Optimal: Fibonacci, O(n) / O(1)

def climbStairs(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

17. Coin Change

Fewest coins to make amount, or -1.

Brute force: recursion, O(coinsᵃᵐᵗ)

def coinChange(coins, amount):
    def rec(rem):
        if rem < 0: return float('inf')
        if rem == 0: return 0
        return min(rec(rem - c) for c in coins) + 1
    ans = rec(amount)
    return ans if ans != float('inf') else -1

Optimal: bottom-up DP, O(amount·coins) / O(amount)

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

18. Longest Increasing Subsequence

Brute force: DP, O(n²) / O(n)

def lengthOfLIS(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

Optimal: patience sort, O(n log n) / O(n)

import bisect
def lengthOfLIS(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

19. Longest Common Subsequence

Brute force: recursion, O(2^(m+n))

def longestCommonSubsequence(a, b):
    def rec(i, j):
        if i == len(a) or j == len(b): return 0
        if a[i] == b[j]: return 1 + rec(i + 1, j + 1)
        return max(rec(i + 1, j), rec(i, j + 1))
    return rec(0, 0)

Optimal: 2D DP, O(mn) / O(mn)

def longestCommonSubsequence(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            if a[i] == b[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])
    return dp[m][n]

20. Word Break

Can s be segmented into dict words?

Brute force: recursion, O(2ⁿ)

def wordBreak(s, wordDict):
    words = set(wordDict)
    def rec(i):
        if i == len(s): return True
        return any(s[i:j] in words and rec(j) for j in range(i + 1, len(s) + 1))
    return rec(0)

Optimal: DP, O(n²) / O(n)

def wordBreak(s, wordDict):
    words = set(wordDict)
    dp = [False] * (len(s) + 1)
    dp[0] = True
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[-1]

21. Combination Sum

All unique combos summing to target (reuse allowed).

Brute force: pure backtrack with duplicate sets

def combinationSum(candidates, target):
    res = set()
    def rec(rem, path):
        if rem == 0:
            res.add(tuple(sorted(path)))
            return
        if rem < 0: return
        for c in candidates:
            rec(rem - c, path + [c])
    rec(target, [])
    return [list(t) for t in res]

Optimal: backtrack with start index, prunes dupes

def combinationSum(candidates, target):
    res, candidates = [], sorted(candidates)
    def rec(start, rem, path):
        if rem == 0:
            res.append(path[:])
            return
        for i in range(start, len(candidates)):
            if candidates[i] > rem: break
            path.append(candidates[i])
            rec(i, rem - candidates[i], path)
            path.pop()
    rec(0, target, [])
    return res

22. House Robber

Can't rob two adjacent.

Brute force: recursion, O(2ⁿ)

def rob(nums):
    def rec(i):
        if i >= len(nums): return 0
        return max(nums[i] + rec(i + 2), rec(i + 1))
    return rec(0)

Optimal: O(n) / O(1)

def rob(nums):
    prev = curr = 0
    for x in nums:
        prev, curr = curr, max(curr, prev + x)
    return curr

23. House Robber II

Houses in a circle.

Brute force: try both windows with the O(2ⁿ) recursion above (omitted).

Optimal: run House Robber I twice, O(n) / O(1)

def rob(nums):
    if len(nums) == 1: return nums[0]
    def helper(arr):
        prev = curr = 0
        for x in arr:
            prev, curr = curr, max(curr, prev + x)
        return curr
    return max(helper(nums[1:]), helper(nums[:-1]))

24. Decode Ways

'A'..'Z' ↔ '1'..'26'. Count decodings of digit string.

Brute force: recursion, O(2ⁿ)

def numDecodings(s):
    def rec(i):
        if i == len(s): return 1
        if s[i] == '0': return 0
        ways = rec(i + 1)
        if i + 1 < len(s) and 10 <= int(s[i:i + 2]) <= 26:
            ways += rec(i + 2)
        return ways
    return rec(0)

Optimal: DP, O(n) / O(1)

def numDecodings(s):
    if not s or s[0] == '0': return 0
    prev2, prev1 = 1, 1
    for i in range(1, len(s)):
        cur = 0
        if s[i] != '0': cur += prev1
        if 10 <= int(s[i - 1:i + 1]) <= 26: cur += prev2
        prev2, prev1 = prev1, cur
    return prev1

25. Unique Paths

m x n grid, only right/down.

Brute force: recursion, O(2^(m+n))

def uniquePaths(m, n):
    def rec(i, j):
        if i == m - 1 or j == n - 1: return 1
        return rec(i + 1, j) + rec(i, j + 1)
    return rec(0, 0)

Optimal: DP, O(mn) / O(n)

def uniquePaths(m, n):
    row = [1] * n
    for _ in range(1, m):
        for j in range(1, n):
            row[j] += row[j - 1]
    return row[-1]

(Combinatorial closed form: C(m+n-2, m-1).)

26. Jump Game

Can you reach the last index?

Brute force: recursion, O(2ⁿ)

def canJump(nums):
    def rec(i):
        if i >= len(nums) - 1: return True
        for step in range(1, nums[i] + 1):
            if rec(i + step): return True
        return False
    return rec(0)

Optimal: greedy, O(n) / O(1)

def canJump(nums):
    reach = 0
    for i, x in enumerate(nums):
        if i > reach: return False
        reach = max(reach, i + x)
    return True

Graph

27. Clone Graph

Predict the pattern

Brute force = optimal: BFS/DFS with a map.

Optimal: DFS, O(V+E) / O(V)

def cloneGraph(node):
    if not node: return None
    cache = {}
    def dfs(n):
        if n in cache: return cache[n]
        copy = Node(n.val)
        cache[n] = copy
        for nb in n.neighbors:
            copy.neighbors.append(dfs(nb))
        return copy
    return dfs(node)

28. Course Schedule

Detect cycle in directed graph.

Brute force: DFS from every node (still O(V+E) if memoized; without memo, exponential).

def canFinish(n, prereqs):
    g = [[] for _ in range(n)]
    for a, b in prereqs: g[b].append(a)
    def has_cycle(u, seen):
        if u in seen: return True
        seen.add(u)
        for v in g[u]:
            if has_cycle(v, seen): return True
        seen.remove(u)
        return False
    return not any(has_cycle(i, set()) for i in range(n))

Optimal: Kahn's BFS topo sort, O(V+E)

from collections import deque
def canFinish(n, prereqs):
    g = [[] for _ in range(n)]
    indeg = [0] * n
    for a, b in prereqs:
        g[b].append(a); indeg[a] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    done = 0
    while q:
        u = q.popleft(); done += 1
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return done == n

29. Pacific Atlantic Water Flow

Cells that can flow to both oceans.

Brute force: DFS from each cell, O((mn)²) For each cell, DFS to see if it reaches both oceans.

Optimal: DFS from oceans inward, O(mn)

def pacificAtlantic(heights):
    if not heights: return []
    m, n = len(heights), len(heights[0])
    pac, atl = set(), set()
    def dfs(i, j, seen):
        seen.add((i, j))
        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in seen \
               and heights[ni][nj] >= heights[i][j]:
                dfs(ni, nj, seen)
    for i in range(m):
        dfs(i, 0, pac); dfs(i, n - 1, atl)
    for j in range(n):
        dfs(0, j, pac); dfs(m - 1, j, atl)
    return [list(c) for c in pac & atl]

30. Number of Islands

Count connected components of '1's.

Brute force = optimal: DFS/BFS flood fill, O(mn).

def numIslands(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    def dfs(i, j):
        if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
            return
        grid[i][j] = '0'
        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
            dfs(i + di, j + dj)
    c = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                dfs(i, j); c += 1
    return c

31. Longest Consecutive Sequence

Brute force: sort, O(n log n)

def longestConsecutive(nums):
    if not nums: return 0
    nums = sorted(set(nums))
    best = run = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1] + 1:
            run += 1; best = max(best, run)
        else:
            run = 1
    return best

Optimal: set, O(n) / O(n) Only start counting from sequence beginnings.

def longestConsecutive(nums):
    s = set(nums); best = 0
    for x in s:
        if x - 1 not in s:
            y = x
            while y + 1 in s: y += 1
            best = max(best, y - x + 1)
    return best

32. Alien Dictionary

Topological order from sorted alien words.

Brute force: try all permutations, O(k!·...) (impractical).

Optimal: topo sort, O(C) where C = total chars

from collections import defaultdict, deque
def alienOrder(words):
    g = defaultdict(set)
    indeg = {c: 0 for w in words for c in w}
    for w1, w2 in zip(words, words[1:]):
        for a, b in zip(w1, w2):
            if a != b:
                if b not in g[a]:
                    g[a].add(b); indeg[b] += 1
                break
        else:
            if len(w1) > len(w2): return ""
    q = deque([c for c in indeg if indeg[c] == 0])
    res = []
    while q:
        c = q.popleft(); res.append(c)
        for nb in g[c]:
            indeg[nb] -= 1
            if indeg[nb] == 0: q.append(nb)
    return "".join(res) if len(res) == len(indeg) else ""

33. Graph Valid Tree

n nodes, edges form a tree iff connected and len(edges) == n-1.

Brute force: DFS check connectivity + cycle

def validTree(n, edges):
    if len(edges) != n - 1: return False
    g = [[] for _ in range(n)]
    for a, b in edges: g[a].append(b); g[b].append(a)
    seen = set()
    def dfs(u):
        seen.add(u)
        for v in g[u]:
            if v not in seen: dfs(v)
    dfs(0)
    return len(seen) == n

Optimal: Union-Find, O(n·α(n))

def validTree(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
        parent[ra] = rb
    return True

34. Number of Connected Components

Brute force: DFS from each unvisited node, O(V+E) (same as optimal).

def countComponents(n, edges):
    g = [[] for _ in range(n)]
    for a, b in edges: g[a].append(b); g[b].append(a)
    seen, c = set(), 0
    def dfs(u):
        seen.add(u)
        for v in g[u]:
            if v not in seen: dfs(v)
    for i in range(n):
        if i not in seen: dfs(i); c += 1
    return c

Optimal: Union-Find, O((V+E)·α)

def countComponents(n, edges):
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]; x = parent[x]
        return x
    c = n
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb: parent[ra] = rb; c -= 1
    return c

Interval

35. Insert Interval

Predict the pattern

Brute force: append, sort, then merge, O(n log n)

def insert(intervals, newInterval):
    intervals = sorted(intervals + [newInterval])
    merged = [intervals[0]]
    for s, e in intervals[1:]:
        if s <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], e)
        else:
            merged.append([s, e])
    return merged

Optimal: O(n) single pass

def insert(intervals, newInterval):
    res, i, n = [], 0, len(intervals)
    while i < n and intervals[i][1] < newInterval[0]:
        res.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval = [min(newInterval[0], intervals[i][0]),
                       max(newInterval[1], intervals[i][1])]
        i += 1
    res.append(newInterval)
    res.extend(intervals[i:])
    return res

36. Merge Intervals

Brute force: repeatedly merge until stable, O(n²) (slow).

Optimal: sort + sweep, O(n log n)

def merge(intervals):
    intervals.sort()
    out = [intervals[0]]
    for s, e in intervals[1:]:
        if s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

37. Non-overlapping Intervals

Min removals to make non-overlapping.

Brute force: DP on subsets, O(2ⁿ) (skip).

Optimal: greedy by end time, O(n log n)

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])
    end = float('-inf'); kept = 0
    for s, e in intervals:
        if s >= end:
            end = e; kept += 1
    return len(intervals) - kept

38. Meeting Rooms

Can a single person attend all?

Brute force: check every pair, O(n²)

def canAttendMeetings(intervals):
    for i in range(len(intervals)):
        for j in range(i + 1, len(intervals)):
            a, b = intervals[i], intervals[j]
            if a[0] < b[1] and b[0] < a[1]: return False
    return True

Optimal: sort, O(n log n)

def canAttendMeetings(intervals):
    intervals.sort()
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]: return False
    return True

39. Meeting Rooms II

Min rooms needed.

Brute force: timeline tally, O((max_t)·n) (slow for big times).

Optimal: min-heap of end times, O(n log n)

import heapq
def minMeetingRooms(intervals):
    intervals.sort()
    heap = []
    for s, e in intervals:
        if heap and heap[0] <= s:
            heapq.heappop(heap)
        heapq.heappush(heap, e)
    return len(heap)

Linked List

40. Reverse Linked List

Predict the pattern

Brute force: stack into new list, O(n) / O(n)

def reverseList(head):
    stack = []
    while head:
        stack.append(head); head = head.next
    dummy = ListNode(0); cur = dummy
    while stack:
        cur.next = stack.pop(); cur = cur.next
    cur.next = None
    return dummy.next

Optimal: in place, O(n) / O(1)

def reverseList(head):
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

41. Detect Cycle

Brute force: hash set, O(n) / O(n)

def hasCycle(head):
    seen = set()
    while head:
        if head in seen: return True
        seen.add(head); head = head.next
    return False

Optimal: Floyd's tortoise & hare, O(n) / O(1)

def hasCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast: return True
    return False

42. Merge Two Sorted Lists

Brute force: extract values, sort, rebuild, O((m+n)log(m+n))

def mergeTwoLists(a, b):
    vals = []
    while a: vals.append(a.val); a = a.next
    while b: vals.append(b.val); b = b.next
    dummy = cur = ListNode(0)
    for v in sorted(vals):
        cur.next = ListNode(v); cur = cur.next
    return dummy.next

Optimal: two pointers, O(m+n) / O(1)

def mergeTwoLists(a, b):
    dummy = cur = ListNode(0)
    while a and b:
        if a.val < b.val:
            cur.next = a; a = a.next
        else:
            cur.next = b; b = b.next
        cur = cur.next
    cur.next = a or b
    return dummy.next

43. Merge K Sorted Lists

Brute force: collect all + sort, O(N log N)

def mergeKLists(lists):
    vals = []
    for h in lists:
        while h: vals.append(h.val); h = h.next
    dummy = cur = ListNode(0)
    for v in sorted(vals):
        cur.next = ListNode(v); cur = cur.next
    return dummy.next

Optimal: min-heap, O(N log k)

import heapq
def mergeKLists(lists):
    heap = []
    for i, h in enumerate(lists):
        if h: heapq.heappush(heap, (h.val, i, h))
    dummy = cur = ListNode(0)
    while heap:
        v, i, n = heapq.heappop(heap)
        cur.next = n; cur = n
        if n.next:
            heapq.heappush(heap, (n.next.val, i, n.next))
    return dummy.next

44. Remove Nth Node From End

Brute force: two passes, O(n)

def removeNthFromEnd(head, n):
    length = 0; cur = head
    while cur: length += 1; cur = cur.next
    dummy = ListNode(0, head); cur = dummy
    for _ in range(length - n): cur = cur.next
    cur.next = cur.next.next
    return dummy.next

Optimal: one pass two pointers, O(n) / O(1)

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    slow = fast = dummy
    for _ in range(n + 1): fast = fast.next
    while fast:
        slow, fast = slow.next, fast.next
    slow.next = slow.next.next
    return dummy.next

45. Reorder List

L0→L1→...→Ln-1→Ln → L0→Ln→L1→Ln-1→...

Brute force: array indexing, O(n) / O(n)

def reorderList(head):
    arr = []
    cur = head
    while cur: arr.append(cur); cur = cur.next
    l, r = 0, len(arr) - 1
    while l < r:
        arr[l].next = arr[r]
        l += 1
        if l == r: break
        arr[r].next = arr[l]
        r -= 1
    arr[l].next = None

Optimal: mid + reverse + merge, O(n) / O(1)

def reorderList(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    prev, cur = None, slow.next
    slow.next = None
    while cur:
        cur.next, prev, cur = prev, cur, cur.next
    a, b = head, prev
    while b:
        a.next, b.next, a, b = b, a.next, a.next, b.next

Matrix

46. Set Matrix Zeroes

Predict the pattern

Brute force: copy matrix, O(mn) / O(mn)

def setZeroes(m):
    rows, cols = set(), set()
    for i in range(len(m)):
        for j in range(len(m[0])):
            if m[i][j] == 0: rows.add(i); cols.add(j)
    for i in range(len(m)):
        for j in range(len(m[0])):
            if i in rows or j in cols: m[i][j] = 0

Optimal: first row/col as flags, O(mn) / O(1)

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    first_row = any(matrix[0][j] == 0 for j in range(n))
    first_col = any(matrix[i][0] == 0 for i in range(m))
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = matrix[0][j] = 0
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    if first_row:
        for j in range(n): matrix[0][j] = 0
    if first_col:
        for i in range(m): matrix[i][0] = 0

47. Spiral Matrix

Brute force = optimal: layer walking, O(mn).

def spiralOrder(matrix):
    res = []
    while matrix:
        res += matrix.pop(0)
        matrix = list(zip(*matrix))[::-1]
    return res

Cleaner pointer version:

def spiralOrder(matrix):
    res = []
    top, bot = 0, len(matrix) - 1
    lft, rgt = 0, len(matrix[0]) - 1
    while top <= bot and lft <= rgt:
        for j in range(lft, rgt + 1): res.append(matrix[top][j])
        top += 1
        for i in range(top, bot + 1): res.append(matrix[i][rgt])
        rgt -= 1
        if top <= bot:
            for j in range(rgt, lft - 1, -1): res.append(matrix[bot][j])
            bot -= 1
        if lft <= rgt:
            for i in range(bot, top - 1, -1): res.append(matrix[i][lft])
            lft += 1
    return res

48. Rotate Image (90° clockwise, in place)

Brute force: copy to new matrix, O(n²) / O(n²)

def rotate(m):
    n = len(m)
    tmp = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            tmp[j][n - 1 - i] = m[i][j]
    for i in range(n):
        m[i] = tmp[i]

Optimal: transpose + reverse rows, O(n²) / O(1)

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]
    for row in m:
        row.reverse()

49. Word Search

Brute force = standard DFS backtracking, O(mn·4^L)

def exist(board, word):
    m, n = len(board), len(board[0])
    def dfs(i, j, k):
        if k == len(word): return True
        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[k]:
            return False
        board[i][j] = '#'
        found = any(dfs(i + di, j + dj, k + 1)
                    for di, dj in ((1,0),(-1,0),(0,1),(0,-1)))
        board[i][j] = word[k]
        return found
    return any(dfs(i, j, 0) for i in range(m) for j in range(n))

Optimal: same DFS + start-cell pruning by frequency Reverse word if the last char is rarer than the first, so DFS prunes earlier.

def exist(board, word):
    from collections import Counter
    cnt = Counter(c for row in board for c in row)
    if Counter(word) - cnt: return False
    if cnt[word[0]] > cnt[word[-1]]: word = word[::-1]
    # then same DFS as brute force
    ...

String

50. Longest Substring Without Repeating Characters

Predict the pattern

Brute force: O(n³) check every substring.

def lengthOfLongestSubstring(s):
    best = 0
    for i in range(len(s)):
        for j in range(i, len(s)):
            if len(set(s[i:j + 1])) == j - i + 1:
                best = max(best, j - i + 1)
    return best

Optimal: sliding window, O(n)

def lengthOfLongestSubstring(s):
    last, l, best = {}, 0, 0
    for r, c in enumerate(s):
        if c in last and last[c] >= l:
            l = last[c] + 1
        last[c] = r
        best = max(best, r - l + 1)
    return best

51. Longest Repeating Character Replacement

At most k replacements; longest single-letter run.

Brute force: O(n²·26) try each window.

Optimal: sliding window, O(n) Window valid if (window_len − max_count) ≤ k.

def characterReplacement(s, k):
    from collections import Counter
    cnt = Counter(); l = best = max_f = 0
    for r, c in enumerate(s):
        cnt[c] += 1
        max_f = max(max_f, cnt[c])
        if r - l + 1 - max_f > k:
            cnt[s[l]] -= 1; l += 1
        best = max(best, r - l + 1)
    return best

52. Minimum Window Substring

Smallest window of s containing all chars of t.

Brute force: O(n²) every substring, check containment.

Optimal: sliding window, O(n + m)

from collections import Counter
def minWindow(s, t):
    need = Counter(t); missing = len(t)
    l = best_l = 0; best = ""
    for r, c in enumerate(s, 1):
        if need[c] > 0: missing -= 1
        need[c] -= 1
        if missing == 0:
            while need[s[l]] < 0:
                need[s[l]] += 1; l += 1
            if not best or r - l < len(best):
                best = s[l:r]
            need[s[l]] += 1; missing += 1; l += 1
    return best

53. Valid Anagram

Brute force: sort both, O(n log n)

def isAnagram(s, t):
    return sorted(s) == sorted(t)

Optimal: counter, O(n)

from collections import Counter
def isAnagram(s, t):
    return Counter(s) == Counter(t)

54. Group Anagrams

Brute force: pairwise compare, O(n²·k)

def groupAnagrams(strs):
    out = []
    used = [False] * len(strs)
    for i, s in enumerate(strs):
        if used[i]: continue
        group = [s]; used[i] = True
        for j in range(i + 1, len(strs)):
            if not used[j] and sorted(strs[j]) == sorted(s):
                group.append(strs[j]); used[j] = True
        out.append(group)
    return out

Optimal: hash by sorted key, O(n·k log k)

from collections import defaultdict
def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        groups[''.join(sorted(s))].append(s)
    return list(groups.values())

55. Valid Parentheses

Brute force: repeated replace, O(n²)

def isValid(s):
    while '()' in s or '[]' in s or '{}' in s:
        s = s.replace('()', '').replace('[]', '').replace('{}', '')
    return s == ''

Optimal: stack, O(n)

def isValid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for c in s:
        if c in pairs:
            if not stack or stack.pop() != pairs[c]: return False
        else:
            stack.append(c)
    return not stack

56. Valid Palindrome

Brute force: clean + reverse, O(n) / O(n)

def isPalindrome(s):
    cleaned = [c.lower() for c in s if c.isalnum()]
    return cleaned == cleaned[::-1]

Optimal: two pointers, O(n) / O(1)

def isPalindrome(s):
    l, r = 0, len(s) - 1
    while l < r:
        while l < r and not s[l].isalnum(): l += 1
        while l < r and not s[r].isalnum(): r -= 1
        if s[l].lower() != s[r].lower(): return False
        l += 1; r -= 1
    return True

57. Longest Palindromic Substring

Brute force: O(n³) check every substring.

def longestPalindrome(s):
    best = ""
    for i in range(len(s)):
        for j in range(i, len(s)):
            sub = s[i:j + 1]
            if sub == sub[::-1] and len(sub) > len(best):
                best = sub
    return best

Optimal: expand around center, O(n²) / O(1)

def longestPalindrome(s):
    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1
        return s[l + 1:r]
    best = ""
    for i in range(len(s)):
        for cand in (expand(i, i), expand(i, i + 1)):
            if len(cand) > len(best): best = cand
    return best

(Manacher's O(n) is the textbook fastest but rarely required.)

58. Palindromic Substrings (count)

Brute force: O(n³)

def countSubstrings(s):
    c = 0
    for i in range(len(s)):
        for j in range(i, len(s)):
            sub = s[i:j + 1]
            if sub == sub[::-1]: c += 1
    return c

Optimal: expand around center, O(n²) / O(1)

def countSubstrings(s):
    def count(l, r):
        c = 0
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1; r += 1; c += 1
        return c
    return sum(count(i, i) + count(i, i + 1) for i in range(len(s)))

59. Encode and Decode Strings

Brute force: pick a separator not in any string (fragile).

Optimal: length-prefix encoding

def encode(strs):
    return ''.join(f"{len(s)}#{s}" for s in strs)

def decode(s):
    res, i = [], 0
    while i < len(s):
        j = s.index('#', i)
        n = int(s[i:j])
        res.append(s[j + 1:j + 1 + n])
        i = j + 1 + n
    return res

Tree

60. Maximum Depth of Binary Tree

Predict the pattern

Brute force = optimal: DFS recursion, O(n).

def maxDepth(root):
    if not root: return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

BFS variant:

from collections import deque
def maxDepth(root):
    if not root: return 0
    q = deque([root]); d = 0
    while q:
        d += 1
        for _ in range(len(q)):
            n = q.popleft()
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
    return d

61. Same Tree

Brute force = optimal: recursive compare, O(n).

def isSameTree(p, q):
    if not p and not q: return True
    if not p or not q or p.val != q.val: return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

62. Invert Binary Tree

Brute force = optimal, O(n).

def invertTree(root):
    if not root: return None
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

63. Binary Tree Maximum Path Sum

Brute force: for each node, compute best path through it, O(n²)

def maxPathSum(root):
    best = float('-inf')
    def max_arm(n):
        if not n: return 0
        return max(0, n.val + max(max_arm(n.left), max_arm(n.right)))
    def dfs(n):
        nonlocal best
        if not n: return
        best = max(best, n.val + max_arm(n.left) + max_arm(n.right))
        dfs(n.left); dfs(n.right)
    dfs(root)
    return best

Optimal: single DFS, O(n)

def maxPathSum(root):
    best = float('-inf')
    def dfs(n):
        nonlocal best
        if not n: return 0
        l = max(0, dfs(n.left))
        r = max(0, dfs(n.right))
        best = max(best, n.val + l + r)
        return n.val + max(l, r)
    dfs(root)
    return best

64. Binary Tree Level Order Traversal

Brute force: DFS with level index, O(n)

def levelOrder(root):
    res = []
    def dfs(n, d):
        if not n: return
        if d == len(res): res.append([])
        res[d].append(n.val)
        dfs(n.left, d + 1); dfs(n.right, d + 1)
    dfs(root, 0)
    return res

Optimal: BFS, O(n)

from collections import deque
def levelOrder(root):
    if not root: return []
    q, res = deque([root]), []
    while q:
        level = []
        for _ in range(len(q)):
            n = q.popleft(); level.append(n.val)
            if n.left: q.append(n.left)
            if n.right: q.append(n.right)
        res.append(level)
    return res

65. Serialize and Deserialize Binary Tree

Brute force: store inorder + preorder, then rebuild, O(n²) rebuild.

Optimal: preorder w/ null markers, O(n)

class Codec:
    def serialize(self, root):
        out = []
        def dfs(n):
            if not n: out.append('#'); return
            out.append(str(n.val)); dfs(n.left); dfs(n.right)
        dfs(root)
        return ','.join(out)

    def deserialize(self, data):
        it = iter(data.split(','))
        def build():
            v = next(it)
            if v == '#': return None
            n = TreeNode(int(v))
            n.left = build(); n.right = build()
            return n
        return build()

66. Subtree of Another Tree

Brute force: for each node, run sameTree, O(m·n)

def isSubtree(root, sub):
    def same(a, b):
        if not a and not b: return True
        if not a or not b or a.val != b.val: return False
        return same(a.left, b.left) and same(a.right, b.right)
    if not root: return False
    return same(root, sub) or isSubtree(root.left, sub) or isSubtree(root.right, sub)

Optimal: serialize + substring, O(m+n)

def isSubtree(root, sub):
    def ser(n):
        if not n: return '#'
        return f'^{n.val},{ser(n.left)},{ser(n.right)}'
    return ser(sub) in ser(root)

67. Build Tree from Preorder + Inorder

Brute force: O(n²): linear search for root each call.

def buildTree(preorder, inorder):
    if not preorder: return None
    root = TreeNode(preorder[0])
    i = inorder.index(preorder[0])
    root.left = buildTree(preorder[1:1 + i], inorder[:i])
    root.right = buildTree(preorder[1 + i:], inorder[i + 1:])
    return root

Optimal: index map + pointers, O(n)

def buildTree(preorder, inorder):
    idx = {v: i for i, v in enumerate(inorder)}
    self_i = 0
    def build(l, r):
        nonlocal self_i
        if l > r: return None
        v = preorder[self_i]; self_i += 1
        n = TreeNode(v)
        n.left = build(l, idx[v] - 1)
        n.right = build(idx[v] + 1, r)
        return n
    return build(0, len(inorder) - 1)

68. Validate BST

Brute force: for each node verify whole subtree, O(n²)

Optimal: inorder traversal must be strictly increasing, O(n)

def isValidBST(root):
    prev = float('-inf'); ok = True
    def dfs(n):
        nonlocal prev, ok
        if not n or not ok: return
        dfs(n.left)
        if n.val <= prev: ok = False; return
        prev = n.val
        dfs(n.right)
    dfs(root)
    return ok

Or with bounds:

def isValidBST(root, lo=float('-inf'), hi=float('inf')):
    if not root: return True
    if not lo < root.val < hi: return False
    return (isValidBST(root.left, lo, root.val) and
            isValidBST(root.right, root.val, hi))

69. Kth Smallest in BST

Brute force: collect inorder, return k-1, O(n) / O(n)

def kthSmallest(root, k):
    arr = []
    def dfs(n):
        if not n: return
        dfs(n.left); arr.append(n.val); dfs(n.right)
    dfs(root)
    return arr[k - 1]

Optimal: iterative inorder, stop at k, O(h+k)

def kthSmallest(root, k):
    stack = []
    while True:
        while root:
            stack.append(root); root = root.left
        root = stack.pop()
        k -= 1
        if k == 0: return root.val
        root = root.right

70. LCA of BST

Brute force: find paths, compare, O(n)

Optimal: descend by BST property, O(h)

def lowestCommonAncestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root

71. Implement Trie

Brute force: store all words in a set, O(L) per op but no prefix search.

Optimal: trie nodes, O(L) per op

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        cur = self.root
        for c in word:
            cur = cur.setdefault(c, {})
        cur['$'] = True

    def search(self, word):
        cur = self.root
        for c in word:
            if c not in cur: return False
            cur = cur[c]
        return '$' in cur

    def startsWith(self, prefix):
        cur = self.root
        for c in prefix:
            if c not in cur: return False
            cur = cur[c]
        return True

72. Add and Search Word (`.` wildcard)

Brute force: list of words; on search, regex match each, O(N·L) per query.

Optimal: trie + DFS for ., O(L) avg / O(26^L) worst

class WordDictionary:
    def __init__(self):
        self.root = {}

    def addWord(self, word):
        cur = self.root
        for c in word:
            cur = cur.setdefault(c, {})
        cur['$'] = True

    def search(self, word):
        def dfs(node, i):
            if i == len(word): return '$' in node
            c = word[i]
            if c == '.':
                return any(k != '$' and dfs(node[k], i + 1) for k in node)
            return c in node and dfs(node[c], i + 1)
        return dfs(self.root, 0)

73. Word Search II

Brute force: Word Search per word, O(W·mn·4^L)

Optimal: single DFS using trie of words, O(mn·4^L)

def findWords(board, words):
    root = {}
    for w in words:
        cur = root
        for c in w:
            cur = cur.setdefault(c, {})
        cur['$'] = w

    m, n = len(board), len(board[0])
    res = []
    def dfs(i, j, node):
        c = board[i][j]
        if c not in node: return
        nxt = node[c]
        if '$' in nxt:
            res.append(nxt.pop('$'))
        board[i][j] = '#'
        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n:
                dfs(ni, nj, nxt)
        board[i][j] = c
    for i in range(m):
        for j in range(n):
            dfs(i, j, root)
    return res

Heap

74. Top K Frequent Elements

Predict the pattern

Brute force: count + sort, O(n log n)

from collections import Counter
def topKFrequent(nums, k):
    return [x for x, _ in Counter(nums).most_common(k)]

Optimal: bucket sort, O(n)

from collections import Counter
def topKFrequent(nums, k):
    cnt = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for x, c in cnt.items():
        buckets[c].append(x)
    res = []
    for c in range(len(buckets) - 1, 0, -1):
        for x in buckets[c]:
            res.append(x)
            if len(res) == k: return res

(Or min-heap of size k → O(n log k).)

75. Find Median from Data Stream

Brute force: keep sorted list, O(n) insert / O(1) median

import bisect
class MedianFinder:
    def __init__(self):
        self.arr = []
    def addNum(self, n):
        bisect.insort(self.arr, n)
    def findMedian(self):
        n = len(self.arr); m = n // 2
        return self.arr[m] if n % 2 else (self.arr[m - 1] + self.arr[m]) / 2

Optimal: two heaps, O(log n) insert / O(1) median Left = max-heap (lower half), right = min-heap (upper half).

import heapq
class MedianFinder:
    def __init__(self):
        self.lo = []   # max-heap (store negatives)
        self.hi = []   # min-heap

    def addNum(self, n):
        heapq.heappush(self.lo, -n)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))

    def findMedian(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Quick reference table

#	Problem	Optimal time	Key trick
1	Two Sum	O(n)	hash complement
2	Best Time Buy/Sell	O(n)	running min
3	Contains Duplicate	O(n)	set
4	Product Except Self	O(n)	prefix × suffix
5	Max Subarray	O(n)	Kadane
6	Max Product Subarray	O(n)	min+max DP
7	Min in Rotated	O(log n)	binary search
8	Search Rotated	O(log n)	binary search
9	3Sum	O(n²)	sort + 2 ptrs
10	Container Water	O(n)	2 ptrs
11	Sum 2 Ints	O(1)	XOR + carry
12	Number of 1 Bits	O(b)	n & (n-1)
13	Counting Bits	O(n)	dp[i>>1]
14	Missing Number	O(n)	gauss sum
15	Reverse Bits	O(32)	shift loop
16	Climb Stairs	O(n)	fib
17	Coin Change	O(amt·k)	DP
18	LIS	O(n log n)	patience
19	LCS	O(mn)	2D DP
20	Word Break	O(n²)	DP + set
21	Combination Sum	O(2^n)	backtrack
22	House Robber	O(n)	rolling DP
23	House Robber II	O(n)	run I twice
24	Decode Ways	O(n)	DP
25	Unique Paths	O(mn)	DP / C(n,k)
26	Jump Game	O(n)	greedy reach
27	Clone Graph	O(V+E)	DFS+map
28	Course Schedule	O(V+E)	Kahn topo
29	Pac Atl Water	O(mn)	reverse BFS
30	Num Islands	O(mn)	flood fill
31	Longest Consec	O(n)	set starts
32	Alien Dict	O(C)	topo sort
33	Valid Tree	O(n α)	union-find
34	Connected Comp	O(n α)	union-find
35	Insert Interval	O(n)	3 phase
36	Merge Intervals	O(n log n)	sort sweep
37	Non-overlap	O(n log n)	greedy end
38	Meeting Rooms	O(n log n)	sort
39	Meeting Rooms II	O(n log n)	min-heap
40	Reverse List	O(n)	iter prev
41	Cycle Detect	O(n)	Floyd
42	Merge 2 Lists	O(n)	2 ptrs
43	Merge K Lists	O(N log k)	heap
44	Remove Nth End	O(n)	2 ptrs offset
45	Reorder List	O(n)	mid+rev+merge
46	Set Zeroes	O(mn)	first row/col
47	Spiral Matrix	O(mn)	layer walk
48	Rotate Image	O(n²)	transpose+rev
49	Word Search	O(mn·4^L)	DFS+backtrack
50	Longest Sub No Rep	O(n)	sliding window
51	Char Replacement	O(n)	window+max-cnt
52	Min Window Sub	O(n)	window + counts
53	Valid Anagram	O(n)	counter
54	Group Anagrams	O(nk log k)	sort-key hash
55	Valid Parens	O(n)	stack
56	Valid Palindrome	O(n)	2 ptrs
57	Longest Palin Sub	O(n²)	expand center
58	Count Palindromes	O(n²)	expand center
59	Encode/Decode Str	O(n)	length-prefix
60	Max Depth	O(n)	DFS
61	Same Tree	O(n)	DFS
62	Invert Tree	O(n)	swap rec
63	Max Path Sum	O(n)	DFS + nonlocal
64	Level Order	O(n)	BFS
65	Serialize Tree	O(n)	preorder + #
66	Subtree	O(m+n)	serialize match
67	Build from Pre+In	O(n)	inorder index
68	Valid BST	O(n)	inorder mono
69	Kth Smallest BST	O(h+k)	iter inorder
70	LCA of BST	O(h)	BST descent
71	Trie	O(L)	dict of dicts
72	Add+Search Word	O(L)	trie + DFS
73	Word Search II	O(mn·4^L)	trie + DFS
74	Top K Frequent	O(n)	bucket sort
75	Median Stream	O(log n)	2 heaps

Array

1. Two Sum

2. Best Time to Buy and Sell Stock

3. Contains Duplicate

4. Product of Array Except Self

5. Maximum Subarray

6. Maximum Product Subarray

7. Find Minimum in Rotated Sorted Array

8. Search in Rotated Sorted Array

9. 3 Sum

10. Container With Most Water

Binary

11. Sum of Two Integers (no +/-)

12. Number of 1 Bits

13. Counting Bits

14. Missing Number

15. Reverse Bits

Dynamic Programming

16. Climbing Stairs

17. Coin Change

18. Longest Increasing Subsequence

19. Longest Common Subsequence

20. Word Break

21. Combination Sum

22. House Robber

23. House Robber II

24. Decode Ways

25. Unique Paths

26. Jump Game

Graph

27. Clone Graph

28. Course Schedule

29. Pacific Atlantic Water Flow

30. Number of Islands

31. Longest Consecutive Sequence

32. Alien Dictionary

33. Graph Valid Tree

34. Number of Connected Components

Interval

35. Insert Interval

36. Merge Intervals

37. Non-overlapping Intervals

38. Meeting Rooms

39. Meeting Rooms II

Linked List

40. Reverse Linked List

41. Detect Cycle

42. Merge Two Sorted Lists

43. Merge K Sorted Lists

44. Remove Nth Node From End

45. Reorder List

Matrix

46. Set Matrix Zeroes

47. Spiral Matrix

48. Rotate Image (90° clockwise, in place)

49. Word Search

String

50. Longest Substring Without Repeating Characters

51. Longest Repeating Character Replacement

52. Minimum Window Substring

53. Valid Anagram

54. Group Anagrams

55. Valid Parentheses

56. Valid Palindrome

57. Longest Palindromic Substring

58. Palindromic Substrings (count)

59. Encode and Decode Strings

Tree

60. Maximum Depth of Binary Tree

61. Same Tree

62. Invert Binary Tree

63. Binary Tree Maximum Path Sum

64. Binary Tree Level Order Traversal

65. Serialize and Deserialize Binary Tree

66. Subtree of Another Tree

67. Build Tree from Preorder + Inorder

68. Validate BST

69. Kth Smallest in BST

70. LCA of BST

71. Implement Trie

11. Sum of Two Integers (no `+`/`-`)

72. Add and Search Word (`.` wildcard)