Data Structures & Algorithms

How to approach a coding interview

A coding round grades four things: problem solving (did you find a good algorithm), coding (is it correct and readable), communication (could the interviewer follow your thinking) and verification (did you test it yourself). A strong candidate with a clear process beats a fast candidate who codes silently and ships a bug.

The seven-step framework

1. Clarify (2-3 min) Restate the problem. Ask about input size, value ranges, negatives, duplicates, empty input, sorted or not, and what to return when there is no answer. Write one small example and its expected output.
2. Brute force (1-2 min) Say the simplest correct idea and its complexity, even if it is O(n^2) or O(2^n). This proves you understand the problem and gives a baseline.
3. Optimise (5-10 min) Look for the bottleneck. Ask: can a hash map remove the inner loop? Is the input sorted (two pointers, binary search)? Is it a contiguous range (sliding window, prefix sums)? Are there repeated subproblems (DP)? Is it "shortest steps" (BFS)?
4. Agree before coding State the algorithm in two or three sentences plus its time and space. Get a nod from the interviewer.
5. Code (15-20 min) Use clear names, small helper functions, and narrate what each block does. Do not over-optimise micro details.
6. Test Trace your own example line by line, then the edge cases: empty, single element, all equal, negatives, maximum size, cycles or disconnected graphs.
7. Discuss Restate final complexity, mention alternatives and follow-ups (streaming input, memory limits, concurrency).

Constraints tell you the target complexity

The rule of thumb is that a typical judge runs roughly 10^8 simple operations per second, so pick the complexity that keeps you below that.

Pattern picker: trigger words to technique

Big-O and complexity analysis

Big-O describes how the running time (or memory) of an algorithm grows as the input size n grows, ignoring constant factors and lower-order terms. O(2n + 5) is O(n), and O(n^2 + n) is O(n^2). It lets you compare algorithms independently of hardware or language.

The complexity ladder (best to worst)

How to calculate it

• Sequential steps add: O(n) followed by O(n log n) is O(n log n) (keep the dominant term).
• Nested loops multiply: a loop of n inside a loop of m is O(n x m).
• Halving loops are logarithmic: while n > 1: n //= 2 runs log2(n) times.
• Recursion: cost = (number of calls) x (work per call). A tree with branching factor b and depth d has about b^d calls. Fibonacci without memoisation is O(2^n); with memoisation it is O(n).
• Divide and conquer (Master theorem): T(n) = aT(n/b) + O(n^d). Merge sort (a=2, b=2, d=1) is O(n log n); binary search (a=1, b=2, d=0) is O(log n).
• Multiple inputs: use separate variables. Graph traversal is O(V + E), not O(n). Comparing two strings of length m and n is O(m x n).

Big-O, Big-Omega, Big-Theta

Best, average, worst and amortized

• Worst case is the guarantee. Quicksort is O(n^2) worst case (bad pivots on sorted input).
• Average case assumes typical random input. Quicksort averages O(n log n); hash map lookups average O(1) but degrade to O(n) when every key collides.
• Amortized is the average cost per operation over a long sequence. Appending to a dynamic array is O(1) amortized: occasionally the array doubles (O(n) copy), but because capacity doubles, total copying over n appends is at most about 2n, so each append costs O(1) on average.

Dynamic array doubling: cost of n appends
capacity: 1 -> 2 -> 4 -> 8 -> 16 ...
copies:   1 +  2 +  4 +  8 + ... + n/2  <  n
total work = n writes + < n copies = O(n)  =>  O(1) amortized per append

Space complexity

Space complexity counts extra memory beyond the input (sometimes called auxiliary space). Remember the hidden costs:

• Recursion stack: DFS on a tree of height h uses O(h) stack; on a skewed tree that is O(n). Python's default recursion limit is about 1000, so deep recursion may need sys.setrecursionlimit or an explicit stack.
• Copies and slices: s[1:] in Python copies, which can silently turn an O(n) algorithm into O(n^2).
• Output space is usually not counted, but say so explicitly (for example, "O(1) extra space apart from the result").

Arrays, strings and hashing

An array stores elements in one contiguous block of memory, so element i is at base + i x size: O(1) random access and excellent CPU cache behaviour. The price is that inserting or deleting in the middle shifts everything after it (O(n)). A dynamic array (Python list, Java ArrayList, C++ vector) grows by doubling, giving O(1) amortized append.

Operation cheat sheet for every structure on this page

* amortized. L = key length. V and E = number of vertices and edges. "~O(1)" for Union-Find means O(alpha(n)), the inverse Ackermann function, which is at most 4 for any realistic n. † Java 8+ HashMap treeifies a long chain into a red-black tree once the table is large enough, so that bucket is O(log n) instead of O(n).

Strings

• Strings are arrays of characters. In Python and Java they are immutable: every modification creates a new string.
• For a fixed alphabet (for example 26 lowercase letters), a count array of size 26 is faster and smaller than a hash map, and counts as O(1) space.
• Anagram check: compare character counts (O(n)) rather than sorting (O(n log n)).
• Common string patterns: sliding window (longest substring), two pointers (palindrome), hashing (group anagrams), trie (prefixes), DP (edit distance, LCS).

Hash maps and hash sets

A hash map stores key-value pairs. A hash function turns the key into an integer, which is reduced to a bucket index (for example hash(key) % capacity). Lookup, insert and delete are O(1) on average.

key "cat" --hash()--> 9812734 --% 8--> bucket 6

