search-and-optimization

What this skill does

# 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.

---

## Individual Patterns

### Binary Search

**Recognition Signals**
- Input array is sorted (or can be sorted without changing the answer).
- Problem asks for the position of a target or the insertion point.
- O(log n) time is expected or required.

**Core Idea**
Maintain a search interval `[lo, hi]` and halve it each step by comparing the midpoint against the target. The invariant is that the answer always lies within the current interval. Choose between `lo = mid + 1` and `hi = mid` (or `hi = mid - 1`) depending on whether you want the leftmost or rightmost match.

**Python Template**

```python
from bisect import bisect_left, bisect_right
from typing import List

def binary_search(nums: List[int], target: int) -> int:
    """Return index of target, or -1 if not found."""
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

def left_bound(nums: List[int], target: int) -> int:
    """Return index of first element >= target."""
    return bisect_left(nums, target)

def right_bound(nums: List[int], target: int) -> int:
    """Return index of first element > target."""
    return bisect_right(nums, target)
```

**Key Edge Cases**
- Empty array — return -1 or 0 depending on variant.
- All elements identical — left_bound and right_bound diverge.
- Target smaller than all elements or larger than all elements.
- Integer overflow in `lo + hi` — use `lo + (hi - lo) // 2`.

**Common Mistakes**
- Off-by-one: using `lo < hi` when the loop should be `lo <= hi` (or vice versa).
- Forgetting to handle the case where `bisect_left` returns `len(nums)`.
- Mutating the input array when the problem requires preserving order.

---

### Binary Search on Answer

**Recognition Signals**
- Problem asks to "minimize the maximum" or "maximize the minimum".
- The answer lies in a bounded numeric range and is monotonic (if X works, all values above/below also work).
- A feasibility check can be written in O(n) or O(n log n).

**Core Idea**
Instead of searching in the input array, binary search over the space of possible answers. Define a predicate `feasible(x) -> bool` that returns True if the answer x satisfies all constraints. The answer space is monotonic: once feasible becomes True, it stays True (or vice versa). Binary search finds the boundary.

**Python Template**

```python
from typing import Callable, List

def binary_search_on_answer(
    lo: int,
    hi: int,
    feasible: Callable[[int], bool],
) -> int:
    """Find the smallest value in [lo, hi] where feasible returns True."""
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

def can_split(nums: List[int], max_sum: int, k: int) -> bool:
    """Check if nums can be split into <= k subarrays each with sum <= max_sum."""
    count, current = 1, 0
    for x in nums:
        if x > max_sum:
            return False
        if current + x > max_sum:
            count += 1
            current = x
        else:
            current += x
    return count <= k
```

**Key Edge Cases**
- Single-element input where lo == hi immediately.
- The feasibility check must handle individual elements exceeding the candidate answer.
- Floating-point variant: use a fixed number of iterations (e.g., 100) instead of `lo < hi`.
- Off-by-one in bounds: `lo` should be the minimum possible answer, `hi` the maximum.

**Common Mistakes**
- Reversing the predicate direction (searching for max when predicate checks min feasibility).
- Setting initial bounds too tight and excluding the actual answer.
- Forgetting that maximizing the minimum requires flipping the search direction.

---

### Two Pointers

**Recognition Signals**
- Sorted array with a pair-sum or triplet-sum target.
- "Find two elements that satisfy a condition" with O(1) extra space.
- Removing duplicates in-place, or partitioning an array.
- Merging two sorted sequences.

**Core Idea**
Place one pointer at each end of a sorted array (opposite direction) or both at the start (same direction). Move pointers inward based on how the current state compares to the target. Each pointer moves at most n times, giving O(n) total. The technique exploits sorted order to prune the search space without nested loops.

**Python Template**

```python
from typing import List, Tuple, Optional

def two_sum_sorted(nums: List[int], target: int) -> Optional[Tuple[int, int]]:
    """Find indices of two numbers in sorted array that sum to target."""
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return (lo, hi)
        elif s < target:
            lo += 1
        else:
            hi -= 1
    return None

def remove_duplicates(nums: List[int]) -> int:
    """Remove duplicates in-place from sorted array. Return new length."""
    if not nums:
        return 0
    write = 1
    for read in range(1, len(nums)):
        if nums[read] != nums[read - 1]:
            nums[write] = nums[read]
            write += 1
    return write
```

**Key Edge Cases**
- Array with fewer than 2 elements.
- Multiple valid pairs — decide if you need the first, all, or any.
- Duplicate values that cause pointer movement to skip valid answers.
- Negative numbers affecting sum direction.

**Common Mistakes**
- Using two pointers on an unsorted array without sorting first.
- Not skipping duplicates when the problem asks for unique pairs.
- Returning indices from the sorted array when the problem wants original indic