Local Search And Divide And Conquer

What's being tested

Demonstrates the ability to find a local minimum using algorithmic tradeoffs between local search (greedy/hill-climbing) and divide-and-conquer (binary-search-like) approaches. Interviewers probe correctness proofs (termination, invariants), complexity reasoning, and handling edge cases like boundaries and equal neighbors.

Patterns & templates

• Binary search on 1D arrays — check A[mid] vs A[mid-1]/A[mid+1], recurse left/right; guarantees O(log n) comparisons when strict inequality holds.

• Mid-column divide-and-conquer for 2D — find global minimum in a column (O(n)), compare to adjacent column, recurse to the half with smaller neighbor.

• Recurrence analysis — for an n×n matrix: $T(n)=T(n/2)+O(n)$ ⇒ overall O(n) time using mid-column strategy.

• Greedy local search (hill-climbing) — repeatedly move to a strictly smaller neighbor until none; simple, O(n*m) worst-case on n×m grid.

• Boundary invariants — treat edges as having “missing” neighbors; endpoints can be local minima by definition.

• Plateau handling — break ties deterministically (e.g., prefer left/up), or treat <= carefully to avoid infinite loops.

• Implementation tips — use A[i][j] indexing checks, guard mid computation (mid = lo + (hi-lo)/2) to avoid overflow in large domains.

Common pitfalls

Pitfall: Assuming hill-climbing is always fast — adversarial inputs can force scanning most elements; argue worst-case complexity.

Pitfall: Using <= vs < incorrectly on ties; this can cause nontermination on plateaus or miss valid local minima.

Pitfall: Off-by-one at boundaries — forgetting to check A[0]/A[n-1] (1D) or edge neighbors (2D) breaks correctness proofs.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.