bucket: 0    1    2    3    4    5    6               7
        -    -   [dog] -    -    -   [cat]->[owl]     -
                                      ^ collision handled by chaining

• Chaining: each bucket holds a list of entries. Java 8+ HashMap treeifies a bin into a red-black tree only when both are true: the bin has at least TREEIFY_THRESHOLD (8) entries and the table capacity is at least MIN_TREEIFY_CAPACITY (64). If the chain is long but the table is still smaller than 64, the map resizes instead of treeifying (a small table with one long chain is almost always a bad hash, and growing the table usually spreads the keys). After treeify, that bucket is O(log n). A tree bin untreeifies back to a list when it shrinks below UNTREEIFY_THRESHOLD (6).
• Open addressing: on collision, probe for another free slot (linear probing, quadratic probing, double hashing). Python's dict uses open addressing. Deletion needs "tombstone" markers.
• Load factor = entries / buckets. When it passes a threshold (0.75 in Java), the table doubles and every key is rehashed. That occasional O(n) step is why inserts are O(1) amortized.
• Keys must be immutable (or at least their hash must not change). Python lists cannot be dict keys; use tuples. In Java, if you override equals() you must override hashCode().
• Worst case is O(n) if an attacker crafts colliding keys (hash-flooding). Randomised hash seeds defend against this.

# Python hash map idioms
from collections import Counter, defaultdict

freq = Counter(words)                  # word -> count, O(n)
top3 = freq.most_common(3)

groups = defaultdict(list)             # group anagrams
for w in words:
    groups["".join(sorted(w))].append(w)

seen = set()                           # dedupe / membership in O(1)
for x in nums:
    if x in seen:
        print("duplicate", x)
    seen.add(x)

The source material also shows the Java equivalent for counting, which is worth recognising:

Map<String, Integer> freq = new HashMap<>();
for (String w : words)
    freq.merge(w, 1, Integer::sum);   // O(1) average per word

Hash map template: Two Sum in one pass

def two_sum(nums, target):
    index_of = {}                       # value -> index seen so far
    for i, x in enumerate(nums):
        if target - x in index_of:
            return [index_of[target - x], i]
        index_of[x] = i
    return []
# O(n) time, O(n) space; brute force is O(n^2)

Linked lists

A linked list is a chain of nodes where each node holds a value and a pointer to the next node (singly linked) or to both neighbours (doubly linked). Inserting after a node you already hold is O(1). Deleting is O(1) on a doubly linked list (you have the previous pointer) or on a singly linked list if you already hold the previous node; given only the node itself on a singly linked list you must walk from the head (or use the "copy the next node and skip it" trick, which cannot delete the tail). Reaching the i-th node is O(n), and nodes are scattered in memory, so scans are slower than arrays in practice.

Singly:  head -> [3|*] -> [7|*] -> [9|*] -> None
Doubly:  None <- [3] <-> [7] <-> [9] -> None
Dummy head trick: dummy -> head ...  (removes "is this the first node?" special cases)

Core techniques

• Dummy (sentinel) node: start with dummy = ListNode(0, head) so that deleting or inserting at the head needs no special case; return dummy.next.
• Reversal: the three-pointer dance (prev, curr, nxt).
• Fast and slow pointers: find the middle, detect a cycle, find the k-th node from the end (move fast k steps first).
• Merge: walk two sorted lists with a tail pointer.
• Hash map + doubly linked list: the classic O(1) LRU cache.

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

def reverse(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next       # save the rest
        curr.next = prev      # flip the pointer
        prev, curr = curr, nxt
    return prev               # O(n) time, O(1) space

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    return slow               # second middle for even length

def has_cycle(head):          # Floyd's tortoise and hare
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

Why Floyd's algorithm finds the cycle start

Let a be the distance from head to the cycle entry, c the cycle length, and suppose they meet b steps into the cycle. The slow pointer walked a + b; the fast pointer walked twice that, 2(a + b), which is also a + b + k*c for some whole number of extra laps k. So a + b = k*c, meaning a = k*c - b. Therefore a pointer starting at the head and a pointer starting at the meeting point, both moving one step at a time, meet exactly at the entry.

Stacks, queues and deques

A stack is last-in-first-out (LIFO): push and pop at the same end. A queue is first-in-first-out (FIFO): add at the back, remove from the front. A deque (double-ended queue) supports O(1) add and remove at both ends and can act as either.

Template: valid parentheses

def is_valid(s):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack          # O(n) time, O(n) space

Queue built from two stacks (amortized O(1))

class MyQueue:
    def __init__(self):
        self.inbox, self.outbox = [], []
    def push(self, x):
        self.inbox.append(x)
    def pop(self):
        self.peek()
        return self.outbox.pop()
    def peek(self):
        if not self.outbox:              # move only when outbox is empty
            while self.inbox:
                self.outbox.append(self.inbox.pop())
        return self.outbox[-1]
# each element is moved at most once => O(1) amortized per operation

Min stack: O(1) getMin

Store pairs (value, min_so_far) on the stack. The minimum is always the top pair's second field, and popping restores the previous minimum automatically.

Heaps and priority queues

A binary heap is a complete binary tree stored in an array where every parent is smaller than its children (min-heap) or larger (max-heap). The root is always the minimum (or maximum). Peek is O(1); push and pop are O(log n) because an element "bubbles" up or down at most the height of the tree. Building a heap from n items with heapify is O(n), not O(n log n).

Min-heap as tree            as array (index i: children 2i+1, 2i+2; parent (i-1)//2)
          1
        /   \               [1, 3, 2, 7, 4, 5]
       3     2               0  1  2  3  4  5
      / \   /
     7   4 5

Python heapq recipes

import heapq

h = []
heapq.heappush(h, 5)             # min-heap by default
smallest = heapq.heappop(h)
heapq.heapify(nums)              # O(n) in place

# max-heap: push negated values
heapq.heappush(h, -x); largest = -heapq.heappop(h)

# tuples sort by first field: (priority, tie_breaker, item)
heapq.heappush(h, (dist, node))

def kth_largest(nums, k):        # keep a min-heap of size k
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)     # drop the smallest
    return h[0]                  # O(n log k) time, O(k) space

Heap patterns

• Top-k: keep a heap of size k of the opposite type (min-heap for k largest). O(n log k).
• K-way merge: put the head of each of k sorted lists in a min-heap; pop the smallest and push its successor. O(N log k).
• Two heaps (running median): a max-heap for the lower half and a min-heap for the upper half, kept balanced in size; the median is at one or both tops. O(log n) add, O(1) median.
• Scheduling: meeting rooms (min-heap of end times), task scheduler, CPU job queues.
• Graph algorithms: Dijkstra and Prim use a min-heap of (distance, node).

Trees, binary search trees and tries

A tree is a connected graph with no cycles: one root, and every other node has exactly one parent. A binary tree allows at most two children. The height h decides the cost of most operations: a balanced tree has h = O(log n); a degenerate (skewed) tree has h = O(n).

Traversals

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def max_depth(root):                       # post-order recursion
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

from collections import deque
def level_order(root):                     # BFS by level
    if not root:
        return []
    out, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):            # freeze the level size
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out

