FAANG Practice Problems

Approach 2 — Hash Map (one pass)

For each element x, look up target - x. Store value -> index as you go so you only scan once.

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

Hash lookup is amortized O(1), so a single scan suffices.

Approach 2 — Sliding Window with Last-Seen Map

Keep left as window start. For each right, if s[right] was seen at index k >= left, jump left = k + 1. Else update best.

def length_of_longest(s):
    last = {}
    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

Each char enters and exits the window at most once.

Approach 2 — Two Pointers

Start at both ends. The shorter wall caps the area; moving it inward is the only move that could improve things.

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

Inward move on the shorter side is the greedy invariant.

Approach 3 — Two Pointers (O(1) memory)

Whichever side has the smaller running max is the binding constraint on the other side's cell.

def trap(h):
    l, r = 0, len(h) - 1
    lmax = rmax = ans = 0
    while l < r:
        if h[l] < h[r]:
            if h[l] >= lmax: lmax = h[l]
            else:            ans += lmax - h[l]
            l += 1
        else:
            if h[r] >= rmax: rmax = h[r]
            else:            ans += rmax - h[r]
            r -= 1
    return ans

Two pointers replace the prefix arrays once we realize only the smaller side matters.

Approach 2 — Sort + Two Pointers

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

sort then fix one element and two-pointer the rest.

Approach — Kadane (DP collapsed)

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

At each step, decide: extend the prior positive-sum window, or restart at x.

Approach — Two Passes with Running Products

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

(output array excluded from space by convention).

Approach 2 — Expand Around Center

def longest_palindrome(s):
    def grow(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 p in (grow(i, i), grow(i, i+1)):
            if len(p) > len(best): best = p
    return best

fastest path for practical n; Manacher is O(n) but rarely required live.

Approach — State Machine

INT_MIN, INT_MAX = -2**31, 2**31 - 1
def my_atoi(s):
    i, n = 0, len(s)
    while i < n and s[i] == ' ': i += 1
    sign = 1
    if i < n and s[i] in '+-':
        sign = -1 if s[i] == '-' else 1
        i += 1
    val = 0
    while i < n and s[i].isdigit():
        val = val * 10 + (ord(s[i]) - ord('0'))
        if val * sign >= INT_MAX: return INT_MAX
        if val * sign <= INT_MIN: return INT_MIN
        i += 1
    return val * sign

Approach — Transpose then Reverse Each Row

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

Clockwise = transpose + horizontal flip. Counter-clockwise = transpose + vertical flip.

Iterative Three-Pointer

def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Dummy + Carry

def add_two(l1, l2):
    dummy = tail = ListNode(0)
    carry = 0
    while l1 or l2 or carry:
        d1 = l1.val if l1 else 0
        d2 = l2.val if l2 else 0
        s = d1 + d2 + carry
        carry, digit = divmod(s, 10)
        tail.next = ListNode(digit); tail = tail.next
        if l1: l1 = l1.next
        if l2: l2 = l2.next
    return dummy.next

Approach 2 — Min-Heap of Heads

import heapq
def merge_k(lists):
    h = []
    for i, node in enumerate(lists):
        if node: heapq.heappush(h, (node.val, i, node))
    dummy = tail = ListNode(0)
    while h:
        _, i, node = heapq.heappop(h)
        tail.next = node; tail = node
        if node.next:
            heapq.heappush(h, (node.next.val, i, node.next))
    return dummy.next

Heap holds at most one node per list; tie-break on i to avoid comparing nodes.

Hash-Map + Doubly Linked List

class Node:
    __slots__ = ("k","v","prev","next")
    def __init__(self, k=0, v=0):
        self.k, self.v = k, v
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.m = {}
        self.head = Node()   # most-recent side
        self.tail = Node()   # least-recent side
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, k):
        if k not in self.m: return -1
        n = self.m[k]
        self._remove(n); self._add_front(n)
        return n.v

    def put(self, k, v):
        if k in self.m:
            n = self.m[k]; n.v = v
            self._remove(n); self._add_front(n); return
        if len(self.m) == self.cap:
            lru = self.tail.prev
            self._remove(lru); del self.m[lru.k]
        n = Node(k, v)
        self.m[k] = n; self._add_front(n)

