Data Structures & Algorithms

Two indices scanning toward each other or at different speeds

• O(n) Complexity
• Space: O(1)

Maintain a window of elements — expand right, shrink left

• O(n) Complexity
• Space: O(1)

Pre-compute cumulative sums for O(1) range queries

• O(n) build, O(1) query Complexity
• Space: O(N)

Maximum subarray sum — keep running total or restart

• O(n) Complexity
• Space: O(1)

Place each number at its correct index in O(n)

• O(n) Complexity
• Space: O(1)

Cancel opposing votes — the majority survives

• O(n) Complexity
• Space: O(1)

Three-way partition with low / mid / high pointers

• O(n) Complexity
• Space: O(1)

Halve the search space every step — O(log n) on sorted data

• O(log n) Complexity
• Space: O(1)

Binary search over the answer space, not the array

• O(n log(max-min)) Complexity
• Space: O(1)

Stack that stays sorted — find next greater/smaller in O(n)

• O(n) Complexity
• Space: O(N)

Deque that keeps window max/min reachable in O(1)

• O(n) Complexity
• Space: O(K)

Use a stack to match opening and closing brackets

• O(n) Complexity
• Space: O(N)

Floyd's cycle detection — slow moves 1 step, fast moves 2

• O(n) Complexity
• Space: O(1)

In-place reversal with three pointers: prev / curr / next

• O(n) Complexity
• Space: O(1)

Min-heap tracks the front of K sorted lists

• O(n log k) Complexity
• Space: O(K)

Queue processes the tree level by level

• O(n) Complexity
• Space: O(W)

Recurse into children — pre / in / post order

• O(n) Complexity
• Space: O(H)

Compute each subtree's answer bottom-up

• O(n) Complexity
• Space: O(H)

Deepest node that is an ancestor of both targets

• O(n) Complexity
• Space: O(H)

Tree of characters for fast prefix lookups

• O(L) per op Complexity
• Space: O(N·L)

Flood-fill connected components in a grid

• O(rows·cols) Complexity
• Space: O(ROWS·COLS)

Order a DAG so every edge points forward

• O(V+E) Complexity
• Space: O(V+E)

Track connected components with path compression

• O(α(n)) per op Complexity
• Space: O(N)

Greedy shortest paths with a min-heap

• O(E log V) Complexity
• Space: O(V)

Relax all edges V-1 times — handles negative weights

• O(V·E) Complexity
• Space: O(V)

Start BFS from all sources at once

• O(rows·cols) Complexity
• Space: O(ROWS·COLS)

Current state depends on the last 1–2 states

• O(n) Complexity
• Space: O(1)

Include or exclude each item once

• O(n·W) Complexity
• Space: O(W)

Each item can be picked unlimited times

• O(n·W) Complexity
• Space: O(W)

2D table — characters match or skip one

• O(m·n) Complexity
• Space: O(M·N)

Patience sorting — binary search the tails

• O(n log n) Complexity
• Space: O(N)

Fill a grid from top-left to bottom-right

• O(m·n) Complexity
• Space: O(N)

Solve ranges by trying every split point

• O(n³) Complexity
• Space: O(N²)

Track distinct states that transition on decisions

• O(n·k) Complexity
• Space: O(K)

A size-K heap keeps the best K seen so far

• O(n log k) Complexity
• Space: O(K)

Max-heap (low half) + min-heap (high half)

• O(log n) add Complexity
• Space: O(N)

Heap of K list-fronts merges sorted sources

• O(n log k) Complexity
• Space: O(K)

At each index: choose it or skip it

• O(2ⁿ) Complexity
• Space: O(N)

Swap, recurse, swap back

• O(n!) Complexity
• Space: O(N)

Place, validate, prune invalid branches

• O(exp) Complexity
• Space: O(N)

Sort by end time, greedily take the earliest finish

• O(n log n) Complexity
• Space: O(1)

Track the farthest index reachable so far

• O(n) Complexity
• Space: O(1)