def inorder_iterative(root):               # explicit stack, no recursion
    out, stack, node = [], [], root
    while stack or node:
        while node:
            stack.append(node); node = node.left
        node = stack.pop()
        out.append(node.val)
        node = node.right
    return out

Binary search trees

In a BST, every value in the left subtree is smaller than the node and every value in the right subtree is larger. Search, insert and delete walk one path: O(h). Self-balancing variants (AVL, red-black) keep h = O(log n); Java's TreeMap and C++ std::map are red-black trees. Python has no built-in balanced BST; use bisect on a sorted list for small data or the third-party sortedcontainers.SortedList.

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

def lowest_common_ancestor(root, p, q):    # general binary tree
    if not root or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    return root if left and right else left or right

Tries (prefix trees)

A trie stores strings character by character: each edge is a character, and a path from the root spells a prefix. Insert and search cost O(L) where L is the word length, independent of how many words are stored, and "all words starting with a prefix" is natural.

Words: cat, car, dog
        (root)
        /    \
       c      d
       |      |
       a      o
      / \     |
     t*  r*   g*      (* = end of word)

class Trie:
    def __init__(self):
        self.root = {}
    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node['$'] = True                     # end-of-word marker
    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node:
                return None
            node = node[ch]
        return node
    def search(self, word):
        node = self._walk(word)
        return node is not None and '$' in node
    def starts_with(self, prefix):
        return self._walk(prefix) is not None

The array-of-26-children version (Node[] kids = new Node[26] in Java) is faster for lowercase-only input but wastes memory for sparse alphabets. Uses: autocomplete, spell check, word search on a grid, IP longest-prefix routing, XOR maximisation with a bitwise trie.

Other trees worth naming

Graphs: BFS, DFS, topological sort, Dijkstra and Union-Find

A graph is a set of vertices (V) connected by edges (E). Edges can be directed or undirected, weighted or unweighted. Trees, grids, social networks, dependency lists and road maps are all graphs. Store them as an adjacency list (a map from node to neighbours, O(V + E) space, best for sparse graphs) or an adjacency matrix (V x V, O(1) edge check, best for dense graphs).

from collections import defaultdict, deque

def build_graph(n, edges, directed=False):
    g = defaultdict(list)
    for u, v in edges:
        g[u].append(v)
        if not directed:
            g[v].append(u)
    return g

BFS: shortest path in an unweighted graph

def bfs_shortest(g, src):
    dist = {src: 0}
    q = deque([src])
    while q:
        u = q.popleft()
        for v in g[u]:
            if v not in dist:          # mark when enqueued, not when popped
                dist[v] = dist[u] + 1
                q.append(v)
    return dist                        # O(V + E) time and space

DFS: components, paths, cycles

def count_components(n, g):
    seen = set()
    def dfs(u):
        seen.add(u)
        for v in g[u]:
            if v not in seen:
                dfs(v)
    count = 0
    for u in range(n):
        if u not in seen:
            dfs(u); count += 1
    return count

# Grid DFS: number of islands
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)
    islands = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == '1':
                sink(r, c); islands += 1
    return islands                     # O(R x C)

Cycle detection

• Undirected: DFS and a neighbour is visited but is not your parent, or Union-Find reports two endpoints already in the same set.
• Directed: three colours (white = unvisited, grey = on the current path, black = done). An edge to a grey node is a back edge, meaning a cycle. Alternatively, Kahn's algorithm fails to output all nodes.