HashMap indexes a doubly linked list so both update sites are O(1).

Approach 1 — Hash Map of Clones

def copy_random_list(head):
    if not head: return None
    m = {}
    cur = head
    while cur:
        m[cur] = Node(cur.val); cur = cur.next
    cur = head
    while cur:
        m[cur].next   = m.get(cur.next)
        m[cur].random = m.get(cur.random)
        cur = cur.next
    return m[head]

Find Middle, Reverse Tail, Merge

def reorder_list(head):
    if not head or not head.next: return
    # 1. middle
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next; fast = fast.next.next
    second = slow.next; slow.next = None
    # 2. reverse second half
    prev, curr = None, second
    while curr:
        nxt = curr.next; curr.next = prev
        prev = curr; curr = nxt
    # 3. weave
    first, second = head, prev
    while second:
        t1, t2 = first.next, second.next
        first.next = second
        second.next = t1
        first, second = t1, t2

three canonical sub-routines bolted together.

BFS with Level-Sized Loop

from collections import deque
def level_order(root):
    if not root: return []
    q = deque([root]); out = []
    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)
        out.append(level)
    return out

where w is max width.

Approach 2 — Bound Propagation

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

Post-Order One-Pass (Binary Tree)

def lca(root, p, q):
    if not root or root is p or root is q: return root
    l = lca(root.left, p, q)
    r = lca(root.right, p, q)
    if l and r: return root
    return l or r

Two non-null children means root is the split; else propagate the single found side.

Pre-Order with Null Sentinels

SEP, NULL = ",", "#"
def serialize(root):
    out = []
    def go(n):
        if not n: out.append(NULL); return
        out.append(str(n.val)); go(n.left); go(n.right)
    go(root)
    return SEP.join(out)

def deserialize(data):
    it = iter(data.split(SEP))
    def go():
        v = next(it)
        if v == NULL: return None
        n = TreeNode(int(v))
        n.left = go(); n.right = go()
        return n
    return go()

Pre-order lets the reader reconstruct via the same recursion pattern.

Post-Order, Track Global Max

def max_path_sum(root):
    best = [float('-inf')]
    def gain(n):
        if not n: return 0
        l = max(0, gain(n.left))
        r = max(0, gain(n.right))
        best[0] = max(best[0], n.val + l + r)
        return n.val + max(l, r)
    gain(root)
    return best[0]

The return value is the "extendable" half; the global includes both sides forking at the node.

DFS with Visited Map

def clone_graph(node):
    if not node: return None
    m = {}
    def dfs(u):
        if u in m: return m[u]
        c = Node(u.val); m[u] = c
        for v in u.neighbors: c.neighbors.append(dfs(v))
        return c
    return dfs(node)

Kahn's Algorithm (BFS over indegrees)

from collections import defaultdict, deque
def find_order(n, prerequisites):
    g = defaultdict(list); indeg = [0] * n
    for a, b in prerequisites:      # b -> a
        g[b].append(a); indeg[a] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    out = []
    while q:
        u = q.popleft(); out.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return out if len(out) == n else []   # [] = cycle

BFS over Pattern Buckets

from collections import defaultdict, deque
def ladder_length(begin, end, words):
    if end not in words: return 0
    buckets = defaultdict(list)
    L = len(begin)
    for w in words | {begin}:
        for i in range(L):
            buckets[w[:i]+"*"+w[i+1:]].append(w)
    q = deque([(begin, 1)]); seen = {begin}
    while q:
        w, d = q.popleft()
        if w == end: return d
        for i in range(L):
            key = w[:i]+"*"+w[i+1:]
            for nb in buckets[key]:
                if nb not in seen:
                    seen.add(nb); q.append((nb, d + 1))
            buckets[key] = []   # never revisit this bucket
    return 0

pattern bucketing collapses neighbours from O(N) to O(L).

DFS Flood-Fill

def num_islands(grid):
    if not grid: return 0
    R, C = len(grid), len(grid[0])
    def dfs(r, c):
        if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] != '1': return
        grid[r][c] = '0'
        dfs(r+1,c); dfs(r-1,c); dfs(r,c+1); dfs(r,c-1)
    cnt = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == '1':
                cnt += 1; dfs(r, c)
    return cnt

