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.

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

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

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

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 indice