Topological sort (Kahn's algorithm)

Orders the nodes of a directed acyclic graph (DAG) so every edge goes from earlier to later: build order, course prerequisites, task scheduling.

def topo_sort(n, edges):               # edge (a, b) means a before b
    g = defaultdict(list); indeg = [0] * n
    for a, b in edges:
        g[a].append(b); indeg[b] += 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 g[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else []   # [] means a cycle exists

Dijkstra: shortest path with non-negative weights

import heapq
def dijkstra(g, src):                  # g[u] = [(v, w), ...]
    dist = {src: 0}
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')):
            continue                   # stale entry, skip
        for v, w in g[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist                        # O((V + E) log V)

Union-Find (disjoint set union)

Tracks which elements belong to the same group. With path compression (point nodes straight at the root while finding) and union by rank or size (attach the smaller tree under the larger), both operations are amortized O(alpha(n)), effectively constant.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n)); self.size = [1] * n
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # already connected: adding edge makes a cycle
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra; self.size[ra] += self.size[rb]
        return True

Core patterns I: pointers, windows, binary search and ranges

Most array and string problems are solved by one of a handful of scanning patterns. Each one turns a quadratic brute force into linear or logarithmic time by never re-examining work that has already been done.

1. Two pointers

Use when: sorted array, pairs or triplets with a target, palindromes, in-place partitioning or removing duplicates. Pointers either move toward each other (opposite ends) or in the same direction (read and write pointers).

def pair_with_sum(a, target):          # a is sorted
    l, r = 0, len(a) - 1
    while l < r:
        s = a[l] + a[r]
        if s == target: return (l, r)
        if s < target: l += 1
        else: r -= 1
    return None                          # O(n) time, O(1) space

def remove_duplicates(a):              # sorted, in place; returns new length
    w = 0
    for r in range(len(a)):
        if r == 0 or a[r] != a[r - 1]:
            a[w] = a[r]; w += 1
    return w

Classics: 3Sum (sort, fix one element, two-pointer the rest, skip duplicates; O(n^2)), container with most water (move the shorter wall inward), trapping rain water, sort colours (Dutch national flag, three pointers).

2. Sliding window

Use when: the answer is a contiguous subarray or substring and the validity of the window changes predictably as it grows or shrinks. Each element enters and leaves the window at most once, so the total is O(n).

def longest_unique_substring(s):     # variable-size window
    last = {}                          # char -> last index
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1        # jump past the repeat
        last[ch] = right
        best = max(best, right - left + 1)
    return best

def max_sum_k(a, k):                   # fixed-size window
    cur = best = sum(a[:k])
    for i in range(k, len(a)):
        cur += a[i] - a[i - k]
        best = max(best, cur)
    return best

Generic shape: expand right; while the window is invalid, shrink left; record the answer. Classics: minimum window substring (need/have counts), longest repeating character replacement (window length minus max frequency must be at most k), permutation in string, sliding window maximum (monotonic deque).

3. Fast and slow pointers

Use when: cycle detection (linked list, or a function like "happy number" or "find the duplicate number" where values point to indices), middle of a list, k-th from the end. See the linked-list section for templates.

4. Binary search (on an index and on the answer)

Use when: data is sorted, or you can ask a yes/no question ok(x) that is monotonic (false, false, ..., true, true). Each step halves the range: O(log n).

def lower_bound(a, target):          # first index with a[i] >= target
    lo, hi = 0, len(a)                 # search space [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target: lo = mid + 1
        else: hi = mid
    return lo                          # same as bisect.bisect_left

# Binary search on the answer: minimum ship capacity to deliver in D days
def ship_within_days(weights, D):
    def ok(cap):
        days, load = 1, 0
        for w in weights:
            if load + w > cap:
                days += 1; load = 0
            load += w
        return days <= D
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid): hi = mid           # feasible: try smaller
        else: lo = mid + 1
    return lo                          # O(n log(sum))

Classics: search in rotated sorted array (one half is always sorted; decide which), find minimum in rotated array, first and last position, Koko eating bananas, split array largest sum, median of two sorted arrays (binary search the partition of the smaller array, O(log min(m, n))).

5. Prefix sums

Use when: many range-sum queries, or "count subarrays whose sum equals k". prefix[i] is the sum of the first i elements, so the sum of a[l..r] is prefix[r+1] - prefix[l] in O(1).

def subarray_sum_equals_k(nums, k):
    count, running = 0, 0
    seen = {0: 1}                      # prefix sum -> how many times
    for x in nums:
        running += x
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count                       # O(n), works with negatives

Variations: 2-D prefix sums for rectangle queries, product of array except self (prefix and suffix products), difference arrays for many range updates, prefix XOR.

6. Monotonic stack

Use when: "next greater element", "previous smaller element", daily temperatures, largest rectangle in a histogram, stock span. Keep the stack sorted; pop every element that the new element makes irrelevant. Each element is pushed and popped once: O(n).

def next_greater(nums):
    res = [-1] * len(nums)
    stack = []                         # indices with decreasing values
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x       # x is the next greater for that index
        stack.append(i)
    return res

def largest_rectangle(heights):
    stack, best = [], 0                # increasing heights (indices)
    for i, h in enumerate(heights + [0]):   # sentinel flushes the stack
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            best = max(best, height * width)
        stack.append(i)
    return best

The monotonic deque variant solves sliding window maximum in O(n): keep indices with decreasing values; drop the front when it leaves the window.

7. Intervals

Use when: meetings, bookings, ranges. Almost always start by sorting by start time (or by end time for greedy selection).

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = []
    for s, e in intervals:
        if merged and s <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], e)
        else:
            merged.append([s, e])
    return merged                      # O(n log n)