worst-case recursion.

Reverse BFS from Each Ocean

def pacific_atlantic(h):
    if not h: return []
    R, C = len(h), len(h[0])
    pac, atl = set(), set()
    def dfs(r, c, visited):
        visited.add((r, c))
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r+dr, c+dc
            if 0 <= nr < R and 0 <= nc < C and (nr,nc) not in visited and h[nr][nc] >= h[r][c]:
                dfs(nr, nc, visited)
    for c in range(C): dfs(0, c, pac); dfs(R-1, c, atl)
    for r in range(R): dfs(r, 0, pac); dfs(r, C-1, atl)
    return [list(p) for p in pac & atl]

reverse flow lets you avoid recomputing per-cell.

Build Edges from Adjacent Pair, Then Topo Sort

from collections import defaultdict, deque
def alien_order(words):
    g = defaultdict(set); indeg = {c: 0 for w in words for c in w}
    for a, b in zip(words, words[1:]):
        for x, y in zip(a, b):
            if x != y:
                if y not in g[x]:
                    g[x].add(y); indeg[y] += 1
                break
        else:
            if len(a) > len(b): return ""    # invalid prefix case
    q = deque(c for c, d in indeg.items() if d == 0)
    out = []
    while q:
        c = q.popleft(); out.append(c)
        for n in g[c]:
            indeg[n] -= 1
            if indeg[n] == 0: q.append(n)
    return "".join(out) if len(out) == len(indeg) else ""

where C = total characters; letter alphabet is bounded so graph is tiny.

Fibonacci with O(1) Memory

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

Two-State DP

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

Approach 2 — Patience Sorting (Binary Search)

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

tails[i] = smallest possible tail of an increasing subseq of length i+1.

2-D DP

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

, can reduce to O(min(m,n)) with rolling rows.

Levenshtein DP

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i
    for j in range(n+1): dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j],    # delete
                                   dp[i][j-1],    # insert
                                   dp[i-1][j-1])  # substitute
    return dp[m][n]

.

Unbounded Knapsack DP

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a-c] + 1)
    return -1 if dp[amount] == INF else dp[amount]

DP on Prefix

def word_break(s, words):
    wset = set(words)
    n = len(s)
    dp = [False] * (n + 1); dp[0] = True
    max_len = max(map(len, wset), default=0)
    for i in range(1, n + 1):
        for j in range(max(0, i - max_len), i):
            if dp[j] and s[j:i] in wset:
                dp[i] = True; break
    return dp[n]

where L = longest dict word.

Subset-Sum with Bitset

def can_partition(nums):
    s = sum(nums)
    if s % 2: return False
    target = s // 2
    dp = 1  # bit 0 set = sum 0 reachable
    for x in nums:
        dp |= dp << x
    return (dp >> target) & 1 == 1

Python ints are arbitrary-precision so the bitset is a single integer.

2-D DP

def is_match(s, p):
    m, n = len(s), len(p)
    dp = [[False]*(n+1) for _ in range(m+1)]
    dp[0][0] = True
    for j in range(1, n+1):
        if p[j-1] == '*': dp[0][j] = dp[0][j-2]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if p[j-1] == '*':
                dp[i][j] = dp[i][j-2]  # zero copies
                if p[j-2] == '.' or p[j-2] == s[i-1]:
                    dp[i][j] |= dp[i-1][j]  # one more
            elif p[j-1] == '.' or p[j-1] == s[i-1]:
                dp[i][j] = dp[i-1][j-1]
    return dp[m][n]

Two-Variable DP

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

Fibonacci-shaped recurrence with zero/out-of-range guards.

Quick-Select (average linear)

import random
def quickselect(nums, k):
    k = len(nums) - k   # k-th largest = index k in ascending
    def select(l, r):
        pivot = nums[random.randint(l, r)]
        lo, hi = l, r
        i = l
        while i <= hi:
            if nums[i] < pivot: nums[lo], nums[i] = nums[i], nums[lo]; lo += 1; i += 1
            elif nums[i] > pivot: nums[hi], nums[i] = nums[i], nums[hi]; hi -= 1
            else: i += 1
        if k < lo: return select(l, lo - 1)
        if k > hi: return select(hi + 1, r)
        return nums[k]
    return select(0, len(nums) - 1)

