Python Interview Questions

26 data structure implementations, then 200 problems: 64 easy, 102 medium, 34 hard. Each card has an example, the steps, short Python code, and the corner cases.

Data Structures · 26 implementations

Dynamic Array

Data StructureLinear

An array that grows on its own. Python list works this way. Build one with a fixed-size backing array.

Example

append 1, 2, 3 → capacity grows 1 → 2 → 4
a[1] → 2

How it works

Use a fixed array a, with n = items used and cap = slots.
On append, if n == cap, it means full. Copy into a new array twice as big.
Write at slot n and add 1 to n.
On pop, shrink to half when only a quarter is used.

append O(1) amortized · pop O(1) amortized · get O(1) · insert in middle O(n)

Pitfalls

Doubling, not adding a fixed amount, is what makes append O(1) amortized.
Shrink at 1/4, not 1/2, or a push and pop at the edge would resize every time.
Bounds check the index.

class DynArray:
    def __init__(self):
        self.cap, self.n, self.a = 1, 0, [None]

    def append(self, x):
        if self.n == self.cap:
            self._resize(2 * self.cap)
        self.a[self.n] = x
        self.n += 1

    def pop(self):
        if self.n == 0:
            raise IndexError("pop from empty array")
        self.n -= 1
        x, self.a[self.n] = self.a[self.n], None
        if 0 < self.n <= self.cap // 4:
            self._resize(self.cap // 2)
        return x

    def __getitem__(self, i):
        if not 0 <= i < self.n:
            raise IndexError(i)
        return self.a[i]

    def _resize(self, cap):
        b = [None] * cap
        b[:self.n] = self.a[:self.n]
        self.a, self.cap = b, cap

Stack

Data StructureLinear

Last in, first out (LIFO). Used for undo, bracket matching, DFS, and monotonic stack problems.

Example

push 1, push 2, pop → 2, peek → 1

How it works

Use a dynamic array. The end of the array is the top.
Push appends to the end.
Pop removes from the end.
Peek reads the last item.

push O(1) · pop O(1) · peek O(1) · Space O(n)

Pitfalls

Pop or peek on an empty stack, so raise or return None.
Never use the front of a list as the top. pop(0) is O(n).

class Stack:
    def __init__(self):
        self.a = []

    def push(self, x):
        self.a.append(x)

    def pop(self):
        if not self.a:
            raise IndexError("pop from empty stack")
        return self.a.pop()

    def peek(self):
        return self.a[-1] if self.a else None

    def __len__(self):
        return len(self.a)

Queue (Circular Buffer)

Data StructureLinear

First in, first out (FIFO). Used for BFS, task queues, and streaming. Build one on a fixed array that wraps around.

Example

cap 3: enqueue 1, 2, 3, dequeue → 1, enqueue 4 → it goes into the freed slot 0

How it works

Use a fixed array a, with head = index of the front and n = items stored.
Enqueue writes at (head + n) % cap.
Dequeue reads at head, then moves head = (head + 1) % cap.
The % cap makes the array wrap like a ring.

enqueue O(1) · dequeue O(1) · Space O(cap)

Pitfalls

Full vs empty: track n, since head == tail alone cannot tell them apart.
In Python, use collections.deque, not list.pop(0).

class CircularQueue:
    def __init__(self, cap):
        self.a, self.head, self.n = [None] * cap, 0, 0

    def enqueue(self, x):
        if self.n == len(self.a):
            raise OverflowError("queue is full")
        self.a[(self.head + self.n) % len(self.a)] = x
        self.n += 1

    def dequeue(self):
        if self.n == 0:
            raise IndexError("queue is empty")
        x, self.a[self.head] = self.a[self.head], None
        self.head = (self.head + 1) % len(self.a)
        self.n -= 1
        return x

Singly Linked List

Data StructureLinear

A chain of nodes. Each node holds a value and a pointer to the next node.

Example

push_front 2, push_front 1, append 3 → 1 → 2 → 3
remove 2 → 1 → 3

How it works

Use a node with val and next. Keep head.
Push front: the new node points to the old head.
Append: walk to the last node and link the new one. Keep a tail pointer to make it O(1).
Remove: use a dummy node before head, find the node before the target, and skip the target.

push_front O(1) · append O(n), O(1) with tail · find O(n) · remove O(n)

Pitfalls

Removing the head, so a dummy node keeps the code simple.
Empty list.
Losing the rest of the list when you relink.

class SNode:
    def __init__(self, val, next=None):
        self.val, self.next = val, next

class SinglyLinkedList:
    def __init__(self):
        self.head = None

    def push_front(self, val):
        self.head = SNode(val, self.head)

    def append(self, val):
        if not self.head:
            return self.push_front(val)
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = SNode(val)

    def remove(self, val):
        dummy = cur = SNode(None, self.head)
        while cur.next and cur.next.val != val:
            cur = cur.next
        if cur.next:
            cur.next = cur.next.next
        self.head = dummy.next

    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.val
            cur = cur.next

Doubly Linked List (Deque)

Data StructureLinear

Each node points to both the next and previous node. You can add or remove at both ends in O(1). This is how a deque and an LRU cache work.

Example

push_back 1, push_back 2, push_front 0 → 0 ⇄ 1 ⇄ 2
pop_back → 2

How it works

Use two sentinel nodes, head and tail, that are never removed.
Insert after a node: link the new node to both neighbors, then point both neighbors at it.
Unlink a node: point its prev and next at each other.
With sentinels, there are no special cases for an empty list.

push/pop at either end O(1) · unlink a known node O(1) · find O(n)

Pitfalls

Update all 4 pointers on insert.
Pop on empty.
Without sentinels, head and tail need extra if checks.

class DNode:
    def __init__(self, val=None):
        self.val, self.prev, self.next = val, None, None

class DoublyLinkedList:
    def __init__(self):
        self.head, self.tail = DNode(), DNode()  # sentinels
        self.head.next, self.tail.prev = self.tail, self.head
        self.n = 0

    def _insert_after(self, node, val):
        new, nxt = DNode(val), node.next
        new.prev, new.next = node, nxt
        node.next = nxt.prev = new
        self.n += 1
        return new

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev
        self.n -= 1
        return node.val

    def push_front(self, val):
        return self._insert_after(self.head, val)

    def push_back(self, val):
        return self._insert_after(self.tail.prev, val)

    def pop_front(self):
        if not self.n:
            raise IndexError("empty")
        return self._unlink(self.head.next)

    def pop_back(self):
        if not self.n:
            raise IndexError("empty")
        return self._unlink(self.tail.prev)

Skip List

Data StructureLinear

A sorted linked list with extra "express lanes" stacked on top. Search, insert, and delete take O(log n) on average. Redis sorted sets use it.

Example

Level 2: 1 ------> 7
Level 1: 1 --> 4 --> 7
Level 0: 1 → 3 → 4 → 6 → 7

How it works

Use nodes with an array next, index=level, val=next node on that level.
To search, start at the top level of head. Move right while the next key is smaller. Then drop down a level.
Record the last node on each level in update.
To insert, flip coins for the new node's height, then splice it in after update[i] on each level.

search O(log n) average · insert O(log n) average · delete O(log n) average · Space O(n) average

Pitfalls

Worst case is O(n), but very unlikely.
Cap the max level.
Levels above the current top must start from head.

import random

class SkipNode:
    def __init__(self, key, level):
        self.key, self.next = key, [None] * level

class SkipList:
    MAX = 16

    def __init__(self):
        self.head, self.level = SkipNode(None, self.MAX), 1

    def _path(self, key):
        update, n = [self.head] * self.MAX, self.head
        for lv in range(self.level - 1, -1, -1):
            while n.next[lv] and n.next[lv].key < key:
                n = n.next[lv]
            update[lv] = n
        return update

    def search(self, key):
        n = self._path(key)[0].next[0]
        return n is not None and n.key == key

    def insert(self, key):
        update, lv = self._path(key), 1
        while lv < self.MAX and random.random() < 0.5:
            lv += 1
        self.level = max(self.level, lv)
        node = SkipNode(key, lv)
        for i in range(lv):
            node.next[i], update[i].next[i] = update[i].next[i], node

    def delete(self, key):
        update = self._path(key)
        n = update[0].next[0]
        if n and n.key == key:
            for i in range(len(n.next)):
                update[i].next[i] = n.next[i]

Hash Map (Separate Chaining)

Data StructureHashing

Maps keys to values in O(1) on average. Each bucket holds a small list of the keys that hash there.

Example

put("a", 1), put("b", 2), get("a") → 1, remove("a"), get("a") → None

How it works

Use an array of buckets. Each bucket is a list of (key, val) pairs.
Bucket index is hash(key) % number of buckets.
Put: if the key is in the bucket, replace it. Else append it.
When size passes 0.75 × buckets, double the buckets and re-insert all pairs.

get/put/remove O(1) average · O(n) worst, all in one bucket · resize O(n), O(1) amortized

Pitfalls

Keys must be hashable and must not change.
Update in place on a repeat key, or you get duplicates.
Resize, or the chains grow long.

class HashMap:
    def __init__(self, cap=8):
        self.buckets, self.size = [[] for _ in range(cap)], 0

    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key, val):
        b = self._bucket(key)
        for i, (k, _) in enumerate(b):
            if k == key:
                b[i] = (key, val)
                return
        b.append((key, val))
        self.size += 1
        if self.size > 0.75 * len(self.buckets):
            pairs = [p for b in self.buckets for p in b]
            self.__init__(2 * len(self.buckets))
            for k, v in pairs:
                self.put(k, v)

    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default

    def remove(self, key):
        b = self._bucket(key)
        for i, (k, _) in enumerate(b):
            if k == key:
                b.pop(i)
                self.size -= 1
                return

Hash Map (Open Addressing)

Data StructureHashing

A hash map with no lists. All keys live in one array. On a clash, step to the next free slot (linear probing). Python's dict uses open addressing.

Example

cap 8: keys hashing to slot 3, 3, 4 land in slots 3, 4, 5

How it works

Use two arrays: keys and vals.
To find a key, start at hash(key) % cap. Step right until you find the key or an EMPTY slot.
Delete writes a GONE marker (tombstone), so later probes do not stop early.
Keep the table at most half full. Else double it and re-insert the live keys.

get/put/remove O(1) average · O(n) worst · Space O(cap)

Pitfalls

Deleting by writing EMPTY breaks probe chains, so use a tombstone.
Tombstones fill the table, so count them toward the resize.
Clustering gets bad above about 70% full.

class ProbeMap:
    EMPTY, GONE = object(), object()

    def __init__(self, cap=8):
        self.keys, self.vals, self.used = [self.EMPTY] * cap, [None] * cap, 0

    def _slot(self, key):
        cap, gone = len(self.keys), None
        i = hash(key) % cap
        while self.keys[i] is not self.EMPTY:
            if self.keys[i] is self.GONE:
                gone = i if gone is None else gone
            elif self.keys[i] == key:
                return i, True
            i = (i + 1) % cap
        return (i if gone is None else gone), False

    def put(self, key, val):
        if (self.used + 1) * 2 > len(self.keys):
            live = [(k, v) for k, v in zip(self.keys, self.vals)
                    if k is not self.EMPTY and k is not self.GONE]
            self.__init__(2 * len(self.keys))
            for k, v in live:
                self.put(k, v)
        i, found = self._slot(key)
        if not found and self.keys[i] is self.EMPTY:
            self.used += 1
        self.keys[i], self.vals[i] = key, val

    def get(self, key, default=None):
        i, found = self._slot(key)
        return self.vals[i] if found else default

    def remove(self, key):
        i, found = self._slot(key)
        if found:
            self.keys[i], self.vals[i] = self.GONE, None

Generic Tree (N-ary)

Data StructureTrees

A tree where each node can have any number of children. Used for file systems, org charts, and the DOM.

Example

A has children B, C, D. B has children E, F → preorder A B E F C D, height 3

How it works

Use a node with val and an array children.
Preorder: visit the node, then each child left to right.
Level order: use a queue. Each round holds one full level.
Height: 1 + the max height of the children.

traversal O(n) · height O(n) · Space O(h) recursion, O(w) for BFS

Pitfalls

A leaf has an empty children array, so use max(..., default=0).
Deep trees can hit Python's recursion limit.

from collections import deque

class NTreeNode:
    def __init__(self, val, children=None):
        self.val, self.children = val, children or []

def preorder_n(root):
    if not root:
        return []
    out = [root.val]
    for c in root.children:
        out += preorder_n(c)
    return out

def level_order_n(root):
    out, q = [], deque([root] if root else [])
    while q:
        out.append([n.val for n in q])
        q = deque(c for n in q for c in n.children)
    return out

def height_n(root):
    if not root:
        return 0
    return 1 + max((height_n(c) for c in root.children), default=0)

D10

Binary Tree (Linked Nodes)

Data StructureTrees

Each node has at most two children: left and right. Know the four traversals by heart.

Example

Tree [1, 2, 3, 4, 5] → pre 1 2 4 5 3, in 4 2 5 1 3, post 4 5 2 3 1, level 1 2 3 4 5

How it works

Preorder: node, left, right. Good for copying a tree.
Inorder: left, node, right. A BST gives sorted order.
Postorder: left, right, node. Good for deleting or for sizes.
Level order: use a queue for BFS.

each traversal O(n) · Space O(h) recursion, O(w) for BFS

Pitfalls

Empty tree.
Skewed tree makes h = n.
Build test trees from a level-order array with None gaps.

from collections import deque

def preorder(n):
    return [n.val] + preorder(n.left) + preorder(n.right) if n else []

def inorder_rec(n):
    return inorder_rec(n.left) + [n.val] + inorder_rec(n.right) if n else []

def postorder(n):
    return postorder(n.left) + postorder(n.right) + [n.val] if n else []

def level_order_vals(root):
    out, q = [], deque([root] if root else [])
    while q:
        n = q.popleft()
        out.append(n.val)
        q.extend(c for c in (n.left, n.right) if c)
    return out

def build_level(vals):
    nodes = [TreeNode(v) if v is not None else None for v in vals]
    kids = nodes[::-1]
    root = kids.pop() if kids else None
    for n in nodes:
        if n:
            if kids: n.left = kids.pop()
            if kids: n.right = kids.pop()
    return root

D11

Binary Tree as an Array

Data StructureTrees

Store a binary tree in a flat array with no pointers. Heaps and segment trees use this layout.

Example

[1, 2, 3, None, 5] → 1 is the root. 2 and 3 are its children. 5 is the right child of 2.

How it works

Use an array, index=node position, val=node value. None marks a gap.
Root is index 0.
Left child of i is 2i + 1. Right child is 2i + 2.
Parent of i is (i - 1) // 2.

child/parent lookup O(1) · traversal O(n) · Space O(2^h), wasteful for skewed trees

Pitfalls

Check i < len(a) before reading.
A skewed tree needs an array of size 2^h.
1-based layouts use 2i and 2i + 1 instead.

def left(i):
    return 2 * i + 1

def right(i):
    return 2 * i + 2

def parent(i):
    return (i - 1) // 2

def inorder_arr(a, i=0):
    if i >= len(a) or a[i] is None:
        return []
    return inorder_arr(a, left(i)) + [a[i]] + inorder_arr(a, right(i))

def height_arr(a, i=0):
    if i >= len(a) or a[i] is None:
        return 0
    return 1 + max(height_arr(a, left(i)), height_arr(a, right(i)))

D12

Binary Search Tree

Data StructureTrees

A binary tree where every left subtree is smaller and every right subtree is bigger. Search, insert, and delete follow one path.

Example

insert 5, 3, 8, 4 → inorder 3 4 5 8
delete 5 → root becomes 8

How it works

Search: go left if the key is smaller, right if bigger.
Insert: walk the same way and attach a new leaf.
Delete a node with 0 or 1 child: replace it with that child.
Delete a node with 2 children: copy in its inorder successor (smallest on the right), then delete the successor.

search/insert/delete O(h) · O(log n) balanced, O(n) skewed

Pitfalls

Sorted input makes a skewed tree. Use AVL or red-black to stay balanced.
Decide how to handle duplicates.
Delete of the root.

class BST:
    def __init__(self):
        self.root = None

    def search(self, key):
        n = self.root
        while n and n.val != key:
            n = n.left if key < n.val else n.right
        return n is not None

    def insert(self, key):
        self.root = self._ins(self.root, key)

    def _ins(self, n, key):
        if not n:
            return TreeNode(key)
        if key < n.val:
            n.left = self._ins(n.left, key)
        elif key > n.val:
            n.right = self._ins(n.right, key)
        return n

    def delete(self, key):
        self.root = self._del(self.root, key)

    def _del(self, n, key):
        if not n:
            return None
        if key < n.val:
            n.left = self._del(n.left, key)
        elif key > n.val:
            n.right = self._del(n.right, key)
        else:
            if not n.left:
                return n.right
            if not n.right:
                return n.left
            s = n.right
            while s.left:
                s = s.left
            n.val = s.val
            n.right = self._del(n.right, s.val)
        return n

D13

Binary Heap (Min-Heap)

Data StructureHeaps

A complete binary tree stored in an array. In a min-heap, every parent is at most its children, so the smallest item is at the top. It powers priority queues.

Example

push 5, 3, 8, 1 → array [1, 3, 8, 5]
pop → 1, then pop → 3

How it works

Use an array as a binary tree: children of i are 2i + 1 and 2i + 2.
Push: append at the end, then sift up. Swap with the parent while the parent is bigger.
Pop: swap the root with the last item, remove it, then sift down. Swap with the smaller child while a child is smaller.
For a max-heap, flip the comparisons.

push O(log n) · pop O(log n) · peek O(1) · build from array O(n)

Pitfalls

Pop on an empty heap.
Sift down must pick the smaller child.
A heap is not sorted. Only the top is known.

class MinHeap:
    def __init__(self):
        self.a = []

    def push(self, x):
        a = self.a
        a.append(x)
        i = len(a) - 1
        while i and a[(i - 1) // 2] > a[i]:
            p = (i - 1) // 2
            a[i], a[p] = a[p], a[i]
            i = p

    def pop(self):
        a = self.a
        if not a:
            raise IndexError("pop from empty heap")
        a[0], a[-1] = a[-1], a[0]
        top, i = a.pop(), 0
        while True:
            l, r, m = 2 * i + 1, 2 * i + 2, i
            if l < len(a) and a[l] < a[m]: m = l
            if r < len(a) and a[r] < a[m]: m = r
            if m == i:
                return top
            a[i], a[m] = a[m], a[i]
            i = m

    def peek(self):
        return self.a[0]

D14

Heaps in Python (heapq)

Data StructureHeaps

Python's heapq gives a min-heap on a plain list. Know the tricks for a max-heap, top k, and custom order.

Example

max-heap of [3, 1, 4] → push -x, pop gives -4 → 4
nlargest(2, [3, 1, 4]) → [4, 3]

How it works

Min-heap: heappush, heappop. h[0] is the smallest.
Max-heap: push -x and negate on pop.
Custom order: push tuples (priority, tiebreak, item).
Top k largest: keep a min-heap of size k. Pop the top when it grows past k.

heappush O(log n) · heappop O(log n) · heapify O(n) · top k O(n log k)

Pitfalls

Tuples compare item by item, so add a counter as a tiebreak when items cannot compare.
No decrease-key: push the new entry and skip stale ones on pop.

import heapq
from itertools import count

def max_heap_demo(nums):
    h = [-x for x in nums]
    heapq.heapify(h)
    return -heapq.heappop(h)

def top_k_largest(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)
    return sorted(h, reverse=True)

class PriorityQueue:
    def __init__(self):
        self.h, self.tie = [], count()

    def push(self, item, priority):
        heapq.heappush(self.h, (priority, next(self.tie), item))

    def pop(self):
        return heapq.heappop(self.h)[2]

D15

Graph (Adjacency List)

Data StructureGraphs

A set of nodes joined by edges. An adjacency list stores each node's neighbors. An adjacency matrix uses a V × V grid instead.

Example

edges 0-1, 0-2, 1-3 → adj = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}
BFS from 0 → 0 1 2 3

How it works

Use a hash map, key=node, val=list of (neighbor, weight).
Undirected: add the edge both ways.
BFS: use a queue and a hash set of seen nodes. Gives the shortest path in hops.
DFS: use a stack (or recursion) and a hash set of seen nodes.

add edge O(1) · BFS/DFS O(V + E) · Space O(V + E) list, O(V²) matrix

Pitfalls

Mark nodes seen when you push, not when you pop, in BFS.
Separate groups need a loop over all nodes.
Use a matrix only for dense graphs or O(1) edge checks.

from collections import defaultdict, deque

class Graph:
    def __init__(self, directed=False):
        self.adj, self.directed = defaultdict(list), directed

    def add_edge(self, u, v, w=1):
        self.adj[u].append((v, w))
        if not self.directed:
            self.adj[v].append((u, w))

    def bfs(self, s):
        seen, q, order = {s}, deque([s]), []
        while q:
            u = q.popleft()
            order.append(u)
            for v, _ in self.adj[u]:
                if v not in seen:
                    seen.add(v)
                    q.append(v)
        return order

    def dfs(self, s):
        seen, st, order = set(), [s], []
        while st:
            u = st.pop()
            if u in seen:
                continue
            seen.add(u)
            order.append(u)
            for v, _ in reversed(self.adj[u]):
                st.append(v)
        return order

D16

Trie with Delete

Data StructureTrees

A tree of chars for fast prefix lookups. Used for autocomplete and spell check.

Example

insert "car", "cat" → shared path c → a, then r and t
delete "car" → only "cat" is left

How it works

Use a node with a hash map, key=char, val=child node, and an end flag.
Insert: walk the chars, making nodes as needed. Set end at the last one.
Search: walk the chars. The word exists if the walk works and end is True.
Delete: clear end, then remove child nodes that have no children and no end, on the way back up.

insert/search/delete O(L), L = word length · Space O(total chars)

Pitfalls

A word that is a prefix of another, like "car" and "cart". Do not delete the shared nodes.
Empty string.

class TrieNode:
    def __init__(self):
        self.kids, self.end = {}, False