import heapq
def min_meeting_rooms(intervals):
    intervals.sort()
    ends = []                          # min-heap of end times in use
    for s, e in intervals:
        if ends and ends[0] <= s:
            heapq.heappop(ends)        # reuse the room that freed earliest
        heapq.heappush(ends, e)
    return len(ends)

Related: insert interval, non-overlapping intervals (greedy by earliest end; answer = n minus the maximum compatible set), interval list intersections (two pointers), sweep line with +1/-1 events.

Core patterns II: backtracking, greedy, heap top-k and bits

These patterns deal with choices: exploring all of them (backtracking), committing to the locally best one (greedy), keeping only the best k (heap), or packing many yes/no choices into the bits of one integer (bit manipulation).

8. Backtracking (DFS over choices)

Use when: generate all subsets, permutations or combinations; constraint puzzles (N-Queens, Sudoku); word search on a grid. The template is choose, explore, un-choose. Prune early when a partial choice cannot lead to a valid answer.

def subsets(nums):
    res, path = [], []
    def bt(start):
        res.append(path[:])            # record a copy
        for i in range(start, len(nums)):
            path.append(nums[i])       # choose
            bt(i + 1)                  # explore
            path.pop()                 # un-choose
    bt(0)
    return res                         # O(n x 2^n)

def permutations(nums):
    res, path, used = [], [], [False] * len(nums)
    def bt():
        if len(path) == len(nums):
            res.append(path[:]); return
        for i, x in enumerate(nums):
            if used[i]: continue
            used[i] = True; path.append(x)
            bt()
            path.pop(); used[i] = False
    bt()
    return res                         # O(n x n!)

def combination_sum(cands, target):    # reuse allowed
    res, path = [], []
    cands.sort()
    def bt(start, remain):
        if remain == 0:
            res.append(path[:]); return
        for i in range(start, len(cands)):
            if cands[i] > remain: break   # prune: sorted, rest are bigger
            path.append(cands[i])
            bt(i, remain - cands[i])
            path.pop()
    bt(0, target)
    return res

Duplicates: sort first and skip nums[i] == nums[i-1] when i > start. N-Queens: track used columns and both diagonals (r - c and r + c) in sets.

9. Greedy

Use when: a locally optimal choice can be proved to lead to a global optimum, usually with an exchange argument ("any optimal solution can be changed to include my greedy choice without getting worse").

• Interval scheduling: pick the meeting that ends earliest, repeat. Maximises the number of non-overlapping meetings.
• Jump game: track the furthest reachable index.
• Gas station: if the total gas is at least the total cost, start after the point where the running tank last went negative.
• Huffman coding: repeatedly merge the two least frequent symbols.
• Kadane's maximum subarray: extend the current run or restart at this element (greedy and DP at once).

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

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

10. Heap top-k

Use when: "k largest", "k most frequent", "k closest points", "k-th smallest in a sorted matrix". Keep a heap of size k; the total is O(n log k), which beats sorting when k is much smaller than n and works on a stream.

import heapq
from collections import Counter
def top_k_frequent(nums, k):
    counts = Counter(nums)
    return heapq.nlargest(k, counts.keys(), key=counts.get)   # O(n log k)

def top_k_frequent_bucket(nums, k):    # O(n) bucket sort alternative
    counts = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for x, c in counts.items():
        buckets[c].append(x)
    out = []
    for c in range(len(buckets) - 1, 0, -1):
        for x in buckets[c]:
            out.append(x)
            if len(out) == k:
                return out
    return out

11. Bit manipulation

def single_number(nums):
    res = 0
    for x in nums:
        res ^= x
    return res

def missing_number(nums):              # 0..n with one missing
    res = len(nums)
    for i, x in enumerate(nums):
        res ^= i ^ x
    return res

Sorting algorithms

Sorting is rarely asked to be implemented from scratch, but you must know the trade-offs, and "sort first" is the opening move for many problems (intervals, two pointers, grouping, greedy). Any sort that only compares elements needs at least Omega(n log n) comparisons in the worst case; non-comparison sorts (counting, radix, bucket) beat this by exploiting the structure of keys.

Comparison table

What the libraries use

• Python list.sort() and sorted(): TimSort, stable, O(n log n) worst case, O(n) on already-sorted data.
• Java Arrays.sort: dual-pivot quicksort for primitive arrays (not stable, which is fine because equal primitives are indistinguishable) and TimSort for object arrays (stable).
• C++ std::sort: introsort (quicksort that switches to heapsort if recursion gets too deep, plus insertion sort for tiny ranges). std::stable_sort is merge-based.

Stability, and why it matters

A stable sort keeps equal elements in their original relative order. This matters when you sort by multiple keys in passes: sort by first name, then stable-sort by last name, and people with the same last name stay ordered by first name. Radix sort depends on this property for each digit pass.

Templates: merge sort and quicksort

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:           # <= keeps it stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out

import random
def quicksort(a, lo=0, hi=None):
    if hi is None: hi = len(a) - 1
    if lo >= hi: return
    p = random.randint(lo, hi)            # random pivot
    a[p], a[hi] = a[hi], a[p]
    pivot, i = a[hi], lo
    for j in range(lo, hi):               # Lomuto partition
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]; i += 1
    a[i], a[hi] = a[hi], a[i]
    quicksort(a, lo, i - 1); quicksort(a, i + 1, hi)

