search-and-optimization

Search and Optimization Patterns

This reference covers eight foundational search and optimization techniques that appear across competitive programming, coding interviews, and production algorithms. Each pattern includes recognition signals, a core idea summary, a Python template with type hints, key edge cases, and common mistakes.

---

Pattern Recognition Table

Trigger Signals	Technique	Typical Complexity
Sorted array, find target, O(log n) required	Binary Search	O(log n)
"Minimize the maximum", "find smallest feasible value"	Binary Search on Answer	O(n log S) where S = search space
Sorted array, find pair with target sum, in-place	Two Pointers	O(n)
Fixed/variable-length subarray, substring constraints	Sliding Window	O(n)
Local optimal leads to global optimal, exchange argument	Greedy	O(n log n) typical
Range sum queries, subarray sums, 2D region sums	Prefix Sums	O(n) build, O(1) query
Overlapping intervals, merge/insert, scheduling	Merge Intervals	O(n log n)
Next greater/smaller element, histogram areas	Monotonic Stack	O(n)

---

Constraint-to-Technique Mapping

When the problem does not immediately suggest a technique, use constraints as a guide:

• n <= 10^5 and "find minimum/maximum feasible" — Binary search on answer with a greedy or simulation check function.
• Sorted input + pair/triplet finding — Two pointers before considering hash maps. Saves space and often required by the problem.
• Contiguous subarray/substring with a constraint — Sliding window. If the constraint is a sum threshold, variable-size window. If fixed length k, fixed-size window.
• Multiple range sum queries on static data — Prefix sums. For 2D grids, build a 2D prefix sum matrix.
• "Given a set of intervals" — Sort by start (or end), then merge or sweep. Check if the problem is really interval scheduling (sort by end, greedy).
• "For each element, find the next greater/smaller" — Monotonic stack. Direction of traversal (left-to-right or right-to-left) depends on whether you need "next" or "previous".
• Optimization under constraints with greedy proof — Try exchange argument: if swapping any two elements in the solution cannot improve it, greedy works.