class TrieD:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        n = self.root
        for ch in word:
            n = n.kids.setdefault(ch, TrieNode())
        n.end = True

    def search(self, word):
        n = self.root
        for ch in word:
            n = n.kids.get(ch)
            if not n:
                return False
        return n.end

    def delete(self, word):
        def go(n, i):
            if i == len(word):
                n.end = False
            else:
                kid = n.kids.get(word[i])
                if kid and go(kid, i + 1):
                    del n.kids[word[i]]
            return not n.kids and not n.end
        go(self.root, 0)

D17

Union Find (Disjoint Set)

Data StructureGraphs

Tracks which items are in the same group. Supports find (which group?) and union (join two groups). Used for Kruskal and connected parts.

Example

n = 5: union(0,1), union(1,2) → find(2) == find(0), count = 3

How it works

Use an array parent, index=node, val=parent node. A root is its own parent.
Find: follow parents to the root. Path compression points nodes closer to the root as you go.
Union: find both roots. Hang the shorter tree (lower rank) under the taller one.
Lower count by 1 on each real union.

find/union O(α(n)), almost O(1) · Space O(n)

Pitfalls

Union of two items already in one group must not change the count.
Without rank and path compression, trees can become O(n) deep.

class UnionFind:
    def __init__(self, n):
        self.parent, self.rank, self.count = list(range(n)), [0] * n, n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1
        return True

D18

LRU Cache from Scratch

Data StructureDesign

Build an LRU cache without OrderedDict. Interviewers often ask for this version.

Example

cap 2: put(1), put(2), get(1), put(3) → key 2 is evicted

How it works

Use a hash map, key=key, val=node in a doubly linked list.
The list runs from least recent (front) to most recent (back). Use two sentinel nodes.
On get or put, unlink the node and move it to the back.
If size is over capacity, it means evict. Unlink the front node and delete its key from the map.

get O(1) · put O(1) · Space O(capacity)

Pitfalls

Store the key in the node, so eviction can delete it from the map.
Put on an existing key must update and move it.
Capacity 1.

class LNode:
    def __init__(self, key=None, val=None):
        self.key, self.val, self.prev, self.next = key, val, None, None

class LRUScratch:
    def __init__(self, cap):
        self.cap, self.map = cap, {}
        self.head, self.tail = LNode(), LNode()
        self.head.next, self.tail.prev = self.tail, self.head

    def _unlink(self, n):
        n.prev.next, n.next.prev = n.next, n.prev

    def _push_back(self, n):
        n.prev, n.next = self.tail.prev, self.tail
        self.tail.prev.next = self.tail.prev = n

    def get(self, key):
        if key not in self.map:
            return -1
        n = self.map[key]
        self._unlink(n)
        self._push_back(n)
        return n.val

    def put(self, key, val):
        if key in self.map:
            self._unlink(self.map[key])
        n = self.map[key] = LNode(key, val)
        self._push_back(n)
        if len(self.map) > self.cap:
            old = self.head.next
            self._unlink(old)
            del self.map[old.key]

D19

Sorted List with bisect

Data StructureLinear

Keep a list sorted so you can find counts, floors, and ceilings by binary search. A simple stand-in for a balanced BST or SortedList.

Example

add 5, 1, 3 → [1, 3, 5]
count_less(4) → 2
floor(4) → 3

How it works

Use a sorted array.
Add with insort, which binary searches the spot and shifts items.
bisect_left(a, x) = how many items are smaller than x.
Floor: the item just before bisect_right(a, x).

add O(n), from shifting · remove O(n) · count/floor/ceiling O(log n)

Pitfalls

Inserts are O(n), so for many updates use a balanced BST or sortedcontainers.
bisect_left vs bisect_right with duplicates.

from bisect import bisect_left, bisect_right, insort

class SortedArray:
    def __init__(self):
        self.a = []

    def add(self, x):
        insort(self.a, x)

    def remove(self, x):
        i = bisect_left(self.a, x)
        if i < len(self.a) and self.a[i] == x:
            self.a.pop(i)

    def count_less(self, x):
        return bisect_left(self.a, x)

    def floor(self, x):
        i = bisect_right(self.a, x)
        return self.a[i - 1] if i else None

    def ceiling(self, x):
        i = bisect_left(self.a, x)
        return self.a[i] if i < len(self.a) else None

D20

AVL Tree

Data StructureBalanced Trees

A self-balancing BST. At every node, the left and right heights differ by at most 1. So the height stays O(log n).

Example

insert 1, 2, 3 → a plain BST is a line. AVL rotates left at 1, so 2 becomes the root.

How it works

Store a height h in each node.
Insert like a BST, then on the way back up, update heights.
Balance = left height - right height. If above 1 or below -1, rotate.
Four cases: LL → rotate right. RR → rotate left. LR → rotate the child left, then the node right. RL → mirror.

search O(log n) · insert O(log n) · delete O(log n) · Space O(n)

Pitfalls

Update heights bottom-up after each rotation.
Pick the double rotation for zig-zag cases.
AVL is more strictly balanced than red-black, so lookups are a bit faster and inserts a bit slower.

class AVLNode:
    def __init__(self, key):
        self.key, self.left, self.right, self.h = key, None, None, 1

def avl_h(n):
    return n.h if n else 0

def avl_fix(n):
    n.h = 1 + max(avl_h(n.left), avl_h(n.right))

def rotate_right(y):
    x = y.left
    y.left, x.right = x.right, y
    avl_fix(y); avl_fix(x)
    return x

def rotate_left(x):
    y = x.right
    x.right, y.left = y.left, x
    avl_fix(x); avl_fix(y)
    return y

def avl_insert(n, key):
    if not n:
        return AVLNode(key)
    if key < n.key:
        n.left = avl_insert(n.left, key)
    else:
        n.right = avl_insert(n.right, key)
    avl_fix(n)
    bal = avl_h(n.left) - avl_h(n.right)
    if bal > 1:
        if key >= n.left.key:          # LR case
            n.left = rotate_left(n.left)
        return rotate_right(n)
    if bal < -1:
        if key < n.right.key:          # RL case
            n.right = rotate_right(n.right)
        return rotate_left(n)
    return n

D21

Red-Black Tree

Data StructureBalanced Trees

A self-balancing BST with a color on each node. The rules keep the longest path at most twice the shortest. Java TreeMap and C++ std::map use it.

Example

insert 10, 20, 30 → recolor and rotate → 20 is a black root, 10 and 30 are red

How it works

Rules: the root is black. A red node has no red child. Every root-to-leaf path has the same number of black nodes.
Insert like a BST and color the new node red.
If its parent is red, look at the uncle. Red uncle: recolor parent and uncle black, grandparent red, and move up.
Black uncle: rotate. First turn a zig-zag into a line, then rotate the grandparent and swap colors.

search O(log n) · insert O(log n), at most 2 rotations · delete O(log n) · Space O(n)

Pitfalls

Use a shared black NIL sentinel for leaves.
Always recolor the root black at the end.
Delete is much longer. Know the idea, not the code.

class RBNode:
    def __init__(self, key, color, nil=None):
        self.key, self.color = key, color
        self.left = self.right = self.parent = nil

class RBTree:
    def __init__(self):
        self.nil = RBNode(None, "B")
        self.root = self.nil

    def _rotate(self, x, a, b):
        # a="right" is a left rotation: x's right child moves up
        y = getattr(x, a)
        setattr(x, a, getattr(y, b))
        if getattr(y, b) is not self.nil:
            getattr(y, b).parent = x
        y.parent = x.parent
        if x.parent is self.nil:
            self.root = y
        elif x is x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        setattr(y, b, x)
        x.parent = y

    def insert(self, key):
        z = RBNode(key, "R", self.nil)
        y, x = self.nil, self.root
        while x is not self.nil:
            y, x = x, (x.left if key < x.key else x.right)
        z.parent = y
        if y is self.nil:
            self.root = z
        elif key < y.key:
            y.left = z
        else:
            y.right = z
        while z.parent.color == "R":
            p, g = z.parent, z.parent.parent
            a, b = ("left", "right") if p is g.left else ("right", "left")
            uncle = getattr(g, b)
            if uncle.color == "R":                # recolor
                p.color = uncle.color = "B"
                g.color = "R"
                z = g
            else:
                if z is getattr(p, b):            # zig-zag to line
                    z = p
                    self._rotate(z, b, a)
                    p = z.parent
                p.color, g.color = "B", "R"
                self._rotate(g, a, b)
        self.root.color = "B"

D22

B-Tree

Data StructureBalanced Trees

A balanced search tree where each node holds many sorted keys and has many children. Wide and shallow, so it needs few disk reads. Databases and file systems use B-trees and B+ trees.

Example

min degree t = 2 (up to 3 keys): insert 1 to 6 → root [2, 4], leaves [1] [3] [5, 6]

How it works

Each node holds between t - 1 and 2t - 1 sorted keys. A node with k keys has k + 1 children.
Search: binary search the keys in a node, then go down the right child.
Insert: go down to a leaf. Split any full node on the way, so there is always room.
Split: move the middle key up to the parent. The left and right halves become two nodes.

search O(log n) · insert O(log n) · Height O(log_t n) · Space O(n)

Pitfalls

A full root splits into a new root, which is the only way height grows.
B+ trees keep all values in the leaves and link the leaves for range scans.
Delete needs merge and borrow steps.

from bisect import bisect_left, bisect_right, insort

class BNode:
    def __init__(self, leaf=True):
        self.keys, self.kids, self.leaf = [], [], leaf

class BTree:
    def __init__(self, t=2):
        self.t, self.root = t, BNode()

    def search(self, k):
        n = self.root
        while True:
            i = bisect_left(n.keys, k)
            if i < len(n.keys) and n.keys[i] == k:
                return True
            if n.leaf:
                return False
            n = n.kids[i]

    def _split(self, parent, i):
        t, full = self.t, parent.kids[i]
        right = BNode(full.leaf)
        parent.keys.insert(i, full.keys[t - 1])
        parent.kids.insert(i + 1, right)
        right.keys, full.keys = full.keys[t:], full.keys[:t - 1]
        if not full.leaf:
            right.kids, full.kids = full.kids[t:], full.kids[:t]

    def insert(self, k):
        if len(self.root.keys) == 2 * self.t - 1:
            old, self.root = self.root, BNode(leaf=False)
            self.root.kids.append(old)
            self._split(self.root, 0)
        n = self.root
        while not n.leaf:
            i = bisect_right(n.keys, k)
            if len(n.kids[i].keys) == 2 * self.t - 1:
                self._split(n, i)
                if k > n.keys[i]:
                    i += 1
            n = n.kids[i]
        insort(n.keys, k)

D23

Segment Tree

Data StructureAdvanced

Answers range queries, like the sum of nums[l:r], and handles point updates. Both run in O(log n). Works for min, max, and gcd too.

Example

nums = [1, 3, 5] → query(0, 3) = 9
update(1, 2) → query(0, 2) = 3

How it works

Use an array t of size 2n, as a binary tree. Leaves sit at t[n:].
Each parent t[i] = t[2i] + t[2i + 1]. Build from the bottom up.
Update: set the leaf, then walk up and fix each parent.
Query [l, r): move l and r up level by level. Add a node when it is a right child on the left side, or a left child on the right side.

build O(n) · update O(log n) · query O(log n) · Space O(n)

Pitfalls

The range is half-open [l, r).
For min or max, change + and the start value.
Range updates need lazy propagation.

class SegTree:
    def __init__(self, nums):
        self.n = len(nums)
        self.t = [0] * self.n + list(nums)
        for i in range(self.n - 1, 0, -1):
            self.t[i] = self.t[2 * i] + self.t[2 * i + 1]

    def update(self, i, val):
        i += self.n
        self.t[i] = val
        while i > 1:
            i //= 2
            self.t[i] = self.t[2 * i] + self.t[2 * i + 1]

    def query(self, l, r):
        s, l, r = 0, l + self.n, r + self.n
        while l < r:
            if l & 1:
                s += self.t[l]; l += 1
            if r & 1:
                r -= 1; s += self.t[r]
            l //= 2; r //= 2
        return s

D24

Fenwick Tree (Binary Indexed Tree)

Data StructureAdvanced

A smaller, simpler tool for prefix sums with point updates. Both run in O(log n).

Example

add(1, 5), add(3, 2) → prefix(3) = 7, range sum of items 2 to 3 = 2

How it works

Use an array t of size n + 1, 1-based. Each t[i] covers a block that ends at i.
i & -i is the lowest set bit, which gives the block size.
Add: from i, add d, then jump i += i & -i until past n.
Prefix sum: from i, add t[i], then jump i -= i & -i until 0.

add O(log n) · prefix O(log n) · range sum O(log n) · Space O(n)

Pitfalls

It is 1-based. Index 0 loops forever.
Range sum [l, r] = prefix(r) - prefix(l - 1).

class Fenwick:
    def __init__(self, n):
        self.t = [0] * (n + 1)

    def add(self, i, d):            # i is 1-based
        while i < len(self.t):
            self.t[i] += d
            i += i & -i

    def prefix(self, i):            # sum of items 1..i
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i
        return s

    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l - 1)

D25

Bloom Filter

Data StructureAdvanced

A tiny, probabilistic set. It answers "definitely not present" or "maybe present". Used in caches and databases to skip disk reads.

Example

add "cat" → might_contain("cat") = True
might_contain("dog") = False, or rarely a false True

How it works

Use a bit array of m bits and k hash functions.
Add: hash the item k ways and set those k bits.
Check: if any of the k bits is 0, it means the item was never added.
If all are 1, it is maybe present.

add O(k) · check O(k) · Space O(m) bits, no items stored

Pitfalls

False positives happen. False negatives never do.
You cannot delete. A counting Bloom filter can.
Pick m and k from the item count and the error rate you want.

import hashlib

class BloomFilter:
    def __init__(self, m=1024, k=3):
        self.bits, self.m, self.k = bytearray(m), m, k

    def _spots(self, item):
        for i in range(self.k):
            h = hashlib.sha256(f"{i}:{item}".encode()).hexdigest()
            yield int(h, 16) % self.m

    def add(self, item):
        for j in self._spots(item):
            self.bits[j] = 1

    def might_contain(self, item):
        return all(self.bits[j] for j in self._spots(item))

D26

Consistent Hash Ring

Data StructureAdvanced

Spread keys across servers so that adding or removing one server moves only a few keys. Used in distributed caches and sharded databases.

Example

servers A, B, C on a ring → key "user42" goes to the first server clockwise from its hash

How it works

Use a sorted array of hash points, and a hash map, key=point, val=server.
Each server gets many virtual points, to spread load evenly.
To find a key's server, hash the key and binary search the first point clockwise.
Wrap around to index 0 past the end.

lookup O(log V) · add/remove server O(V log V), V = virtual points · Space O(V)

Pitfalls

Too few virtual nodes gives uneven load.
Wrap around at the end of the ring.
Python's hash() is random per run, so use a stable hash like md5.

import hashlib
from bisect import bisect_right, insort

class HashRing:
    def __init__(self, servers=(), vnodes=100):
        self.vnodes, self.owner, self.points = vnodes, {}, []
        for s in servers:
            self.add(s)

    def _h(self, s):
        return int(hashlib.md5(s.encode()).hexdigest(), 16)

    def add(self, server):
        for i in range(self.vnodes):
            p = self._h(f"{server}#{i}")
            self.owner[p] = server
            insort(self.points, p)

    def remove(self, server):
        for i in range(self.vnodes):
            p = self._h(f"{server}#{i}")
            del self.owner[p]
            self.points.remove(p)

    def get(self, key):
        if not self.points:
            return None
        i = bisect_right(self.points, self._h(key)) % len(self.points)
        return self.owner[self.points[i]]

Easy · 64 questions

Two Sum

EasyArrays & Hashing

Given a list of numbers and a target, return the indexes of the two numbers that add up to the target.

Example

nums = [2, 7, 11, 15], target = 9 → [0, 1]
Because 2 + 7 = 9.

How to solve

Use a hash map, key=number, val=index, for numbers seen so far.
For each number x, check if target - x is in the map.
If found, it means the pair is complete. Return both indexes.
Else store key=x, val=i and move on.

Time O(n), one pass · Space O(n), the map

Corner cases

Same value twice, like [3, 3], target 6.
Do not use one element twice.
Negatives and zero.
No answer.

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 []

Contains Duplicate

EasyArrays & Hashing

Return True if any value appears at least twice in the list.

Example

[1, 2, 3, 1] → True
[1, 2, 3] → False

How to solve

Use a hash set to store values seen so far.
For each value x, check if x is in the hash set.
If found, it means x appeared before. Return True.
Else add x. Return False at the end.

Time O(n), one pass · Space O(n), the set

Corner cases

Empty list.
One element.
Very large lists, where sorting O(n log n) uses less memory.

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

Valid Anagram

EasyArrays & Hashing

Return True if string t uses exactly the same letters as s, with the same counts.

Example

s = "anagram", t = "nagaram" → True
"rat", "car" → False

How to solve

Use two hash maps (counters), key=letter, val=count, one for s and one for t.
If lengths differ, return False.
Compare the two hash maps.
If equal, it means both use the same letters the same number of times.

Time O(n), one count pass · Space O(1), at most 26 letters

Corner cases

Different lengths.
Empty strings.
Unicode or upper case letters.

from collections import Counter

def is_anagram(s, t):
    return len(s) == len(t) and Counter(s) == Counter(t)

Best Time to Buy and Sell Stock

EasyArrays

prices[i] is the price on day i. Buy once and sell once later. Return the max profit.

Example

[7, 1, 5, 3, 6, 4] → 5
Buy at 1, sell at 6.

How to solve

Use low to store the lowest price so far, and best for the best profit.
For each price p, update low = min(low, p).
Profit if sold today is p - low.
If it beats best, it means this is a better trade. Update best.

Time O(n), one pass · Space O(1), two variables

Corner cases

Prices only fall, so answer is 0.
One day only.
Empty list.

def max_profit(prices):
    low, best = float("inf"), 0
    for p in prices:
        low = min(low, p)
        best = max(best, p - low)
    return best

Move Zeroes

EasyTwo Pointers

Move all zeros to the end of the list in place. Keep the order of the other values.

Example

[0, 1, 0, 3, 12] → [1, 3, 12, 0, 0]

How to solve

Use pointer w to store the next slot for a non-zero.
For each index r, check if nums[r] is non-zero.
If yes, swap it into slot w and move w forward.
Zeros end up pushed to the back.

Time O(n), one pass · Space O(1), in place

Corner cases

All zeros.
No zeros.
One element.

def move_zeroes(nums):
    w = 0
    for r in range(len(nums)):
        if nums[r] != 0:
            nums[w], nums[r] = nums[r], nums[w]
            w += 1

Majority Element

EasyArrays

Return the value that appears more than n/2 times. It always exists.

Example

[2, 2, 1, 1, 1, 2, 2] → 2

How to solve

Use cand to store a candidate and cnt for its vote count.
For each value x: if cnt is 0, pick x as the new candidate.
Same as cand adds 1. A different value subtracts 1.
The majority outvotes all others, so it is the final cand.

Time O(n), one pass · Space O(1), two variables

Corner cases

One element.
If a majority may not exist, do a second pass to verify.

def majority_element(nums):
    cand, cnt = None, 0
    for x in nums:
        if cnt == 0:
            cand = x
        cnt += 1 if x == cand else -1
    return cand

Single Number

EasyBit Manipulation

Every value appears twice except one. Find the one, using O(1) extra space.

Example

[4, 1, 2, 1, 2] → 4

How to solve

Use acc to store the XOR of all values.
For each value x, set acc ^= x.
Pairs cancel since a ^ a = 0.
What is left in acc is the single value.

Time O(n), one pass · Space O(1), one variable

Corner cases

One element.
Negative numbers work fine with XOR.

from functools import reduce
from operator import xor

def single_number(nums):
    return reduce(xor, nums, 0)

Missing Number

EasyMath

The list has n distinct values from 0 to n. One is missing. Find it.

Example

[3, 0, 1] → 2

How to solve

Compute the expected sum of 0 to n: n * (n + 1) // 2.
Compute the real sum of the list.
The gap between them is the missing number.

Time O(n), one sum · Space O(1)

Corner cases

Missing 0.
Missing n.
In other languages, watch for overflow, or use XOR.

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

Plus One

EasyArrays

A number is stored as a list of digits. Add one and return the new digit list.

Example

[1, 2, 9] → [1, 3, 0]
[9, 9] → [1, 0, 0]

How to solve

Walk the digits from the last one to the first.
If the digit is below 9, add 1 and return. No carry is needed.
Else set it to 0, which means a carry moves left.
If every digit was 9, put 1 in front.

Time O(n), worst case all nines · Space O(1), or O(n) for the new list

Corner cases

All nines.
Single digit [0].

def plus_one(digits):
    for i in range(len(digits) - 1, -1, -1):
        if digits[i] < 9:
            digits[i] += 1
            return digits
        digits[i] = 0
    return [1] + digits

Merge Sorted Array

EasyTwo Pointers

nums1 has m values plus n empty slots. nums2 has n values. Merge nums2 into nums1 in sorted order, in place.

Example

nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6] → [1,2,2,3,5,6]

How to solve

Use three pointers: i at the end of nums1 values, j at the end of nums2, k at the last slot.
While nums2 has values left, compare nums1[i] and nums2[j].
Put the bigger one in slot k and move that pointer back.
Filling from the back means nothing gets overwritten.

Time O(m + n), one pass · Space O(1), in place

Corner cases

m = 0.
n = 0.
Leftover nums2 values must be copied.

def merge(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]; i -= 1
        else:
            nums1[k] = nums2[j]; j -= 1
        k -= 1

Remove Duplicates from Sorted Array

EasyTwo Pointers

Remove duplicates in place from a sorted list. Return the count k of unique values, kept in the first k slots.

Example

[0,0,1,1,1,2] → 3, list starts [0,1,2]

How to solve

Use pointer w to store the next write slot.
For each value x, check if it differs from the last written value.
If yes, it means x is new. Write it at w and move w.
Return w, the count of unique values.

Time O(n), one pass · Space O(1), in place

Corner cases

Empty list.
All values the same.

def remove_duplicates(nums):
    w = 0
    for x in nums:
        if w == 0 or x != nums[w - 1]:
            nums[w] = x
            w += 1
    return w

Find All Numbers Disappeared

EasyCyclic Sort