def quickselect(a, k):                    # k-th smallest, 0-based, O(n) average
    pivot = random.choice(a)
    lows  = [x for x in a if x < pivot]
    highs = [x for x in a if x > pivot]
    pivots = len(a) - len(lows) - len(highs)
    if k < len(lows): return quickselect(lows, k)
    if k < len(lows) + pivots: return pivot
    return quickselect(highs, k - len(lows) - pivots)

How the elementary sorts move data

Input: [5, 2, 4, 1]
Insertion: [5 | 2 4 1] -> [2 5 | 4 1] -> [2 4 5 | 1] -> [1 2 4 5]   (grow a sorted prefix)
Selection: pick min 1 -> [1 | 2 4 5] ... (swap the minimum of the rest to the front)
Bubble:    adjacent swaps push the largest to the end each pass
Merge:     [5 2][4 1] -> [5][2][4][1] -> [2 5][1 4] -> [1 2 4 5]
Quick:     pivot 4 -> [2 1] 4 [5] -> recurse on each side

Dynamic programming

Dynamic programming (DP) is recursion plus memory. It applies when a problem has optimal substructure (the best answer is built from best answers to smaller subproblems) and overlapping subproblems (the same smaller subproblems come up again and again). If the subproblems do not overlap, it is plain divide and conquer (like merge sort), not DP.

The framework: state, transition, base case

1. State Decide what dp[i] (or dp[i][j]) means in words, for example "the minimum coins to make amount i" or "the length of the LCS of the first i characters of A and first j of B". The state must capture everything needed to make the remaining decisions.
2. Transition (recurrence) Express a state in terms of smaller states by considering the last choice: "take item i or skip it", "the last step was 1 or 2 stairs".
3. Base cases The smallest states you know directly: dp[0] = 0, empty string, zero capacity.
4. Order Fill so that every state's dependencies are computed first (bottom-up), or recurse with a cache (top-down).
5. Answer Say which state holds the final result (dp[n], dp[m][n], or the max over all states).
6. Optimise space If each row only depends on the previous one, keep one or two rows.

Top-down vs bottom-up

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):                       # top-down: O(n) time, O(n) stack
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)

def fib(n):                            # bottom-up, O(1) space
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

DP families to recognise

1-D: house robber and climbing stairs

def rob(nums):                         # cannot rob adjacent houses
    take, skip = 0, 0                  # best if we rob / don't rob house i
    for x in nums:
        take, skip = skip + x, max(take, skip)
    return max(take, skip)
# dp[i] = max(dp[i-1], dp[i-2] + nums[i])

def climb_stairs(n):                   # 1 or 2 steps at a time
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

Coin change (unbounded knapsack)

def coin_change(coins, amount):        # minimum number of coins
    INF = float('inf')
    dp = [0] + [INF] * amount          # dp[a] = min coins for amount a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1   # O(amount x coins)

def coin_ways(coins, amount):          # number of combinations
    dp = [1] + [0] * amount
    for c in coins:                    # coins outer => combinations, not permutations
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

0/1 knapsack

def knapsack(weights, values, W):
    dp = [0] * (W + 1)                 # dp[w] = best value with capacity w
    for wt, val in zip(weights, values):
        for w in range(W, wt - 1, -1): # go DOWN so each item is used once
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]                       # O(n x W) time, O(W) space

def can_partition(nums):               # equal subset sum
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    dp = [True] + [False] * target
    for x in nums:
        for s in range(target, x - 1, -1):
            dp[s] = dp[s] or dp[s - x]
    return dp[target]

Note that O(n x W) is pseudo-polynomial: it is polynomial in the numeric value W, not in the number of bits needed to write W. Knapsack is NP-hard in general.

Longest increasing subsequence

def lis_quadratic(nums):               # dp[i] = LIS ending at i, O(n^2)
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

import bisect
def lis(nums):                         # patience sorting, O(n log n)
    tails = []                         # tails[k] = smallest tail of an IS of length k+1
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails): tails.append(x)
        else: tails[i] = x
    return len(tails)

Longest common subsequence and edit distance

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

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

Edit distance "horse" -> "ros"
        ""  r  o  s
    ""   0  1  2  3
    h    1  1  2  3
    o    2  2  1  2
    r    3  2  2  2
    s    4  3  3  2
    e    5  4  4  3   <- answer 3 (replace h->r, delete r, delete e)

2-D grid: unique paths

def unique_paths(m, n):                # only right or down moves
    row = [1] * n
    for _ in range(1, m):
        for c in range(1, n):
            row[c] += row[c - 1]       # from above (old row[c]) + from left
    return row[-1]                     # O(m x n) time, O(n) space

Word break

def word_break(s, words):
    words = set(words)
    dp = [True] + [False] * len(s)     # dp[i]: s[:i] can be segmented
    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True; break
    return dp[len(s)]                  # O(n^2) checks (x substring cost)

Range queries: prefix sums, Fenwick trees and segment trees

Prefix sums answer static range sums in O(1) after O(n) setup, but a later point update forces you to rebuild. When the interview mixes point updates with range queries (or range updates with point queries), reach for a Fenwick tree or a segment tree: both are O(log n) per operation.

When to pick which

class Fenwick:
    def __init__(self, n):
        self.t = [0] * (n + 1)          # 1-indexed
    def add(self, i, delta):            # point update
        i += 1
        while i < len(self.t):
            self.t[i] += delta
            i += i & -i                 # next responsible index
    def prefix(self, i):                # sum of [0 .. i]
        i += 1; 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) if l else 0)