Two Heaps

import heapq
class MedianFinder:
    def __init__(self):
        self.lo = []   # max-heap (negated)
        self.hi = []   # min-heap
    def add_num(self, x):
        heapq.heappush(self.lo, -x)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))
    def find_median(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Invariant: len(lo) == len(hi) or len(lo) == len(hi)+1, and every element in lo ≤ every element in hi.

Bucket Sort on Frequency

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

Frequencies are bounded by n, so buckets are dense.

Count-Based Formula

from collections import Counter
def least_interval(tasks, n):
    c = Counter(tasks).values()
    m = max(c)
    n_max = sum(1 for v in c if v == m)
    return max(len(tasks), (m - 1) * (n + 1) + n_max)

Place most-frequent first; count idles; formula falls out by counting "full frames" of size n+1.

Pair Each Element with Running Min

class MinStack:
    def __init__(self):
        self.st = []     # (value, running_min)
    def push(self, x):
        m = x if not self.st else min(x, self.st[-1][1])
        self.st.append((x, m))
    def pop(self): self.st.pop()
    def top(self): return self.st[-1][0]
    def getMin(self): return self.st[-1][1]

Monotonic Stack of Pending Indices

def daily_temperatures(T):
    n = len(T); out = [0]*n
    st = []
    for i, t in enumerate(T):
        while st and T[st[-1]] < t:
            j = st.pop()
            out[j] = i - j
        st.append(i)
    return out

Each index pushed and popped once.

Monotonic Increasing Stack + Sentinel

def largest_rectangle(h):
    st = []; best = 0
    h = h + [0]    # sentinel forces flush
    for i, x in enumerate(h):
        while st and h[st[-1]] > x:
            j = st.pop()
            left = st[-1] if st else -1
            best = max(best, h[j] * (i - left - 1))
        st.append(i)
    return best

When a bar is popped, the rectangle spanning from the previous stacked index to i is exactly its height×width.

Identify Sorted Half, Then Bisect

def search_rotated(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 sorted
            if a[lo] <= t < a[mid]: hi = mid - 1
            else:                    lo = mid + 1
        else:                    # right sorted
            if a[mid] < t <= a[hi]: lo = mid + 1
            else:                    hi = mid - 1
    return -1

Compare to Rightmost

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
        else:              hi = mid
    return a[lo]

Climb Upslope

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

With sentinels -∞ on either side, binary search on the slope is provably correct.

Binary Search on Rate

import math
def min_eating_speed(piles, h):
    def feasible(k):
        return sum(math.ceil(p / k) for p in piles) <= h
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid): hi = mid
        else:              lo = mid + 1
    return lo

where M = max pile.

Binary Search on Capacity

def ship_within_days(weights, D):
    def feasible(cap):
        days, cur = 1, 0
        for w in weights:
            if cur + w > cap: days += 1; cur = 0
            cur += w
        return days <= D
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid): hi = mid
        else:              lo = mid + 1
    return lo

Partition Binary Search

def find_median_sorted(A, B):
    if len(A) > len(B): A, B = B, A
    m, n = len(A), len(B)
    lo, hi = 0, m
    half = (m + n + 1) // 2
    while lo <= hi:
        i = (lo + hi) // 2
        j = half - i
        aL = float('-inf') if i == 0 else A[i-1]
        aR = float('inf')  if i == m else A[i]
        bL = float('-inf') if j == 0 else B[j-1]
        bR = float('inf')  if j == n else B[j]
        if aL <= bR and bL <= aR:
            if (m + n) % 2: return max(aL, bL)
            return (max(aL, bL) + min(aR, bR)) / 2
        if aL > bR: hi = i - 1
        else:       lo = i + 1

Binary search partitions A so that left-halves of A and B together are half of the merged array.

Binary Search on Max-Subarray-Sum

def split_array(nums, m):
    def feasible(cap):
        parts, cur = 1, 0
        for x in nums:
            if cur + x > cap: parts += 1; cur = 0
            cur += x
        return parts <= m
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid): hi = mid
        else:              lo = mid + 1
    return lo