The list has n values in range 1 to n. Some appear twice. Return the values that are missing, using O(1) extra space.

Example

[4,3,2,7,8,2,3,1] → [5, 6]

How to solve

Use the input array itself as a marker. A negative slot means "seen".
For each value v, make slot abs(v) - 1 negative.
Scan again.
If a slot is still positive, it means index + 1 never appeared.

Time O(n), two passes · Space O(1), besides the output

Corner cases

Use abs() since values may already be flipped.
No values missing.

def find_disappeared(nums):
    for v in nums:
        i = abs(v) - 1
        nums[i] = -abs(nums[i])
    return [i + 1 for i, v in enumerate(nums) if v > 0]

Find Pivot Index

EasyPrefix Sum

Return the first index where the sum of values on its left equals the sum on its right. Return -1 if none.

Example

[1, 7, 3, 6, 5, 6] → 3
Left 1+7+3 = 11, right 5+6 = 11.

How to solve

Use total to store the sum of all values, and left for the sum before i.
For each index i, right sum is total - left - nums[i].
If left equals the right sum, it means i is the pivot. Return it.
Else add nums[i] to left.

Time O(n), two passes · Space O(1)

Corner cases

Pivot at index 0, left sum is 0.
Negative values.
No pivot.

def pivot_index(nums):
    total, left = sum(nums), 0
    for i, x in enumerate(nums):
        if left == total - left - x:
            return i
        left += x
    return -1

Squares of a Sorted Array

EasyTwo Pointers

Given a sorted list that may have negatives, return the squares in sorted order.

Example

[-4, -1, 0, 3, 10] → [0, 1, 9, 16, 100]

How to solve

Use two pointers l and r at both ends, and fill the output from the back.
The biggest square is at one of the ends.
Compare abs(nums[l]) and abs(nums[r]).
Put the bigger square at the back slot and move that pointer inward.

Time O(n), one pass · Space O(n), the output

Corner cases

All negative.
All positive.
Zeros.

def sorted_squares(nums):
    l, r = 0, len(nums) - 1
    out = [0] * len(nums)
    for k in range(len(nums) - 1, -1, -1):
        if abs(nums[l]) > abs(nums[r]):
            out[k] = nums[l] ** 2; l += 1
        else:
            out[k] = nums[r] ** 2; r -= 1
    return out

Valid Palindrome

EasyTwo Pointers

Return True if a string reads the same both ways, using only letters and digits and ignoring case.

Example

"A man, a plan, a canal: Panama" → True

How to solve

Use two pointers l and r at both ends.
If a char is not a letter or digit, skip it.
Compare the two chars in lower case.
If different, it means not a palindrome. Return False. Else move both inward.

Time O(n), one pass · Space O(1)

Corner cases

Empty string or only punctuation is True.
Digits count, like "0P" is False.

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

First Unique Character

EasyArrays & Hashing

Return the index of the first char that appears only once. Return -1 if none.

Example

"leetcode" → 0
"loveleetcode" → 2

How to solve

Use a hash map (counter), key=char, val=count.
For each char in order, check if its count is 1.
If found, it means this is the first unique char. Return its index.
Return -1 if none.

Time O(n), two passes · Space O(1), at most 26 letters

Corner cases

All chars repeat.
Empty string.
One char.

from collections import Counter

def first_uniq_char(s):
    cnt = Counter(s)
    for i, ch in enumerate(s):
        if cnt[ch] == 1:
            return i
    return -1

Longest Common Prefix

EasyStrings

Return the longest prefix shared by all strings in a list.

Example

["flower", "flow", "flight"] → "fl"

How to solve

Use pre to store the first string as the starting prefix.
For each other string, check if it starts with pre.
If not, cut the last char off pre and check again.
What is left after all strings is the answer.

Time O(total chars) · Space O(1), besides the prefix

Corner cases

Empty list.
An empty string in the list.
No shared prefix gives "".

def longest_common_prefix(strs):
    if not strs:
        return ""
    pre = strs[0]
    for s in strs[1:]:
        while not s.startswith(pre):
            pre = pre[:-1]
    return pre

Ransom Note

EasyArrays & Hashing

Can you build note using letters from magazine? Each letter can be used once.

Example

note = "aa", magazine = "aab" → True

How to solve

Use two hash maps (counters), key=letter, val=count, one for the note and one for the magazine.
Subtract magazine counts from note counts.
If anything is left, it means the magazine is short of that letter. Return False.
Else return True.

Time O(n + m) · Space O(1), at most 26 letters

Corner cases

Empty note is True.
Note longer than magazine.

from collections import Counter

def can_construct(note, magazine):
    return not (Counter(note) - Counter(magazine))

Isomorphic Strings

EasyArrays & Hashing

Can chars in s be replaced to get t? The mapping must be one to one.

Example

"egg", "add" → True
"badc", "baba" → False

How to solve

Use two hash maps: key=s char, val=t char, and key=t char, val=s char.
For each pair (x, y), check both maps.
If either map already holds a different partner, it means the mapping is broken. Return False.
Else save the pair both ways.

Time O(n), one pass · Space O(1), bounded by the alphabet

Corner cases

Two chars mapping to one char.
Different lengths.

def is_isomorphic(s, t):
    if len(s) != len(t):
        return False
    a, b = {}, {}
    for x, y in zip(s, t):
        if a.setdefault(x, y) != y or b.setdefault(y, x) != x:
            return False
    return True

Word Pattern

EasyArrays & Hashing

Does the word list follow the letter pattern, one to one?

Example

pattern = "abba", s = "dog cat cat dog" → True

How to solve

Split s into words. If counts differ from the pattern, return False.
Use hash sets to count unique letters, unique words, and unique (letter, word) pairs.
If all three counts match, it means each letter maps to one word and back.

Time O(n) · Space O(n), the sets

Corner cases

Word count differs from pattern length.
Two letters map to the same word.

def word_pattern(pattern, s):
    words = s.split()
    if len(words) != len(pattern):
        return False
    return len(set(pattern)) == len(set(words)) == len(set(zip(pattern, words)))

Valid Parentheses

EasyStack

Is a string of ()[]{} brackets balanced and well nested?

Example

"()[]{}" → True
"(]" → False
"([)]" → False

How to solve

Use a stack to store open brackets not yet closed.
For each open bracket, push it.
For each close bracket, check if the top of the stack is its match.
If not, it means bad nesting. Return False. At the end, the stack must be empty.

Time O(n), one pass · Space O(n), the stack

Corner cases

Starts with a close bracket.
Only open brackets left over.
Empty string is True.

def is_valid(s):
    pair = {")": "(", "]": "[", "}": "{"}
    st = []
    for ch in s:
        if ch in pair:
            if not st or st.pop() != pair[ch]:
                return False
        else:
            st.append(ch)
    return not st

Roman to Integer

EasyStrings

Convert a Roman numeral string to an integer.

Example

"MCMXCIV" → 1994

How to solve

Use a hash map, key=symbol, val=value.
For each symbol, check if the next symbol is bigger.
If yes, it means a pair like IV. Subtract this value.
Else add this value.

Time O(n), one pass · Space O(1)

Corner cases

Subtract pairs like IV, IX, CM.
One symbol.

def roman_to_int(s):
    v = {"I": 1, "V": 5, "X": 10, "L": 50,
         "C": 100, "D": 500, "M": 1000}
    total = 0
    for i, ch in enumerate(s):
        if i + 1 < len(s) and v[ch] < v[s[i + 1]]:
            total -= v[ch]
        else:
            total += v[ch]
    return total

Add Binary

EasyMath

Add two binary strings and return the sum as a binary string.

Example

"11" + "1" → "100"

How to solve

Use two pointers at the right end of each string, and a carry.
While digits or a carry remain, add both digits and the carry.
Write sum % 2. Keep sum // 2 as the new carry.
Reverse the written digits at the end.

Time O(max(n, m)) · Space O(max(n, m)), the output

Corner cases

Different lengths.
Final carry.
"0" + "0".

def add_binary(a, b):
    i, j, carry, out = len(a) - 1, len(b) - 1, 0, []
    while i >= 0 or j >= 0 or carry:
        carry += (int(a[i]) if i >= 0 else 0) + (int(b[j]) if j >= 0 else 0)
        out.append(str(carry % 2))
        carry //= 2
        i, j = i - 1, j - 1
    return "".join(reversed(out))

Is Subsequence

EasyTwo Pointers

Is s a subsequence of t? Chars must keep order but need not be next to each other.

Example

s = "abc", t = "ahbgdc" → True

How to solve

Use pointer i to store how much of s is matched.
For each char in t, check if it equals s[i].
If yes, move i.
If i reaches the end of s, it means all of s was found in order.

Time O(len t), one pass · Space O(1)

Corner cases

Empty s is True.
s longer than t.

def is_subsequence(s, t):
    i = 0
    for ch in t:
        if i < len(s) and s[i] == ch:
            i += 1
    return i == len(s)

Fizz Buzz

EasyMath

For 1 to n, output "Fizz" for multiples of 3, "Buzz" for 5, "FizzBuzz" for both, else the number.

Example

n = 5 → ["1","2","Fizz","4","Buzz"]

How to solve

For each i from 1 to n, start with an empty string.
If i % 3 == 0, add "Fizz". If i % 5 == 0, add "Buzz".
If the string is still empty, it means neither. Use the number.

Time O(n) · Space O(n), the output

Corner cases

n = 0 gives an empty list.
Check order matters.

def fizz_buzz(n):
    out = []
    for i in range(1, n + 1):
        s = ("Fizz" if i % 3 == 0 else "") + ("Buzz" if i % 5 == 0 else "")
        out.append(s or str(i))
    return out

Palindrome Number

EasyMath

Is an integer a palindrome, without turning it into a string?

Example

121 → True
-121 → False
10 → False

How to solve

If x is negative or ends in 0 (and is not 0), return False.
Use rev to store the reversed second half.
While x > rev, move the last digit of x onto rev.
If x == rev or x == rev // 10, it means both halves match.

Time O(log x), half the digits · Space O(1)

Corner cases

Zero is True.
Odd digit count, so drop the middle with rev // 10.

def is_palindrome_num(x):
    if x < 0 or (x % 10 == 0 and x != 0):
        return False
    rev = 0
    while x > rev:
        rev = rev * 10 + x % 10
        x //= 10
    return x == rev or x == rev // 10

Reverse Integer

EasyMath

Reverse the digits of a 32-bit signed integer. Return 0 if the result overflows.

Example

123 → 321
-120 → -21

How to solve

Store the sign of x.
Reverse the digits of abs(x) and put the sign back.
If the result is outside the 32-bit range, it means overflow. Return 0.

Time O(log x), one per digit · Space O(1)

Corner cases

Overflow, like 1534236469.
Trailing zeros.
Negative input.

def reverse_int(x):
    sign = -1 if x < 0 else 1
    r = sign * int(str(abs(x))[::-1])
    return r if -2**31 <= r < 2**31 else 0

Power of Two

EasyBit Manipulation

Is n a power of two?

Example

16 → True
6 → False

How to solve

A power of two has exactly one bit set.
n & (n - 1) clears the lowest set bit.
If n > 0 and the result is 0, it means there was only one bit.

Time O(1) · Space O(1)

Corner cases

n = 0.
Negative n.
n = 1 is True.

def is_power_of_two(n):
    return n > 0 and n & (n - 1) == 0

Number of 1 Bits

EasyBit Manipulation

Count the set bits in an unsigned integer.

Example

11 (binary 1011) → 3

How to solve

Use count to store bits cleared so far.
While n is not 0, do n &= n - 1 to clear one set bit.
Add 1 to count each time.

Time O(set bits) · Space O(1)

Corner cases

n = 0.
Large 32-bit values.