i & -i isolates the lowest set bit, which is the size of the block this index is responsible for. A segment tree stores 4n nodes (safe upper bound) and can be extended with lazy propagation for range updates. Both are O(n) memory.

Quick revision

• Big-O ignores constants and keeps the dominant term; always state both time and space, and name every input variable.
• Amortized O(1): dynamic-array append and hash-map insert are occasionally O(n) but average O(1) because capacity doubles.
• Rough budget: about 10^8 simple operations per second; n = 10^5 to 10^6 means O(n) or O(n log n).
• Recursion depth counts as space: O(h) for trees, O(n) for skewed trees and deep DFS.
• Hash maps give O(1) average lookup via hashing and buckets; worst case O(n) when keys collide. Java 8+ HashMap treeifies a bin only if it has 8+ entries and the table capacity is at least 64 (otherwise it resizes); a treeified bin is O(log n).
• Replacing an inner search loop with a hash-map lookup is the most common optimisation.
• Linked lists: use a dummy head, save next before rewiring, check fast and fast.next.
• Floyd's cycle detection: after the pointers meet, reset one to head and step both by one to reach the entry.
• Use collections.deque for queues in Python; list.pop(0) is O(n).
• Heaps: O(1) peek, O(log n) push and pop, O(n) heapify; a size-k min-heap keeps the k largest.
• Two heaps (max-heap low half, min-heap high half) give a running median.
• A BST in-order traversal is sorted; validate with min/max bounds, not just children.
• Diameter of a tree is the max of left-height + right-height over every node, not only the path through the root.
• Fenwick tree: point update and prefix sum in O(log n) via i & -i; segment tree if you need min/max or range updates.
• equals and hashCode must agree; mutable keys in a hash map get lost.
• Tries give O(L) insert and search and natural prefix queries at the cost of memory.
• BFS finds shortest paths in unweighted graphs; mark nodes visited when enqueuing.
• DFS finds components, paths and cycles; directed cycles are detected with grey (on-stack) nodes.
• Topological sort (Kahn): repeatedly remove in-degree-zero nodes; fewer than n output means a cycle.
• Dijkstra needs non-negative weights, O((V + E) log V); use Bellman-Ford for negative edges.
• Union-Find with path compression and union by size is effectively O(1) per operation.
• Two pointers need a monotonic property (usually sortedness) to know which pointer to move.
• Sliding window: expand right, shrink left while invalid; fails with negative numbers for sum constraints.
• Binary search on the answer works whenever feasibility is monotonic; use a half-open "first true" template.
• Prefix sums plus a hash map count subarrays with sum k in O(n), even with negatives.
• Monotonic stack solves next-greater and histogram problems in O(n) because each index is pushed and popped once.
• Interval problems start by sorting; meeting rooms uses a min-heap of end times.
• Backtracking is choose, explore, un-choose; copy the path when recording and prune early.
• Greedy needs a proof (exchange argument); coin change with {1, 3, 4} breaks greedy.
• Comparison sorts are Omega(n log n); counting and radix sort beat it for bounded integer keys.
• Stable sorts (merge, insertion, TimSort, counting) keep equal keys in original order.
• Quicksort is fastest in practice but O(n^2) worst case; random pivots or introsort fix it.
• DP needs optimal substructure and overlapping subproblems; define state, transition, base case, order, answer.
• DP complexity = number of states x work per state.
• 0/1 knapsack iterates capacity downward; unbounded iterates upward.
• LIS is O(n^2) with DP or O(n log n) with patience sorting and binary search.
• Interview flow: clarify, brute force, optimise, agree, code, test edge cases, discuss complexity.

Glossary

Adjacency list

Graph storage mapping each vertex to the list of its neighbours; O(V + E) space.

Amortized cost

Average cost per operation over a worst-case sequence of operations, even if single operations are occasionally expensive.

Backtracking

Depth-first search over choices that undoes each choice after exploring it, pruning branches that cannot succeed.

Balanced BST

A binary search tree (AVL, red-black) that rebalances itself to keep height O(log n).

BFS

Breadth-first search; explores a graph level by level using a queue.

Big-O

Asymptotic upper bound on how cost grows with input size, ignoring constants.

Binary heap

Complete binary tree in an array where each parent is no larger (min-heap) or no smaller (max-heap) than its children.

Binary search on the answer

Binary search over possible answer values using a monotonic feasibility check.

Collision

Two different keys hashing to the same bucket; resolved by chaining or open addressing.

DAG

Directed acyclic graph; a directed graph with no cycles, which always has a topological order.

Deque

Double-ended queue with O(1) insertion and removal at both ends.

DFS

Depth-first search; follows one path as deep as possible before backtracking, using recursion or a stack.

Dijkstra's algorithm

Greedy single-source shortest-path algorithm for non-negative edge weights using a min-heap.

Divide and conquer

Split a problem into independent subproblems, solve each, and combine the results (merge sort).

Dynamic programming

Solving problems with overlapping subproblems by storing and reusing sub-answers.

Exchange argument

Proof technique for greedy algorithms showing any optimal solution can be changed to include the greedy choice.

Fenwick tree

Binary indexed tree supporting prefix sums and point updates in O(log n).

Segment tree

Binary tree over array ranges that answers range queries and applies point or range updates in O(log n).

Treeify

Java 8+ HashMap conversion of a long collision chain into a red-black tree, only when the bin has 8+ entries and the table capacity is at least 64.