def hamming_weight(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

Counting Bits

EasyBit Manipulation

For every i from 0 to n, return the number of 1 bits in i.

Example

n = 5 → [0, 1, 1, 2, 1, 2]

How to solve

Use an array bits, index=i, val=count of 1 bits in i.
For each i, i >> 1 is i without its last bit. We already know its count.
So bits[i] = bits[i >> 1] + (i & 1).

Time O(n) · Space O(n), the output

Corner cases

n = 0 gives [0].

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

Climbing Stairs

EasyDynamic Programming

You climb 1 or 2 steps at a time. How many ways reach step n?

Example

n = 3 → 3
Ways: 1+1+1, 1+2, 2+1.

How to solve

Use a and b to store ways to reach the last two steps.
The last move into step n is a 1-step or a 2-step.
So ways(n) = ways(n-1) + ways(n-2).
Slide a, b = b, a + b n times.

Time O(n) · Space O(1), two variables

Corner cases

n = 1.
n = 2.

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

Min Cost Climbing Stairs

EasyDynamic Programming

cost[i] is the price of step i. You may start at step 0 or 1 and climb 1 or 2. Return the min cost to pass the top.

Example

[10, 15, 20] → 15

How to solve

Use a and b to store the min cost to stand on the last two steps.
For each step cost c, cost to stand here is c + min(a, b).
Slide the pair forward.
The top is reached from either of the last two steps. Return min(a, b).

Time O(n) · Space O(1), two variables

Corner cases

Two steps only.
Zero costs.

def min_cost_climbing(cost):
    a = b = 0
    for c in cost:
        a, b = b, c + min(a, b)
    return min(a, b)

Sqrt(x)

EasyBinary Search

Return the floor of the square root of x, with no sqrt or **0.5.

Example

8 → 2
16 → 4

How to solve

Binary search on the answer r between 0 and x.
Check if mid * mid <= x.
If yes, it means mid is a valid floor. Keep it and search right.
Else search left.

Time O(log x) · Space O(1)

Corner cases

x = 0.
x = 1.
Big x.

def my_sqrt(x):
    lo, hi = 0, x
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if mid * mid <= x:
            lo = mid
        else:
            hi = mid - 1
    return lo

Happy Number

EasyFast & Slow Pointers

Replace n with the sum of the squares of its digits. Repeat. Is n happy, meaning it reaches 1?

Example

19 → True
1+81=82, 64+4=68, 36+64=100, 1.

How to solve

Use a hash set to store numbers already seen.
Replace n with the sum of its digit squares.
If n is 1, it means happy. Return True.
If n is in the hash set, it means a loop. Return False.

Time O(log n) per step, few steps · Space O(steps), the set

Corner cases

n = 1.
Loops like 4 → 16 → … → 4.

def is_happy(n):
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = sum(int(d) ** 2 for d in str(n))
    return n == 1

Count Primes

EasyMath

Count the primes less than n.

Example

10 → 4
Primes 2, 3, 5, 7.

How to solve

Use a boolean array is_p, index=number, val=is prime. Start all as True.
For each p up to sqrt(n) that is still prime, mark p*p, p*p+p, ... as not prime.
Count the True values left.

Time O(n log log n) · Space O(n), the list

Corner cases

n < 3 gives 0.
Start marking at p * p.

def count_primes(n):
    if n < 3:
        return 0
    is_p = [True] * n
    is_p[0] = is_p[1] = False
    for p in range(2, int(n ** 0.5) + 1):
        if is_p[p]:
            is_p[p * p::p] = [False] * len(range(p * p, n, p))
    return sum(is_p)

Binary Search

EasyBinary Search

Return the index of target in a sorted list, or -1.

Example

[-1, 0, 3, 5, 9, 12], 9 → 4

How to solve

Use lo and hi to store the range still possible.
Check the middle value.
If it equals target, return mid.
If it is smaller, it means target is to the right. Else it is to the left.

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

Corner cases

Empty list.
Target at either end.
Target not present.

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

Search Insert Position

EasyBinary Search

Return the index of target in a sorted list, or where it would be inserted.

Example

[1, 3, 5, 6], 5 → 2
2 → 1
7 → 4

How to solve

Use lo and hi to store the range, with hi = len(nums).
Find the first index where nums[i] >= target.
If nums[mid] < target, it means the answer is right of mid. Else it is at mid or left.
Return lo.

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

Corner cases

Insert at 0.
Insert at the end.
Duplicates.

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

First Bad Version

EasyBinary Search

Versions 1 to n. Once a version is bad, all later ones are bad. Find the first bad one with few is_bad calls.

Example

n = 5, first bad is 4 → 4

How to solve

Use lo and hi to store the range of versions.
Check if mid is bad.
If bad, it means the first bad one is at mid or before. Set hi = mid.
Else it is after. Set lo = mid + 1.

Time O(log n) calls · Space O(1)

Corner cases

First version is bad.
Only the last is bad.

def first_bad_version(n, is_bad):
    lo, hi = 1, n
    while lo < hi:
        mid = (lo + hi) // 2
        if is_bad(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Reverse Linked List

EasyLinked List

Reverse a singly linked list and return the new head.

Example

1→2→3→4 → 4→3→2→1

How to solve

Use prev to store the reversed part, starting as None.
For each node, point its next back to prev.
Move prev to this node and step to the saved next node.
When done, prev is the new head.

Time O(n) · Space O(1)

Corner cases

Empty list.
One node.
Save next before you change it.

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

Merge Two Sorted Lists

EasyLinked List

Merge two sorted linked lists into one sorted list.

Example

1→2→4 and 1→3→4 → 1→1→2→3→4→4

How to solve

Use a dummy node to store the start, and tail for the end of the merged list.
While both lists have nodes, compare their heads.
Attach the smaller one to tail and move on.
Attach whatever list is left.

Time O(n + m) · Space O(1), nodes are reused

Corner cases

One list empty.
Both empty.
Equal values.

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

Linked List Cycle

EasyFast & Slow Pointers

Does the linked list have a cycle?

Example

3→2→0→-4→(back to 2) → True

How to solve

Use two pointers: slow moves 1 step, fast moves 2.
Move them until fast hits the end.
If they ever meet, it means there is a cycle.
If fast reaches None, there is no cycle.

Time O(n) · Space O(1)

Corner cases

Empty list.
One node pointing to itself.
Check fast.next before fast.next.next.

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

Middle of the Linked List

EasyFast & Slow Pointers

Return the middle node. If there are two middles, return the second.

Example

1→2→3→4→5 → node 3
1→2→3→4 → node 3

How to solve

Use two pointers: slow moves 1 step, fast moves 2.
When fast reaches the end, slow has gone half as far.
Return slow.

Time O(n) · Space O(1)

Corner cases

One node.
Even length returns the second middle.

def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow

Remove Linked List Elements

EasyLinked List

Remove every node whose value equals val.

Example

1→2→6→3→6, val = 6 → 1→2→3

How to solve

Use a dummy node before the head, so the head can be removed too.
For each node cur, check if cur.next.val == val.
If yes, skip it with cur.next = cur.next.next.
Else move cur forward.

Time O(n) · Space O(1)

Corner cases

Head must be removed.
All nodes removed.
Back to back matches.

def remove_elements(head, val):
    dummy = cur = ListNode(0, head)
    while cur.next:
        if cur.next.val == val:
            cur.next = cur.next.next
        else:
            cur = cur.next
    return dummy.next

Palindrome Linked List

EasyLinked List

Is a linked list a palindrome? Try for O(1) space.

Example

1→2→2→1 → True

How to solve

Use fast and slow pointers to find the middle.
Reverse the second half.
Walk the first half and the reversed half side by side.
If any values differ, it means not a palindrome.

Time O(n) · Space O(1)

Corner cases

One node.
Odd length.
You may want to restore the list.

def is_palindrome_list(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    prev = None
    while slow:
        slow.next, prev, slow = prev, slow, slow.next
    while prev:
        if prev.val != head.val:
            return False
        prev, head = prev.next, head.next
    return True

Intersection of Two Linked Lists

EasyLinked List

Return the node where two linked lists join, or None.

Example

A: 4→1→8→4→5, B: 5→6→1→8→4→5 → node 8

How to solve

Use pointer p on list A and q on list B.
When a pointer hits the end, send it to the head of the other list.
Both walk A + B steps in total.
If they meet, it means that node is the join. If both hit None, there is no join.

Time O(n + m) · Space O(1)

Corner cases

No intersection.
Compare nodes, not values.
One list empty.

def get_intersection(a, b):
    p, q = a, b
    while p is not q:
        p = p.next if p else b
        q = q.next if q else a
    return p

Maximum Depth of Binary Tree

EasyTrees

Return the number of nodes on the longest root to leaf path.

Example

[3, 9, 20, null, null, 15, 7] → 3

How to solve

Recurse on each node.
An empty node has depth 0.
Depth of a node is 1 + max(depth left, depth right).

Time O(n) · Space O(h), the call stack

Corner cases

Empty tree.
A skewed tree can be deep, so recursion limit matters.

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

Invert Binary Tree

EasyTrees

Mirror a binary tree. Swap the left and right child of every node.

Example

[4, 2, 7, 1, 3, 6, 9] → [4, 7, 2, 9, 6, 3, 1]

How to solve

Recurse on each node.
Invert the left and right subtrees.
Swap them.

Time O(n) · Space O(h), the call stack

Corner cases

Empty tree.
One node.

def invert_tree(root):
    if root:
        root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root

Same Tree

EasyTrees

Are two binary trees the same in shape and values?

Example

[1, 2, 3] and [1, 2, 3] → True
[1, 2] and [1, null, 2] → False

How to solve

Recurse on both trees together.
If either node is None, both must be None.
Else the values must match, and both left and right subtrees must match.

Time O(n) · Space O(h), the call stack

Corner cases

Both empty.
Same values, different shape.

def is_same_tree(p, q):
    if not p or not q:
        return p is q
    return (p.val == q.val and is_same_tree(p.left, q.left)
            and is_same_tree(p.right, q.right))

Symmetric Tree

EasyTrees

Is a binary tree a mirror of itself?

Example

[1, 2, 2, 3, 4, 4, 3] → True

How to solve

Use a helper mirror(a, b) to check if two trees mirror each other.
If either is None, both must be None.
Values must match.
Check a.left with b.right, and a.right with b.left.

Time O(n) · Space O(h), the call stack

Corner cases

Empty tree.
Same values, wrong shape.

def is_symmetric(root):
    def mirror(a, b):
        if not a or not b:
            return a is b
        return (a.val == b.val and mirror(a.left, b.right)
                and mirror(a.right, b.left))
    return mirror(root, root)

Path Sum

EasyTrees

Is there a root to leaf path whose values add up to target?

Example

[5,4,8,11,null,13,4,7,2], 22 → True
Path 5→4→11→2.

How to solve

Recurse with the remaining sum.
At each node, subtract its value from the target.
If it is a leaf and the remaining sum is 0, it means the path works.
Else try the left and right child.

Time O(n) · Space O(h), the call stack

Corner cases

Empty tree is False.
Must end at a leaf.
Negative values.

def has_path_sum(root, target):
    if not root:
        return False
    target -= root.val
    if not root.left and not root.right:
        return target == 0
    return has_path_sum(root.left, target) or has_path_sum(root.right, target)

Diameter of Binary Tree

EasyTrees

Return the number of edges on the longest path between any two nodes.

Example

[1, 2, 3, 4, 5] → 3
Path 4→2→1→3.

How to solve

Use best to store the longest path found.
A helper returns the height of each node.
At each node, the path through it is left height + right height.
Update best with it. Return 1 + max(left, right) up.

Time O(n) · Space O(h), the call stack

Corner cases

One node is 0.
The best path may skip the root.

def diameter(root):
    best = 0
    def height(n):
        nonlocal best
        if not n:
            return 0
        l, r = height(n.left), height(n.right)
        best = max(best, l + r)
        return 1 + max(l, r)
    height(root)
    return best

Balanced Binary Tree

EasyTrees

Is the tree height balanced? For every node, child heights differ by at most 1.

Example

[3, 9, 20, null, null, 15, 7] → True

How to solve

A helper returns the height of a node, or -1 if it is not balanced.
Get left and right heights.
If either is -1, or they differ by more than 1, return -1.
Else return 1 + max. The tree is balanced if the root is not -1.

Time O(n) · Space O(h), the call stack

Corner cases

Empty tree is True.
Imbalance deep inside.

def is_balanced(root):
    def h(n):
        if not n:
            return 0
        l, r = h(n.left), h(n.right)
        if l < 0 or r < 0 or abs(l - r) > 1:
            return -1
        return 1 + max(l, r)
    return h(root) >= 0

Lowest Common Ancestor of a BST

EasyTrees

In a binary search tree, return the lowest node that has both p and q below it.

Example

BST [6,2,8,0,4,7,9], p = 2, q = 8 → 6

How to solve

Start at the root.
If both p and q are smaller, it means both are on the left. Go left.
If both are bigger, go right.
Else they split here. This node is the answer.

Time O(h) · Space O(1)

Corner cases

p is an ancestor of q.
p equals q.

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

Subtree of Another Tree

EasyTrees

Is tree sub the same as some subtree of root?

Example

root = [3,4,5,1,2], sub = [4,1,2] → True

How to solve

Use a helper same(a, b) to check if two trees are equal.
For each node of root, check same(node, sub).
If any node matches, it means sub is a subtree.
Else try the left and right children.

Time O(n · m) · Space O(h), the call stack

Corner cases

Equal values but extra children below.
sub empty.

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

Minimum Depth of Binary Tree

EasyTrees

Return the number of nodes on the shortest root to leaf path.

Example

[3, 9, 20, null, null, 15, 7] → 2

How to solve

Use a queue to store (node, depth) for BFS.
Pop nodes level by level.
If a node has no children, it means it is the nearest leaf. Return its depth.
Else push its children with depth + 1.

Time O(n) · Space O(w), the widest level

Corner cases

A node with one child is not a leaf.
Empty tree is 0.

from collections import deque

def min_depth(root):
    if not root:
        return 0
    q = deque([(root, 1)])
    while q:
        n, d = q.popleft()
        if not n.left and not n.right:
            return d
        for c in (n.left, n.right):
            if c:
                q.append((c, d + 1))

Binary Tree Inorder Traversal

EasyTrees

Return node values in inorder: left, node, right. Do it without recursion.

Example

[1, null, 2, 3] → [1, 3, 2]

How to solve

Use a stack to store nodes still to visit.
Go left as far as you can, pushing each node.
Pop a node, record its value, then move to its right child.
Repeat until the stack is empty and no node is left.

Time O(n) · Space O(h), the stack

Corner cases

Empty tree.
Skewed tree.

def inorder(root):
    out, st = [], []
    while root or st:
        while root:
            st.append(root)
            root = root.left
        root = st.pop()
        out.append(root.val)
        root = root.right
    return out

Min Stack

EasyStack

Build a stack with push, pop, top, and get_min, all in O(1).

Example

push -2, push 0, push -3, get_min → -3, pop, get_min → -2

How to solve

Use one stack to store pairs (value, min so far).
On push, the new min is min(value, top min).
On pop, remove the top pair.
get_min reads the min from the top pair.

Time O(1) per call · Space O(n), the stack

Corner cases

Duplicate min values.
Pop on empty, so clarify.

class MinStack:
    def __init__(self):
        self.st = []

    def push(self, x):
        m = min(x, self.st[-1][1]) if self.st else x
        self.st.append((x, m))

    def pop(self):
        self.st.pop()

    def top(self):
        return self.st[-1][0]

    def get_min(self):
        return self.st[-1][1]

Implement Queue using Stacks

EasyStack

Build a FIFO queue using only two stacks.

Example

push 1, push 2, peek → 1, pop → 1, empty → False

How to solve

Use two stacks: inp for new items, and out for items ready to leave.
Push always goes to inp.
For pop or peek, if out is empty, move all of inp into out. This flips the order.
Pop or peek from out.

Time O(1) amortized · Space O(n)

Corner cases

Mixed pushes and pops.
Only refill out when it is empty.

class MyQueue:
    def __init__(self):
        self.inp, self.out = [], []

    def push(self, x):
        self.inp.append(x)

    def peek(self):
        if not self.out:
            while self.inp:
                self.out.append(self.inp.pop())
        return self.out[-1]

    def pop(self):
        self.peek()
        return self.out.pop()

    def empty(self):
        return not self.inp and not self.out

Pascal's Triangle

EasyArrays

Return the first n rows of Pascal's triangle.

Example

n = 4 → [[1],[1,1],[1,2,1],[1,3,3,1]]

How to solve

Use rows to store the rows built so far.
Each new row starts as all 1s.
For each inner spot j, set it to above[j-1] + above[j].
Add the row to rows.

Time O(n²) · Space O(n²), the output

Corner cases

n = 1.
n = 0.

def generate(n):
    rows = []
    for i in range(n):
        row = [1] * (i + 1)
        for j in range(1, i):
            row[j] = rows[-1][j - 1] + rows[-1][j]
        rows.append(row)
    return rows

Flood Fill

EasyGraphs

Starting at pixel (sr, sc), recolor it and every connected pixel of the same color.

Example

[[1,1,1],[1,1,0],[1,0,1]], start (1,1), color 2 → [[2,2,2],[2,2,0],[2,0,1]]

How to solve

Store the old color of the start pixel. If it equals the new color, return.
DFS from the start pixel.
For each pixel inside the grid with the old color, paint it.
Then visit its 4 neighbors.

Time O(R · C) · Space O(R · C), the call stack

Corner cases

New color equals old color, so return early or you loop forever.
Edges of the grid.

def flood_fill(img, sr, sc, color):
    old = img[sr][sc]
    if old == color:
        return img
    def dfs(r, c):
        if 0 <= r < len(img) and 0 <= c < len(img[0]) and img[r][c] == old:
            img[r][c] = color
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                dfs(r + dr, c + dc)
    dfs(sr, sc)
    return img

Meeting Rooms

EasyIntervals

Given meeting times [start, end], can one person attend all of them?

Example

[[0,30],[5,10],[15,20]] → False

How to solve

Sort meetings by start time.
For each meeting, check if it starts before the last one ends.
If yes, it means they overlap. Return False.
Else return True.

Time O(n log n), the sort · Space O(1)

Corner cases

Touching times like [1,2],[2,3] do not overlap.
Empty list.

def can_attend(intervals):
    intervals.sort()
    return all(intervals[i][0] >= intervals[i - 1][1]
               for i in range(1, len(intervals)))

Convert Sorted Array to BST

EasyTrees

Turn a sorted list into a height balanced BST.

Example

[-10, -3, 0, 5, 9] → root 0, left -3, -10, right 9, 5

How to solve

Use a helper build(l, r) for the range nums[l..r].
Pick the middle value as the root.
Build the left subtree from the left half, and the right from the right half.
An empty range returns None.

Time O(n) · Space O(log n), the call stack

Corner cases

Empty list.
Even length, so either middle works.

def sorted_to_bst(nums):
    def build(l, r):
        if l > r:
            return None
        m = (l + r) // 2
        return TreeNode(nums[m], build(l, m - 1), build(m + 1, r))
    return build(0, len(nums) - 1)

Backspace String Compare

EasyTwo Pointers

# means backspace. Are two typed strings equal after editing?

Example

"ab#c", "ad#c" → True

How to solve

Use a stack to store the typed chars.
For each char, if it is #, pop if the stack is not empty.
Else push the char.
Build both strings this way and compare.

Time O(n + m) · Space O(n + m)

Corner cases

# on an empty result does nothing.
Many # in a row.

def backspace_compare(s, t):
    def build(x):
        st = []
        for ch in x:
            if ch == "#":
                if st:
                    st.pop()
            else:
                st.append(ch)
        return st
    return build(s) == build(t)

Maximum Average Subarray I

EasySliding Window

Find the max average of any contiguous block of length k.

Example

[1, 12, -5, -6, 50, 3], k = 4 → 12.75

How to solve

Use cur to store the sum of the current window of size k.
Start with the sum of the first k values.
For each next value, add it and drop the value leaving the window.
Keep the best sum. Return best / k.

Time O(n) · Space O(1)

Corner cases

k equals the list length.
All negative values.

def find_max_average(nums, k):
    cur = best = sum(nums[:k])
    for i in range(k, len(nums)):
        cur += nums[i] - nums[i - k]
        best = max(best, cur)
    return best / k

Medium · 102 questions

Group Anagrams

MediumArrays & Hashing

Group the strings that are anagrams of each other.

Example

["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]]

How to solve

Use a hash map, key=sorted letters, val=list of words.
For each word, sort its letters to get the key.
Anagrams share the same key, so they land in the same list.
Return all the lists.

Time O(n · k log k), k = word length · Space O(n · k)

Corner cases

Empty strings.
One word.
Output order is free.

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        groups["".join(sorted(s))].append(s)
    return list(groups.values())

Top K Frequent Elements

MediumHeap / Bucket Sort

Return the k most frequent values.

Example

[1,1,1,2,2,3], k = 2 → [1, 2]

How to solve

Use a hash map (counter), key=value, val=count.
Use an array of buckets, index=count, val=list of values with that count.
Walk the buckets from the highest count down.
Collect values until you have k.

Time O(n) · Space O(n), the buckets

Corner cases

k equals the number of unique values.
Ties in frequency.

from collections import Counter

def top_k_frequent(nums, k):
    buckets = [[] for _ in range(len(nums) + 1)]
    for x, c in Counter(nums).items():
        buckets[c].append(x)
    out = []
    for b in reversed(buckets):
        out += b
        if len(out) >= k:
            return out[:k]

Product of Array Except Self

MediumPrefix Sum

Return a list where out[i] is the product of all values except nums[i]. No division.

Example

[1, 2, 3, 4] → [24, 12, 8, 6]

How to solve

Use out to store, first, the product of everything left of i.
Fill it left to right with a running product.
Walk right to left with right, the product of everything right of i.
Multiply out[i] by right. Now it holds left × right.

Time O(n), two passes · Space O(1), besides the output

Corner cases

One zero.
Two or more zeros.
Negatives.

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

Longest Consecutive Sequence

MediumArrays & Hashing

Return the length of the longest run of consecutive integers, in O(n).

Example

[100, 4, 200, 1, 3, 2] → 4
Run 1, 2, 3, 4.

How to solve

Use a hash set to store all values.
For each value x, check if x - 1 is in the hash set.
If not, it means x starts a run. Count up while x + 1 is in the hash set.
Keep the longest run.

Time O(n), each value counted once · Space O(n), the set

Corner cases

Duplicates.
Empty list.
Negatives.

def longest_consecutive(nums):
    s, best = set(nums), 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

Subarray Sum Equals K

MediumPrefix Sum

Count contiguous blocks whose sum is k.

Example

[1, 1, 1], k = 2 → 2

How to solve

Use a hash map, key=prefix sum, val=times seen. Start with {0: 1}.
For each value, add it to the running prefix sum.
Check if prefix - k is in the map.
If found, it means a block ending here sums to k. Add its count. Then record this prefix.

Time O(n), one pass · Space O(n), the map

Corner cases

Negatives, so a sliding window fails.
k = 0.
Block starting at index 0.

from collections import defaultdict

def subarray_sum(nums, k):
    seen = defaultdict(int, {0: 1})
    pre = count = 0
    for x in nums:
        pre += x
        count += seen[pre - k]
        seen[pre] += 1
    return count

Maximum Subarray

MediumDynamic Programming

Find the contiguous block with the largest sum.

Example

[-2,1,-3,4,-1,2,1,-5,4] → 6
Block [4,-1,2,1].

How to solve

Use cur to store the best sum ending at this value, and best overall.
For each value x, set cur = max(x, cur + x).
If cur + x is smaller than x, it means the old block hurts. Start fresh at x.
Update best with cur.

Time O(n), one pass · Space O(1)

Corner cases

All negative, so return the largest value, not 0.
One element.

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

Maximum Product Subarray

MediumDynamic Programming

Find the contiguous block with the largest product.

Example

[2, 3, -2, 4] → 6
[-2, 0, -1] → 0

How to solve

Use hi and lo to store the max and min products ending here.
For each value x, a negative x can turn lo into the new max.
So new hi is the max of x, hi * x, lo * x. New lo is the min.
Update best with hi.

Time O(n), one pass · Space O(1)

Corner cases

Zeros reset the run.
Two negatives make a positive.
One element.

def max_product(nums):
    hi = lo = best = nums[0]
    for x in nums[1:]:
        hi, lo = max(x, hi * x, lo * x), min(x, hi * x, lo * x)
        best = max(best, hi)
    return best

Rotate Array

MediumArrays

Rotate the list to the right by k steps, in place.

Example

[1,2,3,4,5,6,7], k = 3 → [5,6,7,1,2,3,4]

How to solve

Set k = k % n to drop full turns.
Reverse the whole list.
Reverse the first k values.
Reverse the rest. Now the last k values sit at the front.

Time O(n) · Space O(1), in place

Corner cases

k > n.
k = 0.
One element.

def rotate(nums, k):
    n = len(nums)
    k %= n
    def rev(l, r):
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l, r = l + 1, r - 1
    rev(0, n - 1); rev(0, k - 1); rev(k, n - 1)

Sort Colors

MediumTwo Pointers

Sort a list of 0s, 1s, and 2s in place, in one pass.

Example

[2, 0, 2, 1, 1, 0] → [0, 0, 1, 1, 2, 2]

How to solve

Use three pointers: lo for the next 0 slot, hi for the next 2 slot, mid to scan.
If nums[mid] is 0, swap it to lo. Move lo and mid.
If it is 2, swap it to hi. Move only hi, since the swapped value is unchecked.
If it is 1, just move mid.

Time O(n), one pass · Space O(1)

Corner cases

All the same value.
Already sorted.

def sort_colors(nums):
    lo, mid, hi = 0, 0, len(nums) - 1
    while mid <= hi:
        if nums[mid] == 0:
            nums[lo], nums[mid] = nums[mid], nums[lo]
            lo += 1; mid += 1
        elif nums[mid] == 2:
            nums[mid], nums[hi] = nums[hi], nums[mid]
            hi -= 1
        else:
            mid += 1

Next Permutation

MediumArrays

Change the list to the next greater ordering of its values, in place. If it is the largest, wrap to the smallest.

Example

[1, 2, 3] → [1, 3, 2]
[3, 2, 1] → [1, 2, 3]

How to solve

From the right, find the first i where nums[i] < nums[i+1].
If found, it means i can grow. Swap it with the rightmost value bigger than it.
Reverse everything after i to make that part smallest.
If not found, the list is the largest. Reverse it all.

Time O(n) · Space O(1)

Corner cases

Already the largest.
Duplicates like [1, 5, 1].

def next_permutation(nums):
    i = len(nums) - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1:] = reversed(nums[i + 1:])

Merge Intervals

MediumIntervals

Merge all overlapping intervals.

Example

[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]

How to solve

Sort intervals by start.
Use out to store merged intervals.
For each interval, check if it starts at or before the last end in out.
If yes, it means they overlap. Extend that end. Else add it as new.

Time O(n log n), the sort · Space O(n), the output

Corner cases

Touching intervals [1,4],[4,5] merge.
One interval inside another.

def merge_intervals(intervals):
    out = []
    for s, e in sorted(intervals):
        if out and s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

Insert Interval

MediumIntervals

Insert a new interval into a sorted list of non-overlapping intervals. Merge where needed.

Example

[[1,3],[6,9]], new [2,5] → [[1,5],[6,9]]

How to solve

Use out to store the result.
Add every interval that ends before the new one starts.
While intervals overlap the new one, grow the new one to cover them.
Add the grown interval, then the rest.

Time O(n) · Space O(n), the output

Corner cases

New interval goes first or last.
It covers everything.
Empty list.

def insert_interval(intervals, new):
    out, i, n = [], 0, len(intervals)
    while i < n and intervals[i][1] < new[0]:
        out.append(intervals[i]); i += 1
    s, e = new
    while i < n and intervals[i][0] <= e:
        s, e = min(s, intervals[i][0]), max(e, intervals[i][1]); i += 1
    return out + [[s, e]] + intervals[i:]

Non-overlapping Intervals

MediumGreedy

Return the fewest intervals to remove so the rest do not overlap.

Example

[[1,2],[2,3],[3,4],[1,3]] → 1

How to solve

Sort intervals by end.
Use end to store the end of the last kept interval.
For each interval, check if it starts at or after end.
If yes, keep it and update end. Else it overlaps. Count it as removed.

Time O(n log n), the sort · Space O(1)

Corner cases

Touching ends are fine.
All the same interval.

def erase_overlap(intervals):
    end, removed = float("-inf"), 0
    for s, e in sorted(intervals, key=lambda x: x[1]):
        if s >= end:
            end = e
        else:
            removed += 1
    return removed

Meeting Rooms II

MediumHeap

Return the minimum number of rooms needed for all meetings.

Example

[[0,30],[5,10],[15,20]] → 2

How to solve

Sort meetings by start.
Use a min-heap of end times of busy rooms. The top is the room that frees up first.
For each meeting, check if the earliest end is at or before its start.
If yes, it means that room is free. Reuse it. Else open a new room. The heap size is the answer.

Time O(n log n) · Space O(n), the heap

Corner cases

Back to back meetings share a room.
Empty list.

import heapq

def min_meeting_rooms(intervals):
    ends = []
    for s, e in sorted(intervals):
        if ends and ends[0] <= s:
            heapq.heapreplace(ends, e)
        else:
            heapq.heappush(ends, e)
    return len(ends)

Spiral Matrix

MediumMatrix

Return all values of a matrix in spiral order.

Example

[[1,2,3],[4,5,6],[7,8,9]] → [1,2,3,6,9,8,7,4,5]

How to solve

Use out to store the result.
Take the top row off the matrix and add it.
Rotate what is left counter-clockwise, so the next edge becomes the top row.
Repeat until the matrix is empty.

Time O(R · C · min(R, C)), from the rotations · Space O(R · C)

Corner cases

One row.
One column.
Non-square matrix.

def spiral_order(matrix):
    out = []
    while matrix:
        out += matrix.pop(0)
        matrix = [list(r) for r in zip(*matrix)][::-1]
    return out

Rotate Image

MediumMatrix

Rotate an n x n matrix 90 degrees clockwise, in place.

Example

[[1,2,3],[4,5,6],[7,8,9]] → [[7,4,1],[8,5,2],[9,6,3]]

How to solve

Transpose the matrix: swap m[i][j] with m[j][i] for j > i.
Reverse each row.
Transpose then reverse rows equals a 90 degree turn clockwise.

Time O(n²) · Space O(1), in place

Corner cases

1 x 1 matrix.
Only swap where j > i in the transpose.

def rotate_image(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()

Set Matrix Zeroes

MediumMatrix

If a cell is 0, set its whole row and column to 0, in place.

Example

[[1,1,1],[1,0,1],[1,1,1]] → [[1,0,1],[0,0,0],[1,0,1]]

How to solve

Use a hash set of rows that hold a 0, and a hash set of columns.
Scan the matrix once to fill both sets.
Scan again.
If a cell's row or column is in a set, set the cell to 0.

Time O(R · C) · Space O(R + C), the sets

Corner cases

A zero in the first row or column.
All zeros.

def set_zeroes(m):
    rows = {i for i, r in enumerate(m) for v in r if v == 0}
    cols = {j for r in m for j, v in enumerate(r) if v == 0}
    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

Valid Sudoku

MediumArrays & Hashing

Is a partly filled 9 x 9 board valid? No repeats in any row, column, or 3 x 3 box.

Example

A row with two 5s → False

How to solve

Use a hash set of tuples like (row, i, v), (col, j, v), (box, i//3, j//3, v).
For each filled cell, build its three tuples.
If any tuple is already in the hash set, it means a repeat. Return False.
Else add the keys.

Time O(81), fixed board · Space O(81)

Corner cases

Empty cells "." are skipped.
Valid does not mean solvable.

def is_valid_sudoku(board):
    seen = set()
    for i in range(9):
        for j in range(9):
            v = board[i][j]
            if v == ".":
                continue
            keys = {("r", i, v), ("c", j, v), ("b", i // 3, j // 3, v)}
            if keys & seen:
                return False
            seen |= keys
    return True

Encode and Decode Strings

MediumStrings

Encode a list of strings into one string, and decode it back.

Example

["lint", "code"] → "4#lint4#code" → ["lint", "code"]

How to solve

To encode, write each string as length#text.
To decode, read digits up to the next #. That is the length.
Read exactly that many chars after #.
Move past them and repeat.

Time O(total chars) · Space O(total chars)

Corner cases

Strings that hold # or digits.
Empty strings.
Empty list.

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

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

Find the Duplicate Number

MediumFast & Slow Pointers

n + 1 values in range 1 to n. One value repeats. Find it without changing the list, in O(1) space.

Example

[1, 3, 4, 2, 2] → 2

How to solve

Treat the list as a linked list where index i points to nums[i].
The repeated value is where a cycle starts.
Use slow and fast pointers until they meet.
Reset slow to 0. Move both by 1. Where they meet is the duplicate.

Time O(n) · Space O(1)

Corner cases

The repeat shows up many times.
Do not sort, since that changes the list.

def find_duplicate(nums):
    slow = fast = 0
    while True:
        slow, fast = nums[slow], nums[nums[fast]]
        if slow == fast:
            break
    slow = 0
    while slow != fast:
        slow, fast = nums[slow], nums[fast]
    return slow

3Sum

MediumTwo Pointers

Return all unique triplets that sum to 0.

Example

[-1, 0, 1, 2, -1, -4] → [[-1,-1,2],[-1,0,1]]

How to solve

Sort the list.
For each index i, run two pointers l and r on the part to its right.
If the sum is too small, move l. Too big, move r. If 0, save it.
Skip equal values for i and l to avoid repeats.

Time O(n²) · Space O(1), besides the output

Corner cases

All zeros.
Fewer than 3 values.
Duplicate triplets.

def three_sum(nums):
    nums.sort()
    out = []
    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: l += 1
            elif s > 0: r -= 1
            else:
                out.append([nums[i], nums[l], nums[r]])
                l += 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
    return out

Container With Most Water

MediumTwo Pointers

Pick two lines from height that hold the most water.

Example

[1,8,6,2,5,4,8,3,7] → 49

How to solve

Use two pointers l and r at both ends.
Area is width × the shorter line. Update best.
Move the shorter line inward.
Moving the taller one can never help, since the short side caps the area.

Time O(n), one pass · Space O(1)

Corner cases

Two lines only.
Equal heights.

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

Two Sum II (Sorted Input)

MediumTwo Pointers

The list is sorted. Return 1-based indexes of two values that sum to target, in O(1) space.

Example

[2, 7, 11, 15], 9 → [1, 2]

How to solve

Use two pointers l and r at both ends.
Check the sum of the two values.
If equal to target, return both (1-based).
If too small, move l right. If too big, move r left.

Time O(n) · Space O(1)

Corner cases

Negative values.
Return 1-based indexes.

def two_sum_sorted(nums, target):
    l, r = 0, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target:
            return [l + 1, r + 1]
        if s < target:
            l += 1
        else:
            r -= 1

Longest Substring Without Repeating Characters

MediumSliding Window

Return the length of the longest substring with all distinct chars.

Example

"abcabcbb" → 3
"pwwkew" → 3

How to solve

Use a hash map, key=char, val=last index seen, and left for the window start.
For each char, check if its last index is inside the window.
If yes, it means a repeat. Move left to just after it.
Save this index. Update best with the window size.

Time O(n), one pass · Space O(k), distinct chars

Corner cases

Empty string.
All the same char.
Do not move left backward.

def length_of_longest_substring(s):
    last, left, best = {}, 0, 0
    for i, ch in enumerate(s):
        if last.get(ch, -1) >= left:
            left = last[ch] + 1
        last[ch] = i
        best = max(best, i - left + 1)
    return best

Longest Repeating Character Replacement

MediumSliding Window

You may change up to k chars. Return the longest run of one char you can make.

Example

"AABABBA", k = 1 → 4

How to solve

Use a hash map (counter), key=char, val=count in window, and top for the highest count.
Grow the window to the right.
If window size - top > k, it means too many changes needed. Slide left one step.
The window never shrinks, so its final size is the answer.

Time O(n) · Space O(26)

Corner cases

k = 0.
k bigger than the string.

from collections import Counter

def character_replacement(s, k):
    cnt, left, top = Counter(), 0, 0
    for right, ch in enumerate(s):
        cnt[ch] += 1
        top = max(top, cnt[ch])
        if right - left + 1 - top > k:
            cnt[s[left]] -= 1
            left += 1
    return len(s) - left

Permutation in String

MediumSliding Window

Does s2 hold some ordering of s1 as a substring?

Example

s1 = "ab", s2 = "eidbaooo" → True

How to solve

Use a hash map (counter), key=letter, val=count in s1.
Keep a window of size len(s1) on s2 with its own hash map, key=letter, val=count in window.
Slide the window one char at a time.
If the two hash maps match, it means the window is an anagram. Return True.

Time O(n · 26) · Space O(26)

Corner cases

s1 longer than s2.
Repeated letters.

from collections import Counter

def check_inclusion(s1, s2):
    k, need = len(s1), Counter(s1)
    win = Counter(s2[:k])
    for i in range(k, len(s2) + 1):
        if win == need:
            return True
        if i < len(s2):
            win[s2[i]] += 1
            win[s2[i - k]] -= 1
    return False

Find All Anagrams in a String

MediumSliding Window

Return all start indexes in s where an anagram of p begins.

Example

s = "cbaebabacd", p = "abc" → [0, 6]

How to solve

Use two hash maps (counters), key=letter, val=count: one for p, one for the window.
For each char, add it to the window. Drop the char that falls out.
If the two hash maps match, it means an anagram starts at i - k + 1. Record it.

Time O(n · 26) · Space O(26)

Corner cases

p longer than s.
Windows that overlap.

from collections import Counter

def find_anagrams(s, p):
    k, need, win, out = len(p), Counter(p), Counter(), []
    for i, ch in enumerate(s):
        win[ch] += 1
        if i >= k:
            win[s[i - k]] -= 1
        if win == need:
            out.append(i - k + 1)
    return out

Minimum Size Subarray Sum

MediumSliding Window

Values are positive. Return the shortest block with sum at least target, or 0.

Example

target = 7, [2,3,1,2,4,3] → 2
Block [4,3].

How to solve

Use left for the window start and total for the window sum.
For each value, add it to total.
While total >= target, record the window length, then drop nums[left] and move left.
Return the shortest length, or 0.

Time O(n), each value enters and leaves once · Space O(1)

Corner cases

No block works, so return 0.
One value is enough.

def min_subarray_len(target, nums):
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

Daily Temperatures

MediumMonotonic Stack

For each day, how many days until a warmer one? Use 0 if never.

Example

[73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]

How to solve

Use a monotonic stack of indexes of days still waiting for a warmer day. Temps fall from bottom to top.
For each day, check if it is warmer than the day on top.
If yes, it means that day's wait is over. Pop it and record i - j. Repeat.
Push today.

Time O(n), each index pushed and popped once · Space O(n), the stack

Corner cases

Equal temps are not warmer.
Temps only fall.

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

Evaluate Reverse Polish Notation

MediumStack

Evaluate an expression in postfix form.

Example

["2","1","+","3","*"] → 9

How to solve

Use a stack to store numbers.
For each token, if it is a number, push it.
If it is an operator, pop b, then a. Push a op b.
The last value on the stack is the answer.

Time O(n) · Space O(n), the stack

Corner cases

Negative numbers like "-3".
Use int(a / b), not //, for negatives.

def eval_rpn(tokens):
    st = []
    for t in tokens:
        if t in "+-*/" and len(t) == 1:
            b, a = st.pop(), st.pop()
            st.append(a + b if t == "+" else a - b if t == "-"
                      else a * b if t == "*" else int(a / b))
        else:
            st.append(int(t))
    return st[0]

Generate Parentheses

MediumBacktracking

Return all well formed strings with n pairs of brackets.

Example

n = 3 → ["((()))","(()())","(())()","()(())","()()()"]

How to solve

Build strings with recursion, tracking open and close counts.
If open count < n, add ( and recurse.
If close count < open count, add ) and recurse.
When length is 2n, save the string.

Time O(4^n / √n), the Catalan number · Space O(n), the recursion

Corner cases

n = 1.
The count grows as the Catalan numbers.

def generate_parenthesis(n):
    out = []
    def go(s, o, c):
        if len(s) == 2 * n:
            out.append(s); return
        if o < n: go(s + "(", o + 1, c)
        if c < o: go(s + ")", o, c + 1)
    go("", 0, 0)
    return out

Decode String

MediumStack

Decode strings like k[text], which means repeat text k times. Nesting is allowed.

Example

"3[a2[c]]" → "accaccacc"

How to solve

Use a stack to store (text before, repeat count) at each [.
Digits build the count. Letters build cur.
On [, push (cur, num) and reset both.
On ], pop and set cur = before + count * cur.

Time O(output length) · Space O(output length)

Corner cases

Multi digit counts like 12[a].
Text outside brackets.

def decode_string(s):
    st, cur, num = [], "", 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch == "[":
            st.append((cur, num)); cur, num = "", 0
        elif ch == "]":
            prev, k = st.pop(); cur = prev + k * cur
        else:
            cur += ch
    return cur

Asteroid Collision

MediumStack

Positive asteroids move right, negative move left. When they meet, the smaller one blows up. Equal size, both go. Return what is left.

Example

[5, 10, -5] → [5, 10]
[8, -8] → []

How to solve

Use a stack to store asteroids that survive.
For each left-moving rock, check the right-moving rock on top.
If the top is smaller, it blows up. Pop and keep checking. If equal, both go.
If the new rock survives all fights, push it.

Time O(n), each rock pushed and popped once · Space O(n)

Corner cases

Both moving left never meet.
Equal sizes.

def asteroid_collision(rocks):
    st = []
    for a in rocks:
        while a < 0 and st and st[-1] > 0:
            if st[-1] < -a:
                st.pop(); continue
            if st[-1] == -a:
                st.pop()
            break
        else:
            st.append(a)
    return st

Search in Rotated Sorted Array

MediumBinary Search

A sorted list of distinct values was rotated. Find target in O(log n).

Example

[4,5,6,7,0,1,2], 0 → 4

How to solve

Use lo and hi to store the range.
At mid, one half is always sorted. Find which one.
If target lies in that sorted half's range, search there.
Else search the other half.

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

Corner cases

Not rotated.
Two values.
Target missing.

def search_rotated(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]:
            if nums[lo] <= target < nums[mid]: hi = mid - 1
            else: lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]: lo = mid + 1
            else: hi = mid - 1
    return -1

Find Minimum in Rotated Sorted Array

MediumBinary Search

Find the smallest value in a rotated sorted list of distinct values.

Example

[3, 4, 5, 1, 2] → 1

How to solve

Use lo and hi to store the range.
Compare nums[mid] with nums[hi].
If nums[mid] > nums[hi], it means the drop is to the right. Set lo = mid + 1.
Else the min is at mid or left. Set hi = mid.

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

Corner cases

Not rotated.
One value.

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

100

Koko Eating Bananas

MediumBinary Search

Koko eats k bananas per hour, one pile at a time. Find the smallest k that finishes all piles in h hours.

Example

piles = [3,6,7,11], h = 8 → 4

How to solve

Binary search on the speed k, from 1 to the biggest pile.
For a speed k, hours needed is the sum of ceil(pile / k).
If hours fit in h, it means k works. Try slower.
Else try faster.

Time O(n log max pile) · Space O(1)

Corner cases

h equals the number of piles, so k = max pile.
Huge piles.

def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)
    while lo < hi:
        k = (lo + hi) // 2
        if sum((p + k - 1) // k for p in piles) <= h:
            hi = k
        else:
            lo = k + 1
    return lo

101

Search a 2D Matrix

MediumBinary Search

Each row is sorted, and each row starts above the last row's end. Find target.

Example

[[1,3,5,7],[10,11,16,20],[23,30,34,60]], 3 → True

How to solve

Treat the matrix as one sorted list of R · C values.
Index i maps to row i // C and column i % C.
Run a normal binary search on i.

Time O(log(R · C)) · Space O(1)

Corner cases

Empty matrix.
One row.

def search_matrix(m, target):
    if not m or not m[0]:
        return False
    rows, cols = len(m), len(m[0])
    lo, hi = 0, rows * cols - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        v = m[mid // cols][mid % cols]
        if v == target:
            return True
        lo, hi = (mid + 1, hi) if v < target else (lo, mid - 1)
    return False

102

Find Peak Element

MediumBinary Search

Return any index whose value is bigger than both neighbors. Outside the list counts as minus infinity.

Example

[1, 2, 3, 1] → 2

How to solve

Use lo and hi to store the range.
Compare nums[mid] with nums[mid + 1].
If the next value is bigger, it means a peak lies right. Set lo = mid + 1.
Else a peak is at mid or left. Set hi = mid.

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

Corner cases

One value.
Values only rise or only fall.

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

103

First and Last Position in Sorted Array

MediumBinary Search

Return the first and last index of target in a sorted list, or [-1, -1].

Example

[5,7,7,8,8,10], 8 → [3, 4]

How to solve

Use bisect_left to find the first index >= target.
If that index is past the end or holds another value, it means target is missing.
Else use bisect_right - 1 for the last index.

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

Corner cases

Target missing.
Empty list.
All values equal target.

from bisect import bisect_left, bisect_right

def search_range(nums, target):
    l = bisect_left(nums, target)
    if l == len(nums) or nums[l] != target:
        return [-1, -1]
    return [l, bisect_right(nums, target) - 1]

104

Time Based Key-Value Store

MediumBinary Search

set(key, value, t) stores a value. get(key, t) returns the value with the largest time at or before t.

Example

set("foo","bar",1), get("foo",3) → "bar"
get("foo",0) → ""

How to solve

Use two hash maps: key=key, val=array of times, and key=key, val=array of values.
Set appends, since times come in rising order.
Get uses bisect_right on the times to find the last time <= t.
If there is none, return "".

Time O(1) set, O(log n) get · Space O(n)

Corner cases

Time before the first set returns "".
Unknown key.

from bisect import bisect_right
from collections import defaultdict

class TimeMap:
    def __init__(self):
        self.times = defaultdict(list)
        self.vals = defaultdict(list)

    def set(self, key, value, t):
        self.times[key].append(t)
        self.vals[key].append(value)

    def get(self, key, t):
        i = bisect_right(self.times[key], t)
        return self.vals[key][i - 1] if i else ""

105

Add Two Numbers

MediumLinked List

Two numbers are stored as linked lists, digits in reverse order. Return their sum as a list.

Example

2→4→3 + 5→6→4 → 7→0→8
342 + 465 = 807.

How to solve

Use a dummy node to store the start of the result, and carry.
While either list or the carry is left, add both digits and the carry.
Make a node with sum % 10. Keep sum // 10 as the carry.
Move along both lists.

Time O(max(n, m)) · Space O(max(n, m)), the output

Corner cases

Different lengths.
Final carry adds a node.

def add_two_numbers(a, b):
    dummy = tail = ListNode(0)
    carry = 0
    while a or b or carry:
        carry += (a.val if a else 0) + (b.val if b else 0)
        tail.next = ListNode(carry % 10)
        tail, carry = tail.next, carry // 10
        a, b = a and a.next, b and b.next
    return dummy.next

106

Remove Nth Node From End of List

MediumTwo Pointers

Remove the nth node from the end in one pass.

Example

1→2→3→4→5, n = 2 → 1→2→3→5

How to solve

Use a dummy node before the head, and two pointers.
Move fast n + 1 steps ahead.
Move both until fast is None. Now slow is just before the target.
Skip it with slow.next = slow.next.next.

Time O(n), one pass · Space O(1)

Corner cases

Remove the head.
One node list.

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

107

Reorder List

MediumLinked List

Reorder L0→L1→…→Ln into L0→Ln→L1→Ln-1→… in place.

Example

1→2→3→4→5 → 1→5→2→4→3

How to solve

Use fast and slow pointers to find the middle. Cut the list there.
Reverse the second half.
Weave: take one node from the first half, then one from the second, and repeat.

Time O(n) · Space O(1)

Corner cases

One or two nodes.
Cut the first half at the middle.

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

108

Copy List with Random Pointer

MediumLinked List

Deep copy a list where each node also has a random pointer.

Example

Nodes [7,null],[13,0],[11,4] → a new list with the same links

How to solve

Use a hash map, key=old node, val=new node.
Pass 1: make a copy of every node.
Pass 2: set each copy's next and random by looking up the map.

Time O(n) · Space O(n), the map

Corner cases

random is None.
random points to itself.
Empty list.

def copy_random_list(head):
    m = {None: None}
    n = head
    while n:
        m[n] = Node(n.val)
        n = n.next
    n = head
    while n:
        m[n].next, m[n].random = m[n.next], m[n.random]
        n = n.next
    return m[head]

109

LRU Cache

MediumDesign

Build a cache of fixed size. get and put run in O(1). When full, drop the least recently used key.

Example

cap 2: put(1,1), put(2,2), get(1) → 1, put(3,3) drops key 2

How to solve

Use an ordered hash map (Python OrderedDict), key=key, val=value, oldest first.
On get, if the key exists, move it to the end and return it.
On put, save it and move it to the end.
If size is over capacity, it means evict. Pop from the front.

Time O(1) per call · Space O(capacity)

Corner cases

Put on an existing key updates and refreshes it.
Capacity 1.

from collections import OrderedDict

class LRUCache:
    def __init__(self, cap):
        self.cap, self.d = cap, OrderedDict()

    def get(self, key):
        if key not in self.d:
            return -1
        self.d.move_to_end(key)
        return self.d[key]

    def put(self, key, val):
        self.d[key] = val
        self.d.move_to_end(key)
        if len(self.d) > self.cap:
            self.d.popitem(last=False)

110

Sort List

MediumLinked List

Sort a linked list in O(n log n) time.

Example

4→2→1→3 → 1→2→3→4

How to solve

Use merge sort.
Find the middle with fast and slow pointers. Cut the list in two.
Sort each half.
Merge the two sorted halves like Merge Two Sorted Lists.

Time O(n log n) · Space O(log n), the recursion

Corner cases

Empty or one node.
Start fast at head.next so two nodes split.

def sort_list(head):
    if not head or not head.next:
        return head
    slow, fast = head, head.next
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    mid, slow.next = slow.next, None
    a, b = sort_list(head), sort_list(mid)
    dummy = tail = ListNode(0)
    while a and b:
        if a.val <= b.val: tail.next, a = a, a.next
        else: tail.next, b = b, b.next
        tail = tail.next
    tail.next = a or b
    return dummy.next

111

String to Integer (atoi)

MediumStrings

Parse a string into a 32-bit int. Skip leading spaces, read an optional sign, then digits. Clamp to the range.

Example

" -42abc" → -42
"words 9" → 0

How to solve

Skip leading spaces.
Read an optional + or - sign.
Read digits one at a time: n = n * 10 + digit. Stop at a non-digit.
Apply the sign and clamp to the 32-bit range.

Time O(n) · Space O(1)

Corner cases

Empty or only spaces.
Sign with no digits.
Overflow.

def my_atoi(s):
    s = s.lstrip()
    sign, i, n = 1, 0, 0
    if s[:1] in ("-", "+"):
        sign = -1 if s[0] == "-" else 1
        i = 1
    while i < len(s) and s[i].isdigit():
        n = n * 10 + int(s[i]); i += 1
    return max(-2**31, min(sign * n, 2**31 - 1))

112

Longest Palindromic Substring

MediumStrings

Return the longest substring that is a palindrome.

Example

"babad" → "bab"
"cbbd" → "bb"

How to solve

Use best to store the longest palindrome found.
Every palindrome grows from a center: a char or a gap.
For each center, expand while both ends match.
If this one is longer than best, keep it.

Time O(n²) · Space O(1)

Corner cases

One char.
Even length palindromes.
All the same char.

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

113

Palindromic Substrings

MediumStrings

Count all substrings that are palindromes.

Example

"aaa" → 6

How to solve

Use count to store palindromes found.
Try all 2n - 1 centers: each char and each gap.
Expand while both ends match.
Each step of expansion is one more palindrome. Add 1.

Time O(n²) · Space O(1)

Corner cases

Each single char counts.
Empty string is 0.

def count_substrings(s):
    count = 0
    for c in range(2 * len(s) - 1):
        l, r = c // 2, c // 2 + c % 2
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1
            l, r = l - 1, r + 1
    return count

114

Gas Station

MediumGreedy

Stations sit in a circle. Return the start that lets you drive the full loop, or -1.

Example

gas = [1,2,3,4,5], cost = [3,4,5,1,2] → 3

How to solve

If total gas < total cost, it means no start works. Return -1.
Use tank for gas left and start for the candidate.
For each station, add gas - cost to the tank.
If the tank drops below 0, it means no start up to here works. Set start = i + 1, tank = 0.

Time O(n) · Space O(1)

Corner cases

Only one valid start exists.
One station.

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    tank = start = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start, tank = i + 1, 0
    return start

115

Jump Game

MediumGreedy

nums[i] is the max jump from i. Can you reach the last index?

Example

[2,3,1,1,4] → True
[3,2,1,0,4] → False

How to solve

Use far to store the farthest index you can reach.
For each index i, check if i > far.
If yes, it means you can never get here. Return False.
Else update far = max(far, i + nums[i]).

Time O(n) · Space O(1)

Corner cases

One value.
A zero at index 0 with more values.

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

116

Jump Game II

MediumGreedy

Return the fewest jumps to reach the last index. It is always reachable.

Example

[2,3,1,1,4] → 2

How to solve

Use end to store the edge of the current jump, and far for the farthest reach.
For each index, update far.
If i hits end, it means you must jump again. Count a jump and set end = far.
Stop before the last index.

Time O(n) · Space O(1)

Corner cases

One value needs 0 jumps.
Loop only to n - 2.

def jump(nums):
    jumps = end = far = 0
    for i in range(len(nums) - 1):
        far = max(far, i + nums[i])
        if i == end:
            jumps += 1
            end = far
    return jumps

117

Partition Labels

MediumGreedy

Split a string into as many parts as you can, so each letter is in only one part. Return part sizes.

Example

"ababcbacadefegdehijhklij" → [9, 7, 8]

How to solve

Use a hash map, key=letter, val=last index.
Walk the string. Grow the part's end to the last index of each char.
If i == end, it means no letter in this part shows up later. Close the part.
Start the next part at i + 1.

Time O(n) · Space O(26)

Corner cases

One letter repeated.
All unique letters.

def partition_labels(s):
    last = {ch: i for i, ch in enumerate(s)}
    out, start, end = [], 0, 0
    for i, ch in enumerate(s):
        end = max(end, last[ch])
        if i == end:
            out.append(end - start + 1)
            start = i + 1
    return out

118

Kth Largest Element in an Array

MediumHeap

Return the kth largest value in the list.

Example

[3,2,1,5,6,4], k = 2 → 5

How to solve

Use a min-heap of size k to store the k largest values seen. The top is the smallest of them.
Start with the first k values.
For each other value, check if it is bigger than the heap top.
If yes, replace the top. At the end, the top is the kth largest.

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

Corner cases

Duplicates count separately.
k = 1.
k = n.

import heapq

def find_kth_largest(nums, k):
    heap = nums[:k]
    heapq.heapify(heap)
    for x in nums[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)
    return heap[0]

119

K Closest Points to Origin

MediumHeap

Return the k points closest to (0, 0).

Example

[[1,3],[-2,2]], k = 1 → [[-2,2]]

How to solve

Compare points by squared distance x² + y². No sqrt is needed.
Use a max-heap of size k to keep the k closest. heapq.nsmallest does this for you.
If a closer point comes, it means the farthest in the heap must go. Pop the top.
Return those points.

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

Corner cases

Skip sqrt, it is not needed.
Ties.
k equals the count.

import heapq

def k_closest(points, k):
    return heapq.nsmallest(k, points, key=lambda p: p[0] ** 2 + p[1] ** 2)

120

Task Scheduler

MediumGreedy

Same tasks need n idle slots between them. Return the min total time.

Example

["A","A","A","B","B","B"], n = 2 → 8
A B idle A B idle A B.

How to solve

Use a hash map (counter), key=task, val=count. Let f be the top count.
Let m be how many tasks have count f.
The frame is (f - 1) blocks of size n + 1, plus m at the end.
Answer is max(len(tasks), (f - 1) * (n + 1) + m).

Time O(n) · Space O(26)

Corner cases

n = 0.
Many task types fill all idle slots.

from collections import Counter

def least_interval(tasks, n):
    cnt = Counter(tasks).values()
    f = max(cnt)
    m = sum(c == f for c in cnt)
    return max(len(tasks), (f - 1) * (n + 1) + m)

121

Binary Tree Level Order Traversal

MediumTrees / BFS

Return node values level by level, left to right.

Example

[3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]

How to solve

Use a queue to store the nodes of the current level.
Each round, pop exactly len(queue) nodes. That is one level.
Save their values as one list.
Push their children for the next round.

Time O(n) · Space O(w), the widest level

Corner cases

Empty tree.
Skewed tree.

from collections import deque

def level_order(root):
    out, q = [], deque([root] if root else [])
    while q:
        level = []
        for _ in range(len(q)):
            n = q.popleft()
            level.append(n.val)
            q.extend(c for c in (n.left, n.right) if c)
        out.append(level)
    return out

122

Binary Tree Zigzag Level Order

MediumTrees / BFS

Return levels, alternating left to right and right to left.

Example

[3,9,20,null,null,15,7] → [[3],[20,9],[15,7]]

How to solve

Use a queue for normal level order.
Collect each level's values as a list.
If the level number is odd, reverse that list before saving it.

Time O(n) · Space O(w), the widest level

Corner cases

Empty tree.
One node.

from collections import deque

def zigzag(root):
    out, q = [], deque([root] if root else [])
    while q:
        level = []
        for _ in range(len(q)):
            n = q.popleft()
            level.append(n.val)
            q.extend(c for c in (n.left, n.right) if c)
        out.append(level[::-1] if len(out) % 2 else level)
    return out

123

Binary Tree Right Side View

MediumTrees / BFS

Return the values you see when looking at the tree from the right side.

Example

[1,2,3,null,5,null,4] → [1, 3, 4]

How to solve

Use out to store one value per depth.
DFS, visiting the right child before the left.
If depth == len(out), it means this is the first node seen at this depth. It is the rightmost. Save it.

Time O(n) · Space O(h), the call stack

Corner cases

A left node can be seen when the right side is shorter.

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

124

Validate Binary Search Tree

MediumTrees

Is a tree a valid BST? Left subtree values are smaller and right subtree values are bigger, at every node.

Example

[5,1,4,null,null,3,6] → False
3 is in the right subtree of 5.

How to solve

Recurse with a range (lo, hi) that each node must fit in.
Start with minus and plus infinity.
If a node is outside its range, it means the BST rule is broken. Return False.
Go left with hi = node.val, right with lo = node.val.

Time O(n) · Space O(h), the call stack

Corner cases

Checking only the direct children is wrong.
Duplicates are not allowed.
Use infinities, not int limits.

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

125

Kth Smallest Element in a BST

MediumTrees

Return the kth smallest value in a BST.

Example

[3,1,4,null,2], k = 1 → 1

How to solve

Use a stack for an inorder walk, which visits values in sorted order.
Go left as far as you can, pushing nodes.
Pop a node and count it.
If the count reaches k, return it. Else move to the right child.

Time O(h + k) · Space O(h), the stack

Corner cases

k = 1.
k equals the node count.

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

126

Lowest Common Ancestor of a Binary Tree

MediumTrees

Return the lowest node that has both p and q below it, in any binary tree.

Example

[3,5,1,6,2,0,8], p = 5, q = 1 → 3

How to solve

Recurse on each node. Return the node if it is p, q, or None.
Get results from the left and right subtrees.
If both are not None, it means p and q split here. This node is the LCA.
Else pass up whichever side found something.

Time O(n) · Space O(h), the call stack

Corner cases

p is the ancestor of q.
Both nodes exist, as given.

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

127

Construct Binary Tree from Preorder and Inorder

MediumTrees

Rebuild a tree from its preorder and inorder lists. Values are unique.

Example

pre = [3,9,20,15,7], in = [9,3,15,20,7] → [3,9,20,null,null,15,7]

How to solve

Use a hash map, key=value, val=index in inorder.
The next preorder value is the root of the current range.
Its inorder index splits the range into left and right.
Build the left subtree first, then the right, since preorder lists left first.

Time O(n) · Space O(n), the map

Corner cases

One node.
Skewed tree.

def build_tree(preorder, inorder):
    idx = {v: i for i, v in enumerate(inorder)}
    it = iter(preorder)
    def build(l, r):
        if l > r:
            return None
        v = next(it)
        node = TreeNode(v)
        node.left = build(l, idx[v] - 1)
        node.right = build(idx[v] + 1, r)
        return node
    return build(0, len(inorder) - 1)

128

Count Good Nodes in Binary Tree

MediumTrees

A node is good if no node on the path from the root is bigger. Count good nodes.

Example

[3,1,4,3,null,1,5] → 4

How to solve

Recurse, passing down hi, the largest value on the path so far.
If node.val >= hi, it means no bigger node is above. Count it.
Update hi and recurse on both children.

Time O(n) · Space O(h), the call stack

Corner cases

Equal values count as good.
The root is always good.

def good_nodes(root, hi=float("-inf")):
    if not root:
        return 0
    good = root.val >= hi
    hi = max(hi, root.val)
    return good + good_nodes(root.left, hi) + good_nodes(root.right, hi)

129

Path Sum II

MediumTrees / Backtracking

Return every root to leaf path whose sum equals target.

Example

[5,4,8,11,null,13,4,7,2,null,null,5,1], 22 → [[5,4,11,2],[5,8,4,5]]

How to solve

Use path to store values on the current root-to-node path.
Add the node to path and subtract its value from the target.
If it is a leaf and the rest is 0, save a copy of path.
Recurse on children, then pop the node on the way back.

Time O(n²) worst, copying paths · Space O(h)

Corner cases

Save path[:], not path.
Negative values.
Empty tree.

def path_sum(root, target):
    out, path = [], []
    def dfs(n, rem):
        if not n:
            return
        path.append(n.val)
        if not n.left and not n.right and rem == n.val:
            out.append(path[:])
        dfs(n.left, rem - n.val)
        dfs(n.right, rem - n.val)
        path.pop()
    dfs(root, target)
    return out

130

Implement Trie (Prefix Tree)

MediumTrie

Build a trie with insert, search, and starts_with.

Example

insert("apple"), search("app") → False, starts_with("app") → True

How to solve

Use a trie. Each node is a hash map, key=char, val=child node.
Insert walks the word, making nodes as needed. Mark the end with $.
search walks the word and needs $ at the end.
starts_with only needs the walk to succeed.

Time O(L) per call, L = word length · Space O(total chars)

Corner cases

Empty string.
A word that is a prefix of another.

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

    def insert(self, word):
        n = self.root
        for ch in word:
            n = n.setdefault(ch, {})
        n["$"] = True

    def _find(self, s):
        n = self.root
        for ch in s:
            if ch not in n:
                return None
            n = n[ch]
        return n

    def search(self, word):
        n = self._find(word)
        return n is not None and "$" in n

    def starts_with(self, prefix):
        return self._find(prefix) is not None

131

Design Add and Search Words

MediumTrie

Add words, then search where . matches any one letter.

Example

add "bad", search ".ad" → True, search "b.." → True

How to solve

Use a trie of the words. Each node is a hash map, key=char, val=child node.
To search, walk the trie with DFS.
For a letter, follow that child.
For a ., try every child. If any path reaches $ at the end, return True.

Time O(L) add, O(26^dots · L) search · Space O(total chars)

Corner cases

All dots.
Word longer than any stored word.

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

    def add_word(self, word):
        n = self.root
        for ch in word:
            n = n.setdefault(ch, {})
        n["$"] = True

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

132

Subsets

MediumBacktracking

Return all subsets of a list of distinct values.

Example

[1, 2, 3] → [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

How to solve

Use out to store subsets, starting with [[]].
For each value x, copy every subset in out and add x to the copy.
Add the copies to out. Each value doubles the count.

Time O(n · 2^n) · Space O(n · 2^n), the output

Corner cases

Empty list gives [[]].
With duplicates, sort and skip repeats.

def subsets(nums):
    out = [[]]
    for x in nums:
        out += [s + [x] for s in out]
    return out

133

Permutations

MediumBacktracking

Return all orderings of a list of distinct values.

Example

[1, 2, 3] → 6 lists, from [1,2,3] to [3,2,1]

How to solve

Recurse with path, the values picked, and rest, the values left.
For each value in rest, pick it and recurse without it.
If rest is empty, it means a full ordering. Save path.

Time O(n · n!) · Space O(n · n!), the output

Corner cases

One value.
With duplicates, sort and skip used repeats.

def permute(nums):
    out = []
    def go(path, rest):
        if not rest:
            out.append(path); return
        for i in range(len(rest)):
            go(path + [rest[i]], rest[:i] + rest[i + 1:])
    go([], nums)
    return out

134

Combination Sum

MediumBacktracking

Return all unique combos from candidates that sum to target. Each value may be reused.

Example

[2,3,6,7], 7 → [[2,2,3],[7]]

How to solve

Recurse with a start index, the path, and the remaining sum.
If the remaining sum is 0, save path.
For each candidate from start on, if it fits, recurse with the same index i.
Same i means the value can be reused. Starting at start stops reordered repeats.

Time O(n^(target / min)) worst · Space O(target / min), the recursion

Corner cases

No combo works.
Sorting lets you break early.

def combination_sum(cands, target):
    out = []
    def go(start, path, rem):
        if rem == 0:
            out.append(path); return
        for i in range(start, len(cands)):
            if cands[i] <= rem:
                go(i, path + [cands[i]], rem - cands[i])
    go(0, [], target)
    return out

135

Combination Sum II

MediumBacktracking

Each value may be used once. The list has duplicates. Return unique combos that sum to target.

Example

[10,1,2,7,6,1,5], 8 → [[1,1,6],[1,2,5],[1,7],[2,6]]

How to solve

Sort the candidates.
Recurse with start, path, and the remaining sum. Use i + 1, since each value is used once.
If a value equals the one before at the same level, skip it. That stops repeat combos.
If a value is too big, stop the loop.

Time O(2^n) · Space O(n), the recursion

Corner cases

Duplicate combos.
No combo works.

def combination_sum2(cands, target):
    cands.sort()
    out = []
    def go(start, path, rem):
        if rem == 0:
            out.append(path); return
        for i in range(start, len(cands)):
            if i > start and cands[i] == cands[i - 1]:
                continue
            if cands[i] > rem:
                break
            go(i + 1, path + [cands[i]], rem - cands[i])
    go(0, [], target)
    return out

136

Word Search

MediumBacktracking

Can the word be traced on the grid through adjacent cells, using each cell once?

Example

Grid [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED" → True

How to solve

Try a DFS from every cell.
DFS checks if the cell matches word[i].
If yes, mark the cell as used, try 4 neighbors for i + 1, then unmark it.
If i reaches the word length, it means the whole word is found.

Time O(R · C · 3^L) · Space O(L), the recursion

Corner cases

Reusing a cell.
Word longer than the grid.
One cell grid.

def exist(board, word):
    R, C = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word):
            return True
        if not (0 <= r < R and 0 <= c < C) or board[r][c] != word[i]:
            return False
        board[r][c] = "#"
        found = any(dfs(r + dr, c + dc, i + 1)
                    for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)))
        board[r][c] = word[i]
        return found
    return any(dfs(r, c, 0) for r in range(R) for c in range(C))

137

Letter Combinations of a Phone Number

MediumBacktracking

Map digits 2 to 9 to phone letters. Return all letter strings the digits could stand for.

Example

"23" → ["ad","ae","af","bd","be","bf","cd","ce","cf"]

How to solve

Use a hash map, key=digit, val=letters.
Start out with [""].
For each digit, extend every string in out with each of its letters.
Empty input returns [].

Time O(4^n · n) · Space O(4^n · n), the output

Corner cases

Empty input returns [], not [""].
Digits 7 and 9 have 4 letters.

def letter_combinations(digits):
    if not digits:
        return []
    keys = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
    out = [""]
    for d in digits:
        out = [s + ch for s in out for ch in keys[d]]
    return out

138

Palindrome Partitioning

MediumBacktracking

Split a string so every part is a palindrome. Return all such splits.

Example

"aab" → [["a","a","b"],["aa","b"]]

How to solve

Recurse with a start index and the parts so far.
For each end, check if s[start:end] is a palindrome.
If yes, add it as a part and recurse from end.
If start reaches the end, it means a full split. Save it.

Time O(n · 2^n) · Space O(n), the recursion

Corner cases

One char.
All the same char gives many splits.

def partition(s):
    out = []
    def go(start, path):
        if start == len(s):
            out.append(path); return
        for end in range(start + 1, len(s) + 1):
            part = s[start:end]
            if part == part[::-1]:
                go(end, path + [part])
    go(0, [])
    return out

139

Number of Islands

MediumGraphs

Count groups of "1" cells joined up, down, left, or right.

Example

[["1","1","0"],["0","1","0"],["0","0","1"]] → 2

How to solve

Use count to store islands found.
Scan every cell.
If it is land, it means a new island. Add 1 and sink the whole island to water with DFS.
Sinking stops you from counting it twice.

Time O(R · C) · Space O(R · C), the call stack worst case

Corner cases

Empty grid.
Diagonals do not join.
Deep recursion on big grids, so BFS is safer.

def num_islands(grid):
    R, C = len(grid), len(grid[0])
    def sink(r, c):
        if 0 <= r < R and 0 <= c < C and grid[r][c] == "1":
            grid[r][c] = "0"
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                sink(r + dr, c + dc)
    count = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == "1":
                count += 1
                sink(r, c)
    return count

140

Max Area of Island

MediumGraphs

Return the size of the biggest island of 1s.

Example

An island of 6 cells is the largest → 6

How to solve

DFS from each cell returns the size of its island.
Water or outside the grid returns 0.
Land returns 1 plus the sizes of its 4 neighbors. Set it to 0 so it is counted once.
Keep the max size.

Time O(R · C) · Space O(R · C), the call stack

Corner cases

No land gives 0.
One big island.

def max_area_of_island(grid):
    R, C = len(grid), len(grid[0])
    def area(r, c):
        if not (0 <= r < R and 0 <= c < C) or grid[r][c] != 1:
            return 0
        grid[r][c] = 0
        return 1 + area(r + 1, c) + area(r - 1, c) + area(r, c + 1) + area(r, c - 1)
    return max((area(r, c) for r in range(R) for c in range(C)), default=0)

141

Clone Graph

MediumGraphs

Deep copy a connected undirected graph. Each node has val and neighbors.

Example

[[2,4],[1,3],[2,4],[1,3]] → the same shape, all new nodes

How to solve

Use a hash map, key=old node, val=copy.
DFS: if a node is already in the map, return its copy.
Else make the copy and save it before visiting neighbors.
Saving first stops infinite loops on cycles.

Time O(V + E) · Space O(V), the map

Corner cases

Empty graph.
One node with no neighbors.
Cycles.

def clone_graph(node):
    copies = {}
    def dfs(n):
        if n in copies:
            return copies[n]
        copies[n] = Node(n.val)
        copies[n].neighbors = [dfs(x) for x in n.neighbors]
        return copies[n]
    return dfs(node) if node else None

142

Rotting Oranges

MediumGraphs / BFS

Each minute, rotten oranges (2) rot fresh neighbors (1). Return the minutes until none are fresh, or -1.

Example

[[2,1,1],[1,1,0],[0,1,1]] → 4

How to solve

Use a queue to store all rotten oranges at the start. Count fresh ones.
Run BFS one level at a time. Each level is one minute.
Rot each fresh neighbor, lower the fresh count, and queue it.
If fresh oranges remain, it means some can never rot. Return -1.

Time O(R · C) · Space O(R · C), the queue

Corner cases

No fresh oranges gives 0.
A fresh orange that can never be reached gives -1.

from collections import deque

def oranges_rotting(g):
    R, C = len(g), len(g[0])
    q = deque((r, c) for r in range(R) for c in range(C) if g[r][c] == 2)
    fresh = sum(row.count(1) for row in g)
    mins = 0
    while q and fresh:
        mins += 1
        for _ in range(len(q)):
            r, c = q.popleft()
            for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
                if 0 <= nr < R and 0 <= nc < C and g[nr][nc] == 1:
                    g[nr][nc] = 2; fresh -= 1; q.append((nr, nc))
    return -1 if fresh else mins

143

Pacific Atlantic Water Flow

MediumGraphs

Water flows to cells of equal or lower height. Find cells that can reach both the Pacific (top and left) and Atlantic (bottom and right).

Example

A 5 x 5 height grid → 7 cells, like [0,4], [1,3], …

How to solve

Flip the problem: walk uphill from each ocean's edge.
Use one hash set of cells the Pacific edge reaches, and one for the Atlantic.
Move to a neighbor only if it is at least as high.
Cells in both hash sets are the answer.

Time O(R · C) · Space O(R · C), the sets

Corner cases

One row or one column.
Flat grid, so all cells qualify.

def pacific_atlantic(h):
    R, C = len(h), len(h[0])
    def reach(starts):
        seen, st = set(starts), list(starts)
        while st:
            r, c = st.pop()
            for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
                if (0 <= nr < R and 0 <= nc < C and (nr, nc) not in seen
                        and h[nr][nc] >= h[r][c]):
                    seen.add((nr, nc)); st.append((nr, nc))
        return seen
    pac = reach([(0, c) for c in range(C)] + [(r, 0) for r in range(R)])
    atl = reach([(R-1, c) for c in range(C)] + [(r, C-1) for r in range(R)])
    return [list(x) for x in pac & atl]

144

Surrounded Regions

MediumGraphs

Flip every "O" region to "X" unless it touches the border.

Example

An inner O group becomes X. An O on the edge stays.

How to solve

DFS from every O on the border. Mark it S for safe.
Any O still left cannot reach the border. Flip it to X.
Turn every S back to O.

Time O(R · C) · Space O(R · C), the call stack

Corner cases

All O.
Grid with one row.

def solve(board):
    R, C = len(board), len(board[0])
    def mark(r, c):
        if 0 <= r < R and 0 <= c < C and board[r][c] == "O":
            board[r][c] = "S"
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                mark(r + dr, c + dc)
    for r in range(R):
        mark(r, 0); mark(r, C - 1)
    for c in range(C):
        mark(0, c); mark(R - 1, c)
    for r in range(R):
        for c in range(C):
            board[r][c] = "O" if board[r][c] == "S" else "X"

145

Course Schedule

MediumTopological Sort

pre[i] = [a, b] means take b before a. Can you finish all n courses?

Example

n = 2, [[1,0],[0,1]] → False
It is a cycle.

How to solve

Use a graph as an adjacency list, index=course, val=courses that need it.
Use an array indeg, index=course, val=prerequisites left.
Queue every course with 0 prerequisites.
Pop a course, count it done, and lower its next courses' counts. Queue any that hit 0.
If all n are done, it means no cycle. Return True.

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

Corner cases

No prerequisites.
A course that needs itself.
Separate groups.

from collections import deque

def can_finish(n, pre):
    adj, indeg = [[] for _ in range(n)], [0] * n
    for a, b in pre:
        adj[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 adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return done == n

146

Course Schedule II

MediumTopological Sort

Return an order to take all courses, or [] if it cannot be done.

Example

n = 4, [[1,0],[2,0],[3,1],[3,2]] → [0,1,2,3]

How to solve

Same as Course Schedule.
Use order to store courses in the order you pop them.
If order has all n courses, return it.
Else it means a cycle. Return [].

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

Corner cases

Many valid orders exist.
Cycle gives [].

from collections import deque

def find_order(n, pre):
    adj, indeg = [[] for _ in range(n)], [0] * n
    for a, b in pre:
        adj[b].append(a); indeg[a] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft(); order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []

147

Number of Connected Components

MediumUnion Find

Count connected groups in an undirected graph of n nodes.

Example

n = 5, [[0,1],[1,2],[3,4]] → 2

How to solve

Use union find (disjoint set). Array parent, index=node, val=parent node. The root is the group leader.
Start with n groups.
For each edge, find both leaders.
If they differ, it means two groups join. Link them and lower the count by 1.

Time O(E · α(n)), nearly linear · Space O(n)

Corner cases

No edges gives n.
Repeat edges.

def count_components(n, edges):
    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:
            parent[ra] = rb
            n -= 1
    return n

148

Graph Valid Tree

MediumUnion Find

Do n nodes and these edges form a tree? It must be connected with no cycle.

Example

n = 5, [[0,1],[0,2],[0,3],[1,4]] → True

How to solve

A tree has exactly n - 1 edges. If not, return False.
Use union find (disjoint set), array parent, index=node, val=parent node.
For each edge, find both leaders.
If they are the same, it means the edge closes a cycle. Return False. Else link them.

Time O(n · α(n)) · Space O(n)

Corner cases

n = 1, no edges is True.
Right edge count but split in two.

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

149

Redundant Connection

MediumUnion Find

A tree got one extra edge. Return the edge that can be removed. If there are many, return the last one.

Example

[[1,2],[1,3],[2,3]] → [2,3]

How to solve

Use union find (disjoint set), array parent, index=node, val=parent node.
For each edge in order, find both leaders.
If they are already the same, it means this edge makes a cycle. Return it.
Else link the groups.

Time O(n · α(n)) · Space O(n)

Corner cases

Nodes are 1-based.
The cycle may be long.

def find_redundant(edges):
    parent = list(range(len(edges) + 1))
    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 [a, b]
        parent[ra] = rb

150

Shortest Path in Binary Matrix

MediumGraphs / BFS

Find the shortest clear path of 0s from top left to bottom right. You may move in 8 directions. Return the cell count, or -1.

Example

[[0,1],[1,0]] → 2

How to solve

If the start or end is blocked, return -1.
Use a queue to store (row, col, path length) for BFS.
Pop a cell. If it is the end, return its length.
Else push each open neighbor in 8 directions and mark it visited.

Time O(n²) · Space O(n²), the queue

Corner cases

Start or end is 1.
1 x 1 grid with 0 gives 1.

from collections import deque

def shortest_path(grid):
    n = len(grid)
    if grid[0][0] or grid[-1][-1]:
        return -1
    q, grid[0][0] = deque([(0, 0, 1)]), 1
    while q:
        r, c, d = q.popleft()
        if r == c == n - 1:
            return d
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                    grid[nr][nc] = 1; q.append((nr, nc, d + 1))
    return -1

151

Network Delay Time

MediumShortest Paths

A signal leaves node k over weighted directed edges. How long until all n nodes get it? Return -1 if some never do.

Example

times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 → 2

How to solve

Use a graph as an adjacency list: a hash map, key=node, val=list of (next, time).
Use a min-heap of (time, node), starting with (0, k). The top is the closest node.
Pop the smallest time. If the node is settled, skip it. Else settle it and push its neighbors.
If all n are settled, return the max time. Else -1.

Time O(E log V) · Space O(V + E)

Corner cases

Unreachable node gives -1.
Several edges between the same pair.

import heapq
from collections import defaultdict

def network_delay(times, n, k):
    adj = defaultdict(list)
    for u, v, w in times:
        adj[u].append((v, w))
    dist, heap = {}, [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in dist:
            continue
        dist[u] = d
        for v, w in adj[u]:
            if v not in dist:
                heapq.heappush(heap, (d + w, v))
    return max(dist.values()) if len(dist) == n else -1

152

Cheapest Flights Within K Stops

MediumShortest Paths

Find the cheapest price from src to dst using at most k stops. Return -1 if none.

Example

n = 4, flights [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], 0 → 3, k = 1 → 700

How to solve

Use an array cost, index=city, val=cheapest price so far. Start with cost[src] = 0.
Repeat k + 1 times, once per flight allowed.
Copy cost. For each flight, try to lower the copy using the old prices.
Using old prices means each round adds only one more flight.

Time O(k · E) · Space O(n)

Corner cases

k = 0 means direct flights only.
No route.

def find_cheapest_price(n, flights, src, dst, k):
    INF = float("inf")
    cost = [INF] * n
    cost[src] = 0
    for _ in range(k + 1):
        nxt = cost[:]
        for u, v, w in flights:
            if cost[u] + w < nxt[v]:
                nxt[v] = cost[u] + w
        cost = nxt
    return -1 if cost[dst] == INF else cost[dst]

153

Min Cost to Connect All Points

MediumMinimum Spanning Tree

Connect all points. Edge cost is the Manhattan distance. Return the min total cost.

Example

[[0,0],[2,2],[3,10],[5,2],[7,0]] → 20

How to solve

Use Prim's algorithm. Use an array best, index=point, val=cheapest link to the tree.
Start with point 0 at cost 0.
Each round, add the unused point with the smallest best. Add its cost.
Update best for the rest using distances to the new point.

Time O(n²) · Space O(n)

Corner cases

One point gives 0.
Duplicate points.

def min_cost_connect(points):
    n = len(points)
    best = [float("inf")] * n
    best[0], used, total = 0, [False] * n, 0
    for _ in range(n):
        u = min((i for i in range(n) if not used[i]), key=best.__getitem__)
        used[u], total = True, total + best[u]
        for v in range(n):
            if not used[v]:
                d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
                best[v] = min(best[v], d)
    return total

154

House Robber

MediumDynamic Programming

You cannot rob two houses next to each other. Return the most money you can take.

Example

[2, 7, 9, 3, 1] → 12
Houses 2 + 9 + 1.

How to solve

Use a and b to store the best total up to two houses back and one house back.
For each house x, choose: skip it (b) or rob it (a + x).
New best is max(b, a + x). Slide the pair.

Time O(n) · Space O(1)

Corner cases

Empty list.
One house.

def rob(nums):
    a = b = 0
    for x in nums:
        a, b = b, max(b, a + x)
    return b

155

House Robber II

MediumDynamic Programming

Same as House Robber, but the houses are in a circle.

Example

[2, 3, 2] → 3

How to solve

The first and last houses touch, so you cannot rob both.
Run House Robber on all houses but the first.
Run it on all houses but the last.
Return the bigger result. One house returns its value.

Time O(n) · Space O(n), the slices

Corner cases

One house, so return it.
Two houses.

def rob_circle(nums):
    def line(arr):
        a = b = 0
        for x in arr:
            a, b = b, max(b, a + x)
        return b
    if len(nums) == 1:
        return nums[0]
    return max(line(nums[1:]), line(nums[:-1]))

156

Coin Change

MediumDynamic Programming

Return the fewest coins that make the amount. Return -1 if it cannot be done.

Example

coins = [1, 2, 5], amount = 11 → 3
5 + 5 + 1.

How to solve

Use a DP array dp, index=amount a, val=fewest coins for a. dp[0] = 0.
For each amount a, try each coin c.
If c <= a, dp[a] = min(dp[a], dp[a - c] + 1).
If dp[amount] is still infinity, it means no way. Return -1.

Time O(amount · coins) · Space O(amount)

Corner cases

amount = 0 gives 0.
Greedy fails for coins like [1, 3, 4], amount 6.

def coin_change(coins, amount):
    INF = float("inf")
    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]

157

Coin Change II

MediumDynamic Programming

Count the ways to make the amount. Each coin is unlimited.

Example

amount = 5, coins = [1, 2, 5] → 4

How to solve

Use a DP array dp, index=amount a, val=number of ways to make a. dp[0] = 1.
Loop coins on the outside.
For each amount a from c up, add dp[a - c].
Coins outside means each combo is counted once, not once per order.

Time O(amount · coins) · Space O(amount)

Corner cases

amount = 0 gives 1.
Swapping the loops counts orders, which is wrong.

def change(amount, coins):
    dp = [1] + [0] * amount
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

158

Longest Increasing Subsequence

MediumDynamic Programming

Return the length of the longest strictly increasing subsequence.

Example

[10,9,2,5,3,7,101,18] → 4
Like [2,3,7,101].

How to solve

Use tails, where tails[i] stores the smallest end of any rising run of length i + 1.
For each value x, binary search the first tail >= x.
If none, it means x extends the longest run. Append it.
Else replace that tail with x. The answer is len(tails).

Time O(n log n) · Space O(n)

Corner cases

Equal values do not count as rising.
tails is not the real sequence.

from bisect import bisect_left

def length_of_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)

159

Word Break

MediumDynamic Programming

Can the string be split into words from the dictionary?

Example

"leetcode", ["leet", "code"] → True

How to solve

Use a DP array dp, index=i, val=True if s[:i] can be split. dp[0] = True.
For each i, try each split point j.
If dp[j] is True and s[j:i] is a word, it means s[:i] can be split.
Return dp[n].

Time O(n²) slices · Space O(n)

Corner cases

Words can repeat.
Empty string is True.

def word_break(s, words):
    words = set(words)
    dp = [True] + [False] * len(s)
    for i in range(1, len(s) + 1):
        dp[i] = any(dp[j] and s[j:i] in words for j in range(i))
    return dp[-1]

160

Unique Paths

MediumDynamic Programming

A robot moves only right or down on an m x n grid. How many paths go from top left to bottom right?

Example

m = 3, n = 7 → 28

How to solve

Use a 1D DP array row, index=column j, val=paths to that cell. Start all as 1.
For each next row, row[j] += row[j - 1].
That is paths from above plus paths from the left.
Return the last cell.

Time O(m · n) · Space O(n)

Corner cases

One row or one column gives 1.

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

161

Longest Common Subsequence

MediumDynamic Programming

Return the length of the longest subsequence found in both strings.

Example

"abcde", "ace" → 3

How to solve

Use a 2D DP table, dp[i][j] = LCS of a[:i] and b[:j]. Keep one row at a time.
If a[i] equals b[j], take the diagonal + 1.
Else take the max of the cell above and the cell to the left.
Return the last cell.

Time O(n · m) · Space O(m)

Corner cases

An empty string gives 0.
No common chars.

def lcs(a, b):
    prev = [0] * (len(b) + 1)
    for x in a:
        cur = [0]
        for j, y in enumerate(b):
            cur.append(prev[j] + 1 if x == y else max(prev[j + 1], cur[j]))
        prev = cur
    return prev[-1]

162

Decode Ways

MediumDynamic Programming

Letters map A=1 to Z=26. Count the ways to decode a digit string.

Example

"226" → 3
2 2 6, 22 6, 2 26.

How to solve

Use a and b to store the ways for two digits back and one digit back.
For each digit, if it is not 0, it can stand alone. Add b.
If the last two digits form 10 to 26, they can pair. Add a.
Slide the pair forward.

Time O(n) · Space O(1)

Corner cases

A leading "0" gives 0.
"06" is not valid.
"100" gives 0.

def num_decodings(s):
    a, b = 1, int(s[0] != "0")
    for i in range(1, len(s)):
        c = b if s[i] != "0" else 0
        if 10 <= int(s[i - 1:i + 1]) <= 26:
            c += a
        a, b = b, c
    return b

163

Partition Equal Subset Sum

MediumDynamic Programming

Can the list be split into two groups with equal sums?

Example

[1, 5, 11, 5] → True
[1, 5, 5] and [11].

How to solve

If the total is odd, return False.
Use a hash set to store every sum some subset can reach. Start with {0}.
For each value x, add s + x for every sum s in the hash set.
If total / 2 is in the hash set, it means an equal split exists.

Time O(n · total) · Space O(total)

Corner cases

Odd total.
One value.

def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    sums = {0}
    for x in nums:
        sums |= {s + x for s in sums}
    return total // 2 in sums

164

Target Sum

MediumDynamic Programming

Put + or - before each value. Count the ways to reach target.

Example

[1, 1, 1, 1, 1], 3 → 5

How to solve

Use a hash map (counter), key=running sum, val=number of ways. Start with {0: 1}.
For each value x, every sum s branches to s + x and s - x.
Carry the counts into a new hash map.
Return the count for target.

Time O(n · total) · Space O(total)

Corner cases

Zeros double the count.
Target out of reach.

from collections import Counter

def find_target_sum_ways(nums, target):
    ways = Counter({0: 1})
    for x in nums:
        nxt = Counter()
        for s, c in ways.items():
            nxt[s + x] += c
            nxt[s - x] += c
        ways = nxt
    return ways[target]

165

Best Time to Buy and Sell Stock with Cooldown

MediumDynamic Programming

Trade as often as you like. After a sale, you must wait one day before you buy. Return the max profit.

Example

[1, 2, 3, 0, 2] → 3
Buy, sell, cooldown, buy, sell.

How to solve

Use three states: hold (own a share), sold (sold today), rest (free to buy).
For each price: hold = keep holding, or buy from rest.
sold = sell what you hold. rest = stay resting, or come off yesterday's sale.
Return max(sold, rest).

Time O(n) · Space O(1)

Corner cases

One day.
Prices only fall.

def max_profit_cooldown(prices):
    hold, sold, rest = float("-inf"), 0, 0
    for p in prices:
        hold, sold, rest = max(hold, rest - p), hold + p, max(rest, sold)
    return max(sold, rest)

166

Interleaving String

MediumDynamic Programming

Is s3 made by mixing s1 and s2 while keeping each one's order?

Example

"aabcc", "dbbca", "aadbbcbcac" → True

How to solve

If lengths do not add up, return False.
Recurse on (i, j), chars used from s1 and s2. Memoize in a hash map, key=(i, j), val=result.
If s1[i] matches the next char of s3, try taking it. Same for s2[j].
If i + j reaches the end of s3, it means success.

Time O(n · m) · Space O(n · m), the cache

Corner cases

Length mismatch.
Empty strings.

from functools import cache

def is_interleave(s1, s2, s3):
    if len(s1) + len(s2) != len(s3):
        return False
    @cache
    def go(i, j):
        if i + j == len(s3):
            return True
        return ((i < len(s1) and s1[i] == s3[i + j] and go(i + 1, j))
                or (j < len(s2) and s2[j] == s3[i + j] and go(i, j + 1)))
    return go(0, 0)

Hard · 34 questions

167

Trapping Rain Water

HardTwo Pointers

Bars have heights. Return how much rain water is trapped between them.

Example

[0,1,0,2,1,0,1,3,2,1,2,1] → 6

How to solve

Use two pointers l and r, with lmax and rmax for the tallest bar seen on each side.
Water on a bar is side max - its height.
Move the side with the lower bar. Its max is the real limit, since the other side is taller.
Add that side's water and step inward.

Time O(n) · Space O(1)

Corner cases

Fewer than 3 bars.
Heights only rise.

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

168

Median of Two Sorted Arrays

HardBinary Search

Return the median of two sorted lists in O(log(min(m, n))).

Example

[1, 3], [2] → 2.0
[1, 2], [3, 4] → 2.5

How to solve

Binary search a cut i in the shorter list a.
Cut b at j = half - i, so the left side holds half the values.
If a_left <= b_right and b_left <= a_right, it means the cut is right. The median comes from the 4 edge values.
If a_left is too big, move i left. Else move it right.

Time O(log(min(m, n))) · Space O(1)

Corner cases

One list empty.
Odd vs even total.
Use infinities at the edges.

def find_median(a, b):
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    lo, hi, half = 0, m, (m + n + 1) // 2
    INF = float("inf")
    while True:
        i = (lo + hi) // 2
        j = half - i
        al = a[i - 1] if i else -INF
        ar = a[i] if i < m else INF
        bl = b[j - 1] if j else -INF
        br = b[j] if j < n else INF
        if al <= br and bl <= ar:
            if (m + n) % 2:
                return float(max(al, bl))
            return (max(al, bl) + min(ar, br)) / 2
        if al > br: hi = i - 1
        else: lo = i + 1

169

Minimum Window Substring

HardSliding Window

Return the smallest window of s that holds every char of t, counting repeats.

Example

s = "ADOBECODEBANC", t = "ABC" → "BANC"

How to solve

Use a hash map (counter), key=char, val=count still needed, and missing for the total still needed.
Grow the window right. If the char was needed, lower missing.
When missing is 0, it means the window holds all of t. Record it, then shrink from the left.
Stop shrinking once a needed char leaves.

Time O(n + m) · Space O(alphabet)

Corner cases

t longer than s.
Repeats in t.
No window gives "".

from collections import Counter

def min_window(s, t):
    need, missing = Counter(t), len(t)
    left, best = 0, (0, float("inf"))
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        while missing == 0:
            if right - left < best[1] - best[0]:
                best = (left, right)
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
    return "" if best[1] == float("inf") else s[best[0]:best[1] + 1]

170

Sliding Window Maximum

HardMonotonic Deque

Return the max of every window of size k.

Example

[1,3,-1,-3,5,3,6,7], k = 3 → [3,3,5,5,6,7]

How to solve

Use a monotonic deque (double-ended queue) of indexes, values falling from front to back.
For each new value, pop smaller values from the back. They can never be a max again.
If the front index has left the window, pop it.
The front is the max of this window.

Time O(n), each index added and removed once · Space O(k)

Corner cases

k = 1.
k equals the length.
Equal values.

from collections import deque

def max_sliding_window(nums, k):
    dq, out = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

171

Largest Rectangle in Histogram

HardMonotonic Stack

Return the area of the largest rectangle in a histogram.

Example

[2, 1, 5, 6, 2, 3] → 10

How to solve

Use a monotonic stack of bar indexes, heights rising from bottom to top. Start it with -1.
For each bar, while the top bar is taller, pop it.
The popped bar spans from the new top + 1 to i - 1. Area is height × that width.
Add a 0 bar at the end so every bar gets popped.

Time O(n) · Space O(n), the stack

Corner cases

All bars equal.
Rising or falling heights.
One bar.

def largest_rectangle(heights):
    st, best = [-1], 0
    for i, h in enumerate(heights + [0]):
        while st[-1] != -1 and heights[st[-1]] >= h:
            height = heights[st.pop()]
            best = max(best, height * (i - st[-1] - 1))
        st.append(i)
    return best

172

Maximal Rectangle

HardMonotonic Stack

In a grid of "0" and "1", find the largest rectangle of only 1s.

Example

A 4 x 5 grid → 6

How to solve

Use an array h, index=column, val=count of 1s stacked up to this row.
For each row, grow h[j] on a 1 and reset it on a 0.
Now each row is a histogram.
Run Largest Rectangle on it and keep the max.

Time O(R · C) · Space O(C)

Corner cases

Empty grid.
All zeros.

def maximal_rectangle(matrix):
    if not matrix:
        return 0
    h, best = [0] * len(matrix[0]), 0
    for row in matrix:
        h = [h[j] + 1 if v == "1" else 0 for j, v in enumerate(row)]
        st = [-1]
        for i, x in enumerate(h + [0]):
            while st[-1] != -1 and h[st[-1]] >= x:
                height = h[st.pop()]
                best = max(best, height * (i - st[-1] - 1))
            st.append(i)
    return best

173

Merge k Sorted Lists

HardHeap

Merge k sorted linked lists into one sorted list.

Example

[1→4→5, 1→3→4, 2→6] → 1→1→2→3→4→4→5→6

How to solve

Use a min-heap of (value, list id, node) for the head of each list. The top is the smallest head.
Pop the smallest node and attach it to the result.
If it has a next node, push that next node.
The list id breaks ties, so nodes are never compared.

Time O(N log k), N total nodes · Space O(k), the heap

Corner cases

Empty lists inside.
k = 0.
Add an index to the heap tuple so nodes are never compared.

import heapq

def merge_k_lists(lists):
    heap = [(n.val, i, n) for i, n in enumerate(lists) if n]
    heapq.heapify(heap)
    dummy = tail = ListNode(0)
    while heap:
        _, i, n = heapq.heappop(heap)
        tail.next = tail = n
        if n.next:
            heapq.heappush(heap, (n.next.val, i, n.next))
    return dummy.next

174

Reverse Nodes in k-Group

HardLinked List

Reverse the list k nodes at a time. A last group shorter than k stays as it is.

Example

1→2→3→4→5, k = 2 → 2→1→4→3→5

How to solve

Use a dummy node, and prev_tail for the end of the last done group.
Check that k nodes are left. If not, stop.
Reverse those k nodes.
Link prev_tail to the new group head. The old group head is the new prev_tail.

Time O(n) · Space O(1)

Corner cases

k = 1 changes nothing.
Length is a multiple of k.

def reverse_k_group(head, k):
    dummy = prev_tail = ListNode(0, head)
    while True:
        node = prev_tail
        for _ in range(k):
            node = node.next
            if not node:
                return dummy.next
        prev, cur = node.next, prev_tail.next
        for _ in range(k):
            cur.next, prev, cur = prev, cur, cur.next
        first = prev_tail.next
        prev_tail.next = prev
        prev_tail = first

175

Binary Tree Maximum Path Sum

HardTrees

A path joins any nodes through parent links. Return the max path sum.

Example

[-10,9,20,null,null,15,7] → 42
Path 15→20→7.

How to solve

Use best to store the best path found.
A helper returns the best downward path from a node. A negative side counts as 0.
At each node, val + left + right is a path that bends here. Update best.
Return val + max(left, right) up, since a parent can use only one side.

Time O(n) · Space O(h), the call stack

Corner cases

All negative, so the answer is the biggest node.
Drop negative gains.

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

176

Serialize and Deserialize Binary Tree

HardTrees

Turn a tree into a string, and turn the string back into the same tree.

Example

[1,2,3,null,null,4,5] → "1,2,#,#,3,4,#,#,5,#,#" → same tree

How to solve

To encode, walk the tree in preorder. Write each value, and # for None.
To decode, read the tokens in the same order with an iterator.
A # means None. Else make a node, then build its left, then its right.

Time O(n) · Space O(n)

Corner cases

Empty tree.
Negative or multi digit values.
Deep trees and recursion limits.

def serialize(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(data):
    it = iter(data.split(","))
    def build():
        v = next(it)
        if v == "#":
            return None
        return TreeNode(int(v), build(), build())
    return build()

177

Word Search II

HardTrie / Backtracking

Find every word from a list that can be traced on the grid.

Example

Grid of letters, words ["oath","pea","eat","rain"] → ["eat","oath"]

How to solve

Use a trie of all the words. Each node is a hash map, key=char, val=child node. Store the full word at its end node.
DFS from each cell, walking the trie with the path.
If a node holds a word, it means a match. Save it and remove it so it is found once.
Prune trie nodes that become empty, to speed up later searches.

Time O(R · C · 4^L) worst · Space O(total chars), the trie

Corner cases

The same word found twice.
Reusing a cell.
Prune empty trie nodes for speed.

def find_words(board, words):
    root = {}
    for w in words:
        n = root
        for ch in w:
            n = n.setdefault(ch, {})
        n["$"] = w
    R, C, out = len(board), len(board[0]), []
    def dfs(r, c, parent):
        ch = board[r][c]
        node = parent[ch]
        if "$" in node:
            out.append(node.pop("$"))
        board[r][c] = "#"
        for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
            if 0 <= nr < R and 0 <= nc < C and board[nr][nc] in node:
                dfs(nr, nc, node)
        board[r][c] = ch
        if not node:
            parent.pop(ch)
    for r in range(R):
        for c in range(C):
            if board[r][c] in root:
                dfs(r, c, root)
    return out

178

Word Ladder

HardGraphs / BFS

Change one letter at a time. Each step must be a word in the list. Return the length of the shortest chain from begin to end, or 0.

Example

"hit" → "cog", list ["hot","dot","dog","lot","log","cog"] → 5

How to solve

Use a hash set to store words not yet used.
Use a queue to store (word, steps) for BFS from begin.
For each word, try every one-letter change.
If the new word is in the hash set, remove it and queue it. The first time you reach end is the shortest.

Time O(n · L · 26) · Space O(n)

Corner cases

end not in the list gives 0.
begin equals end.

from collections import deque
from string import ascii_lowercase

def ladder_length(begin, end, words):
    words = set(words)
    if end not in words:
        return 0
    q = deque([(begin, 1)])
    while q:
        w, d = q.popleft()
        if w == end:
            return d
        for i in range(len(w)):
            for ch in ascii_lowercase:
                nw = w[:i] + ch + w[i + 1:]
                if nw in words:
                    words.remove(nw)
                    q.append((nw, d + 1))
    return 0

179

Alien Dictionary

HardTopological Sort

Words are sorted in an alien alphabet. Return a valid letter order, or "" if none.

Example

["wrt","wrf","er","ett","rftt"] → "wertf"

How to solve

Use a graph as an adjacency list: a hash map, key=letter, val=hash set of letters after it.
Compare each pair of next words. The first different char gives one edge.
If a longer word comes before its own prefix, it means the order is invalid. Return "".
Run topological sort. If not every letter comes out, there is a cycle. Return "".

Time O(total chars) · Space O(26²)

Corner cases

A word before its own prefix, like ["abc","ab"], is invalid.
Letters with no edges still count.

from collections import deque

def alien_order(words):
    adj = {c: set() for w in words for c in w}
    indeg = {c: 0 for c in adj}
    for a, b in zip(words, words[1:]):
        for x, y in zip(a, b):
            if x != y:
                if y not in adj[x]:
                    adj[x].add(y); indeg[y] += 1
                break
        else:
            if len(a) > len(b):
                return ""
    q = deque(c for c in indeg if indeg[c] == 0)
    out = []
    while q:
        c = q.popleft(); out.append(c)
        for d in adj[c]:
            indeg[d] -= 1
            if indeg[d] == 0:
                q.append(d)
    return "".join(out) if len(out) == len(adj) else ""

180

Find Median from Data Stream

HardTwo Heaps

Support add_num and find_median as numbers stream in.

Example

add 1, add 2, median → 1.5, add 3, median → 2

How to solve

Use a max-heap lo for the smaller half, and a min-heap hi for the bigger half. Python heapq is a min-heap, so store negated values in lo.
To add, push into lo, then move lo's top into hi. This keeps the order right.
If hi is bigger, move its top back to lo.
Median is lo's top, or the average of both tops.

Time O(log n) add, O(1) median · Space O(n)

Corner cases

Even vs odd count.
Negatives.
Push through the other heap to keep order.

import heapq

class MedianFinder:
    def __init__(self):
        self.lo, self.hi = [], []

    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

181

Edit Distance

HardDynamic Programming

Return the fewest inserts, deletes, or replaces to turn a into b.

Example

"horse" → "ros" → 3

How to solve

Use a 2D DP table, dp[i][j] = cost to turn a[:i] into b[:j]. Keep one row.
An empty side costs the length of the other side.
If the chars match, copy the diagonal.
Else take 1 + the min of insert, delete, or replace.

Time O(n · m) · Space O(m)

Corner cases

An empty string costs the other's length.
Equal strings cost 0.

def min_distance(a, b):
    prev = list(range(len(b) + 1))
    for i, x in enumerate(a, 1):
        cur = [i]
        for j, y in enumerate(b, 1):
            cur.append(prev[j - 1] if x == y
                       else 1 + min(prev[j], cur[j - 1], prev[j - 1]))
        prev = cur
    return prev[-1]

182

Regular Expression Matching

HardDynamic Programming

Match the whole string s to pattern p. . matches any char. * means zero or more of the char before it.

Example

"aa", "a*" → True
"ab", ".*" → True
"mississippi", "mis*is*p*." → False

How to solve

Recurse on (i, j), the positions in s and p. Memoize in a hash map, key=(i, j), val=result.
first is True if s[i] matches p[j] or p[j] is ..
If the next pattern char is *: skip x*, or use one char of s if first.
Else need first, then move both.

Time O(n · m) · Space O(n · m), the cache

Corner cases

Empty string with "a*b*" is True.
Pattern starts with * is not allowed.

from functools import cache

def is_match(s, p):
    @cache
    def go(i, j):
        if j == len(p):
            return i == len(s)
        first = i < len(s) and p[j] in (s[i], ".")
        if j + 1 < len(p) and p[j + 1] == "*":
            return go(i, j + 2) or (first and go(i + 1, j))
        return first and go(i + 1, j + 1)
    return go(0, 0)

183

Wildcard Matching

HardDynamic Programming

Match the whole string to a pattern. ? matches one char. * matches any sequence, even empty.

Example

"adceb", "*a*b" → True
"cb", "?a" → False

How to solve

Recurse on (i, j), the positions in s and p. Memoize in a hash map, key=(i, j), val=result.
If p[j] is *: match nothing with (i, j+1), or eat one char with (i+1, j).
If p[j] is ? or equals s[i], move both.
If j reaches the end, it is a match only if i did too.

Time O(n · m) · Space O(n · m), the cache

Corner cases

Pattern of only *.
Empty string.
Many * in a row.

from functools import cache

def is_wild_match(s, p):
    @cache
    def go(i, j):
        if j == len(p):
            return i == len(s)
        if p[j] == "*":
            return go(i, j + 1) or (i < len(s) and go(i + 1, j))
        return i < len(s) and p[j] in (s[i], "?") and go(i + 1, j + 1)
    return go(0, 0)

184

Longest Valid Parentheses

HardStack

Return the length of the longest well formed bracket substring.

Example

")()())" → 4

How to solve

Use a stack to store indexes. Start with -1 as the base before a valid run.
On (, push its index.
On ), pop. If the stack is empty, it means this ) breaks the run. Push it as the new base.
Else the valid run is i - top. Keep the max.

Time O(n) · Space O(n)

Corner cases

Empty string.
All ).
Nested and side by side, like "()(())".

def longest_valid_parentheses(s):
    st, best = [-1], 0
    for i, ch in enumerate(s):
        if ch == "(":
            st.append(i)
        else:
            st.pop()
            if not st:
                st.append(i)
            else:
                best = max(best, i - st[-1])
    return best

185

Burst Balloons

HardDynamic Programming

Bursting balloon i earns left * nums[i] * right, using its current neighbors. Return the max total.

Example

[3, 1, 5, 8] → 167

How to solve

Pad with 1 on both ends.
Let dp(l, r) be the best coins from balloons strictly between l and r. Memoize in a hash map, key=(l, r), val=best coins.
Pick k as the LAST balloon to burst there. Its neighbors are then l and r.
Score is v[l] * v[k] * v[r] + dp(l, k) + dp(k, r). Take the max over k.

Time O(n³) · Space O(n²), the cache

Corner cases

One balloon.
Zeros in the list.

from functools import cache

def max_coins(nums):
    v = [1] + nums + [1]
    @cache
    def dp(l, r):
        return max((v[l] * v[k] * v[r] + dp(l, k) + dp(k, r)
                    for k in range(l + 1, r)), default=0)
    return dp(0, len(v) - 1)

186

Distinct Subsequences

HardDynamic Programming

Count the subsequences of s that equal t.

Example

s = "rabbbit", t = "rabbit" → 3

How to solve

Use a DP array dp, index=j, val=ways to build t[:j]. dp[0] = 1.
For each char of s, walk j from the end of t down.
If the char equals t[j-1], add dp[j-1] to dp[j].
Walking backward stops one char from being used twice.

Time O(n · m) · Space O(m)

Corner cases

Empty t gives 1.
t longer than s gives 0.

def num_distinct(s, t):
    dp = [1] + [0] * len(t)
    for ch in s:
        for j in range(len(t), 0, -1):
            if t[j - 1] == ch:
                dp[j] += dp[j - 1]
    return dp[-1]

187

N-Queens

HardBacktracking

Place n queens on an n x n board so none attack each other. Return all boards.

Example

n = 4 → 2 boards, like [".Q..","...Q","Q...","..Q."]

How to solve

Place one queen per row, with recursion.
Use three hash sets: used columns, r - c diagonals, and r + c diagonals.
For each column, if none of the three is used, place a queen and recurse to the next row.
If all rows are filled, it means a full board. Save it.

Time O(n!) · Space O(n)

Corner cases

n = 1 gives one board.
n = 2 and n = 3 give none.

def solve_n_queens(n):
    out, cols = [], []
    def go(r, used_c, d1, d2):
        if r == n:
            out.append(["." * c + "Q" + "." * (n - c - 1) for c in cols]); return
        for c in range(n):
            if c not in used_c and r - c not in d1 and r + c not in d2:
                cols.append(c)
                go(r + 1, used_c | {c}, d1 | {r - c}, d2 | {r + c})
                cols.pop()
    go(0, set(), set(), set())
    return out

188

Sudoku Solver

HardBacktracking

Fill a 9 x 9 Sudoku board in place. There is one solution.

Example

A board with "." blanks → the solved board

How to solve

Use 27 hash sets: digits used in each row, column, and box.
List all blank cells.
For each blank in turn, try each digit not in its row, column, or box.
If the rest solves, done. Else undo the digit and try the next.

Time O(9^blanks) worst · Space O(81)

Corner cases

Board already full.
Pick the blank with the fewest options to go faster.

def solve_sudoku(b):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    blanks = []
    for r in range(9):
        for c in range(9):
            v = b[r][c]
            if v == ".":
                blanks.append((r, c))
            else:
                rows[r].add(v); cols[c].add(v); boxes[r // 3 * 3 + c // 3].add(v)
    def go(i):
        if i == len(blanks):
            return True
        r, c = blanks[i]
        k = r // 3 * 3 + c // 3
        for v in "123456789":
            if v not in rows[r] and v not in cols[c] and v not in boxes[k]:
                b[r][c] = v
                rows[r].add(v); cols[c].add(v); boxes[k].add(v)
                if go(i + 1):
                    return True
                rows[r].remove(v); cols[c].remove(v); boxes[k].remove(v)
        b[r][c] = "."
        return False
    go(0)

189

Longest Increasing Path in a Matrix

HardDFS + Memo

Return the length of the longest strictly increasing path. Moves go up, down, left, or right.

Example

[[9,9,4],[6,6,8],[2,1,1]] → 4
Path 1→2→6→9.

How to solve

DFS from each cell. Memoize in a hash map, key=(row, col), val=longest path from it.
The path from a cell is 1 + the best path from any bigger neighbor.
No visited hash set is needed, since values must rise and can never loop.
Return the max over all cells.

Time O(R · C) · Space O(R · C), the cache

Corner cases

All values equal gives 1.
One cell.

from functools import cache

def longest_increasing_path(m):
    R, C = len(m), len(m[0])
    @cache
    def dfs(r, c):
        best = 1
        for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
            if 0 <= nr < R and 0 <= nc < C and m[nr][nc] > m[r][c]:
                best = max(best, 1 + dfs(nr, nc))
        return best
    return max(dfs(r, c) for r in range(R) for c in range(C))

190

Swim in Rising Water

HardShortest Paths

At time t you can swim through cells with height at most t. Return the earliest time to go from top left to bottom right.

Example

[[0,2],[1,3]] → 3

How to solve

Use a min-heap of (highest cell on the path, row, col). The top is the lowest path so far.
Pop the cell with the lowest path max.
If it is the end, return its value.
Else push each unvisited neighbor with max(path max, its height).

Time O(n² log n) · Space O(n²)

Corner cases

1 x 1 grid gives grid[0][0].
The start cell's height counts.

import heapq

def swim_in_water(g):
    n = len(g)
    heap, seen = [(g[0][0], 0, 0)], {(0, 0)}
    while heap:
        t, r, c = heapq.heappop(heap)
        if r == c == n - 1:
            return t
        for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
                seen.add((nr, nc))
                heapq.heappush(heap, (max(t, g[nr][nc]), nr, nc))

191

Reconstruct Itinerary

HardGraphs

Use every ticket once, starting from "JFK". If there are many routes, return the one first in word order.

Example

[["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] → ["JFK","MUC","LHR","SFO","SJC"]

How to solve

Use a graph as an adjacency list: a hash map, key=airport, val=list of destinations, sorted in reverse so pop() gives the smallest.
Use a stack, starting at JFK.
While the top airport has tickets left, fly the smallest one and push it.
When an airport is stuck, add it to the route. Reverse the route at the end.

Time O(E log E), the sort · Space O(E)

Corner cases

Dead ends that must be visited last.
Repeat tickets.

from collections import defaultdict

def find_itinerary(tickets):
    adj = defaultdict(list)
    for a, b in sorted(tickets, reverse=True):
        adj[a].append(b)
    route, st = [], ["JFK"]
    while st:
        while adj[st[-1]]:
            st.append(adj[st[-1]].pop())
        route.append(st.pop())
    return route[::-1]

192

Critical Connections in a Network

HardGraphs

Return every edge whose removal splits the network. These are bridges.

Example

n = 4, [[0,1],[1,2],[2,0],[1,3]] → [[1,3]]

How to solve

DFS and give each node a visit time tin.
low[u] stores the earliest visit time reachable from u's subtree using one back edge.
After visiting child v, update low[u].
If low[v] > tin[u], it means v cannot reach above u. The edge u-v is a bridge.

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

Corner cases

Skip the edge back to the parent.
Graph with no cycles: every edge is a bridge.

def critical_connections(n, connections):
    adj = [[] for _ in range(n)]
    for a, b in connections:
        adj[a].append(b); adj[b].append(a)
    tin, low, out, timer = [-1] * n, [0] * n, [], [0]
    def dfs(u, parent):
        tin[u] = low[u] = timer[0]; timer[0] += 1
        for v in adj[u]:
            if v == parent:
                continue
            if tin[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > tin[u]:
                    out.append([u, v])
            else:
                low[u] = min(low[u], tin[v])
    dfs(0, -1)
    return out

193

First Missing Positive

HardCyclic Sort

Return the smallest positive integer not in the list, in O(n) time and O(1) space.

Example

[3, 4, -1, 1] → 2
[1, 2, 0] → 3

How to solve

Use the input array itself. Put each value v from 1 to n at index v - 1.
For each index, keep swapping its value to its home slot until it cannot move.
Scan again.
The first index i with nums[i] != i + 1 means i + 1 is missing. Else return n + 1.

Time O(n), each swap fixes a slot · Space O(1)

Corner cases

Duplicates, so swap only if the target slot differs.
All negative.
Values bigger than n.

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

194

Count of Smaller Numbers After Self

HardMerge Sort

For each value, count how many smaller values come after it.

Example

[5, 2, 6, 1] → [2, 1, 1, 0]

How to solve

Use merge sort on indexes. out[i] stores the answer for index i.
When merging, right side items placed before a left item are smaller and came after it.
So when you place a left item, add how many right items are already placed.
Recurse until the full list is sorted.

Time O(n log n) · Space O(n)

Corner cases

Equal values are not smaller.
Negatives.
One value.

def count_smaller(nums):
    out = [0] * len(nums)
    def sort(idx):
        if len(idx) <= 1:
            return idx
        mid = len(idx) // 2
        l, r = sort(idx[:mid]), sort(idx[mid:])
        merged, j = [], 0
        for i in l:
            while j < len(r) and nums[r[j]] < nums[i]:
                merged.append(r[j]); j += 1
            out[i] += j
            merged.append(i)
        return merged + r[j:]
    sort(list(range(len(nums))))
    return out

195

Basic Calculator

HardStack

Evaluate a string with +, -, brackets, and spaces.

Example

"(1+(4+5+2)-3)+(6+8)" → 23
"- (3 + 4)" → -7

How to solve

Use res for the result so far, sign for the current sign, and num for the number being read.
On + or -, add sign * num to res, then set the new sign.
On (, push (res, sign) and start fresh.
On ), finish the inner result. Pop and set res = saved res + saved sign * inner.

Time O(n) · Space O(n), the stack

Corner cases

Unary minus.
Multi digit numbers.
Spaces anywhere.

def calculate(s):
    res, num, sign, st = 0, 0, 1, []
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)
        elif ch in "+-":
            res += sign * num
            num, sign = 0, 1 if ch == "+" else -1
        elif ch == "(":
            st.append((res, sign)); res, sign = 0, 1
        elif ch == ")":
            res += sign * num
            prev, s0 = st.pop()
            res, num = prev + s0 * res, 0
    return res + sign * num

196

Candy

HardGreedy

Kids stand in a line with ratings. Each kid gets at least one candy. A kid with a higher rating than a neighbor gets more. Return the fewest candies.

Example

[1, 0, 2] → 5
Candies 2, 1, 2.

How to solve

Use an array c, index=kid, val=candies, starting at 1 each.
Left to right: if a kid beats the left kid, give left + 1.
Right to left: if a kid beats the right kid, give at least right + 1.
Sum the list.

Time O(n) · Space O(n)

Corner cases

Equal ratings need no extra.
Ratings only fall.

def candy(r):
    n = len(r)
    c = [1] * n
    for i in range(1, n):
        if r[i] > r[i - 1]:
            c[i] = c[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if r[i] > r[i + 1]:
            c[i] = max(c[i], c[i + 1] + 1)
    return sum(c)

197

Split Array Largest Sum

HardBinary Search

Split the list into k non-empty blocks. Make the largest block sum as small as possible.

Example

[7, 2, 5, 10, 8], k = 2 → 18
Blocks [7,2,5] and [10,8].

How to solve

Binary search the answer between max(nums) and sum(nums).
For a limit, count how many blocks you need if no block may pass it.
If blocks <= k, it means the limit works. Try smaller.
Else try bigger.

Time O(n log sum) · Space O(1)

Corner cases

k = 1 gives the total.
k equals the length gives the max.

def split_array(nums, k):
    def blocks(limit):
        count, cur = 1, 0
        for x in nums:
            if cur + x > limit:
                count, cur = count + 1, 0
            cur += x
        return count
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if blocks(mid) <= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

198

Russian Doll Envelopes

HardDynamic Programming

An envelope fits in another if both its width and height are smaller. Return the most envelopes you can nest.

Example

[[5,4],[6,4],[6,7],[2,3]] → 3

How to solve

Sort by width up, and by height down for equal widths.
Now find the longest rising run of heights, using the LIS tails trick.
Height down for equal widths stops two same-width envelopes from both being picked.

Time O(n log n) · Space O(n)

Corner cases

Equal widths cannot nest.
Duplicate envelopes.

from bisect import bisect_left

def max_envelopes(env):
    env.sort(key=lambda e: (e[0], -e[1]))
    tails = []
    for _, h in env:
        i = bisect_left(tails, h)
        if i == len(tails):
            tails.append(h)
        else:
            tails[i] = h
    return len(tails)

199

LFU Cache

HardDesign

Build a cache with O(1) get and put. When full, drop the least used key. Break ties by least recent use.

Example

cap 2: put(1,1), put(2,2), get(1), put(3,3) drops key 2

How to solve

Use a hash map, key=key, val=(value, freq). Use a second hash map, key=freq, val=ordered hash map (OrderedDict) of keys, oldest first.
Track min_freq, the lowest freq in use.
On use, move the key from freq f to f + 1. If f was min_freq and is now empty, raise min_freq.
When full, evict the oldest key in min_freq. A new key sets min_freq = 1.

Time O(1) per call · Space O(capacity)

Corner cases

Capacity 0.
Put on an existing key counts as a use.
Reset min_freq to 1 on a new key.

from collections import OrderedDict, defaultdict

class LFUCache:
    def __init__(self, cap):
        self.cap, self.min_f = cap, 0
        self.kv, self.groups = {}, defaultdict(OrderedDict)

    def _touch(self, key):
        val, f = self.kv[key]
        del self.groups[f][key]
        if not self.groups[f] and self.min_f == f:
            self.min_f += 1
        self.kv[key] = (val, f + 1)
        self.groups[f + 1][key] = None

    def get(self, key):
        if key not in self.kv:
            return -1
        self._touch(key)
        return self.kv[key][0]

    def put(self, key, val):
        if self.cap == 0:
            return
        if key in self.kv:
            self._touch(key)
            self.kv[key] = (val, self.kv[key][1])
            return
        if len(self.kv) == self.cap:
            old, _ = self.groups[self.min_f].popitem(last=False)
            del self.kv[old]
        self.kv[key] = (val, 1)
        self.groups[1][key] = None
        self.min_f = 1

200

Text Justification

HardStrings

Pack words into lines of exactly width chars. Spread spaces evenly, with extra spaces on the left. The last line is left aligned.

Example

["This","is","an","example"], width = 16 → ["This is an", "example "]

How to solve

Use line to store the words on the current line, and size for their letters.
If the next word does not fit, it means the line is done. Spread the spare spaces.
Use divmod to split spaces across gaps. Give the extras to the leftmost gaps.
The last line, and one-word lines, pad on the right.

Time O(total chars) · Space O(width)

Corner cases

One word on a line.
The last line.
A word exactly width long.

def full_justify(words, width):
    out, line, size = [], [], 0
    for w in words:
        if size + len(w) + len(line) > width:
            gaps = len(line) - 1 or 1
            q, r = divmod(width - size, gaps)
            for i in range(gaps):
                line[i] += " " * (q + (i < r))
            out.append("".join(line).ljust(width))
            line, size = [], 0
        line.append(w)
        size += len(w)
    out.append(" ".join(line).ljust(width))
    return out

Contents

Data Structures · 26 implementations

Easy · 64 questions

Medium · 102 questions