Hash function

Function mapping a key to an integer, used to pick a bucket in a hash table.

In-place

An algorithm that uses O(1) (or very little) extra memory beyond the input.

Load factor

Number of entries divided by number of buckets; triggers resizing when too high.

Memoisation

Caching the results of a recursive function so each input is computed once (top-down DP).

Monotonic stack

A stack kept in increasing or decreasing order, used for next-greater or next-smaller queries.

Open addressing

Collision strategy that stores all entries in the table itself and probes for another free slot.

Optimal substructure

Property that an optimal solution is composed of optimal solutions to subproblems.

Overlapping subproblems

Property that the same subproblems recur many times in a naive recursion.

Path compression

Union-Find optimisation that points nodes directly at their root during find.

Prefix sum

Running total array where the sum of any range is the difference of two entries.

Pseudo-polynomial

Running time polynomial in a numeric input value (like capacity W) but exponential in its bit length.

Quickselect

Partition-based selection of the k-th smallest element in O(n) average time.

Sliding window

Technique that maintains a contiguous range with two indices that only move forward.

Stable sort

A sort that preserves the relative order of elements with equal keys.

Tabulation

Bottom-up DP that fills a table iteratively in dependency order.

TimSort

Hybrid stable sort combining merge sort and insertion sort on natural runs; used by Python and Java for objects.

Topological sort

Linear ordering of a DAG's vertices so every edge points forward.

Trie

Prefix tree storing strings character by character along root-to-node paths.

Two pointers

Technique using two indices that move through data, often from both ends, to avoid nested loops.

Union-Find

Disjoint set union structure supporting near-constant-time find and union of groups.

Interview questions

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

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

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

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

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

def reverse_rec(head):
    if not head or not head.next:
        return head
    new_head = reverse_rec(head.next)
    head.next.next = head
    head.next = None
    return new_head

def merge(a, b):
    dummy = tail = ListNode()
    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

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

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

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

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

def can_finish(n, prereqs):
    g = [[] for _ in range(n)]; indeg = [0] * n
    for course, pre in prereqs:
        g[pre].append(course); indeg[course] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    done = 0
    while q:
        u = q.popleft(); done += 1
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return done == n

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

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

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

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

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = [0] * 26
        for c in w: key[ord(c) - 97] += 1
        groups[tuple(key)].append(w)
    return list(groups.values())

def top_k(nums, k):
    c = Counter(nums)
    return heapq.nlargest(k, c, key=c.get)

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

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

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

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

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

def clone_graph(node):
    copies = {}
    def dfs(n):
        if n in copies: return copies[n]
        c = Node(n.val); copies[n] = c
        c.neighbors = [dfs(x) for x in n.neighbors]
        return c
    return dfs(node) if node else None

class MinStack:
    def __init__(self): self.s = []
    def push(self, x):
        self.s.append((x, min(x, self.s[-1][1]) if self.s else x))
    def pop(self): self.s.pop()
    def top(self): return self.s[-1][0]
    def getMin(self): return self.s[-1][1]

from collections import OrderedDict
class LRUCache:
    def __init__(self, cap):
        self.cap, self.d = cap, OrderedDict()
    def get(self, k):
        if k not in self.d: return -1
        self.d.move_to_end(k)
        return self.d[k]
    def put(self, k, v):
        self.d[k] = v
        self.d.move_to_end(k)
        if len(self.d) > self.cap:
            self.d.popitem(last=False)   # evict least recently used

class MedianFinder:
    def __init__(self): self.low, self.high = [], []
    def addNum(self, x):
        heapq.heappush(self.low, -x)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))
    def findMedian(self):
        if len(self.low) > len(self.high): return -self.low[0]
        return (-self.low[0] + self.high[0]) / 2

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

def trap(h):
    l, r = 0, len(h) - 1
    lmax = rmax = water = 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

def min_window(s, t):
    need = Counter(t); missing = len(t)
    left = start = 0; best = float('inf')
    for right, c in enumerate(s):
        if need[c] > 0: missing -= 1
        need[c] -= 1
        while missing == 0:
            if right - left + 1 < best:
                best, start = right - left + 1, left
            need[s[left]] += 1
            if need[s[left]] > 0: missing += 1
            left += 1
    return "" if best == float('inf') else s[start:start + best]

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

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

def max_sliding_window(a, k):
    dq, out = deque(), []
    for i, x in enumerate(a):
        while dq and a[dq[-1]] <= x: dq.pop()
        dq.append(i)
        if dq[0] <= i - k: dq.popleft()
        if i >= k - 1: out.append(a[dq[0]])
    return out

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

def find_cheapest(n, flights, src, dst, k):
    dist = [float('inf')] * n; dist[src] = 0
    for _ in range(k + 1):
        nxt = dist[:]
        for u, v, w in flights:
            if dist[u] + w < nxt[v]: nxt[v] = dist[u] + w
        dist = nxt
    return -1 if dist[dst] == float('inf') else dist[dst]

import random
class RandomizedSet:
    def __init__(self): self.a, self.pos = [], {}
    def insert(self, x):
        if x in self.pos: return False
        self.pos[x] = len(self.a); self.a.append(x); return True
    def remove(self, x):
        if x not in self.pos: return False
        i, last = self.pos[x], self.a[-1]
        self.a[i], self.pos[last] = last, i
        self.a.pop(); del self.pos[x]; return True
    def getRandom(self): return random.choice(self.a)

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