Binary search, search on the answer, and monotonic stacks

What it is

Two patterns joined by one idea: discard candidates in bulk using an ordering invariant.

Binary search halves a range each step because the range is ordered, giving $O(\log n)$. The version worth memorising is not "find this value" but "find the first position where a predicate becomes true", because that one function also gives you lower_bound, upper_bound, insertion point, count of a value, and every "smallest x such that" problem. Search on the answer applies the same machinery when the input is not sorted at all: what is monotonic is a feasibility predicate over the space of possible answers, so you binary search the answers and use a feasibility check where a comparison would normally go.

A monotonic stack keeps a stack whose values are sorted (increasing or decreasing from bottom to top) and pops anything that violates the order as new elements arrive. The popped elements are ones that can never win again, and the moment they are popped is exactly when their answer becomes known. It answers "for each element, what is the nearest element to its left or right that is larger or smaller" in $O(n)$.

Don't be confused: "the array must be sorted" is not the precondition for binary search. The precondition is that the predicate you are searching on is monotonic: once it becomes true it stays true. A sorted array is the most common way to get one, which is why the two get conflated, but a rotated sorted array is not sorted and is still binary searchable, and the answer space in min_capacity below is not an array at all. Say "monotonic predicate", not "sorted array", and you will spot the search-on-the-answer problems that everyone else brute forces.

Don't be confused: a monotonic stack is not a sorted stack you maintain for its own sake. The values in it are incidentally ordered; the point is that the stack holds exactly the elements whose answer is still unknown, and the ordering is what proves a new element resolves a contiguous block of them. If you cannot say which pending question each stack entry represents, you are pattern matching rather than reasoning, and the variants will catch you.

The problem it solves

Binary search's practical problem is not "search a sorted array"; a hash map does that faster. It is the family of questions a hash map cannot answer: where does this value belong, how many are less than this, what is the nearest value to this. Those are range and order questions, and they are why every database index is a B-tree rather than a hash table.

Search on the answer solves a class that looks intractable: "what is the minimum capacity that gets this done in $k$ days?" The direct approach requires inverting a complicated process. The binary search approach only requires simulating it, which is easy, and then searching. Turning an optimisation problem into a decision problem plus a search is one of the highest leverage moves in the whole pattern set.

The monotonic stack solves the $O(n^2)$ "for each element, scan for the nearest bigger one" shape. It comes up disguised: largest rectangle in a histogram, trapping rain water, stock span, and the sliding window maximum, which is the same idea with a deque.

Mechanics

"""Binary search, "search on the answer", and monotonic stacks.

Runnable: `python3 search_and_stacks.py`. Both families discard candidates using
an ordering invariant. Binary search discards half the range because the range is
sorted; a monotonic stack discards candidates that can never win again.
"""

import bisect


# --- Binary search: the boundary form, not the equality form -----------------
# Write ONE binary search and derive the rest. The version that returns "the
# first index where pred is True" handles find, lower_bound, upper_bound and
# insertion point; the version that compares for equality handles only one of
# them and has three places to put an off-by-one.
def first_true(lo, hi, pred):
    """Smallest x in [lo, hi) with pred(x) True, or hi if there is none.

    Requires pred to be monotonic: False...False True...True. That precondition
    is the whole algorithm; everything else is bookkeeping.
    """
    while lo < hi:
        mid = lo + (hi - lo) // 2      # not (lo+hi)//2: that overflows in Java/C++
        if pred(mid):
            hi = mid                   # mid might be the answer, so keep it
        else:
            lo = mid + 1               # mid is not, so discard it
    return lo


def lower_bound(arr, target):
    """First index with arr[i] >= target."""
    return first_true(0, len(arr), lambda i: arr[i] >= target)


def upper_bound(arr, target):
    """First index with arr[i] > target. count(target) = upper - lower."""
    return first_true(0, len(arr), lambda i: arr[i] > target)


def search_rotated(arr, target):
    """Rotated sorted array. Sortedness is broken globally but at least one half
    of any split is still sorted, and that is enough to decide which half to
    keep."""
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        if arr[lo] <= arr[mid]:                      # left half is sorted
            if arr[lo] <= target < arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                        # right half is sorted
            if arr[mid] < target <= arr[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1


# --- Search on the answer ----------------------------------------------------
# The input is not sorted and may not even be a list. What is monotonic is the
# PREDICATE over the answer space: if a capacity of 20 works, so does 21. So you
# binary search the answer, using a feasibility check as the comparison.
def min_capacity(weights, days):
    """Least ship capacity that moves all packages within `days` days, keeping
    order. Answer space is [max(weights), sum(weights)]."""

    def feasible(cap):
        used, load = 1, 0
        for w in weights:
            if load + w > cap:
                used += 1
                load = 0
            load += w
        return used <= days

    return first_true(max(weights), sum(weights) + 1, feasible)


def sqrt_floor(n):
    """Integer square root, to show the answer space need not come from a list."""
    return first_true(0, n + 1, lambda x: x * x > n) - 1


# --- Monotonic stack ---------------------------------------------------------
def next_greater(nums):
    """For each element, the next strictly greater element to its right, or -1.

    Invariant: the stack holds indices whose answers are still unknown, and
    their values are strictly decreasing from bottom to top. When a new value
    arrives it resolves every stacked index it beats. Each index is pushed once
    and popped once, so O(n) despite the nested loop.
    """
    out = [-1] * len(nums)
    stack = []                                   # indices, values decreasing
    for i, n in enumerate(nums):
        while stack and nums[stack[-1]] < n:
            out[stack.pop()] = n
        stack.append(i)
    return out


def largest_rectangle(heights):
    """Largest rectangle in a histogram. The classic payoff for the pattern.

    For each bar, the widest rectangle of that bar's height runs from the first
    bar to its left that is shorter, to the first bar to its right that is
    shorter. A monotonic increasing stack finds both boundaries in one pass:
    when bar i pops bar j, i IS j's right boundary and the new stack top is j's
    left boundary.
    """
    stack = []                                   # indices, heights increasing
    best = 0
    best_at = None
    for i, h in enumerate(heights + [0]):        # sentinel 0 flushes the stack
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] + 1 if stack else 0
            width = i - left
            if height * width > best:
                best = height * width
                best_at = (left, i, height)
        stack.append(i)
    return best, best_at


def daily_temperatures(temps):
    """How many days until a warmer day. Same stack, but store the distance
    rather than the value, which is what most variants actually ask for."""
    out = [0] * len(temps)
    stack = []
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            out[j] = i - j
        stack.append(i)
    return out


if __name__ == "__main__":
    arr = [1, 3, 3, 3, 5, 8, 8, 13]
    print("array               :", arr)
    print("lower_bound(3)      :", lower_bound(arr, 3))
    print("upper_bound(3)      :", upper_bound(arr, 3))
    print("count of 3          :", upper_bound(arr, 3) - lower_bound(arr, 3))
    print("lower_bound(4)      :", lower_bound(arr, 4), "(insertion point, 4 is absent)")
    print("agrees with bisect  :", (bisect.bisect_left(arr, 3), bisect.bisect_right(arr, 3)))

    rot = [12, 15, 18, 2, 5, 6, 8]
    print()
    print("rotated             :", rot)
    print("search_rotated(5)   :", search_rotated(rot, 5))
    print("search_rotated(12)  :", search_rotated(rot, 12))
    print("search_rotated(99)  :", search_rotated(rot, 99))

    w = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    print()
    print("weights             :", w, "sum =", sum(w))
    for d in (5, 3, 1):
        print(f"min_capacity(days={d:2}) :", min_capacity(w, d))
    print("sqrt_floor(2000)    :", sqrt_floor(2000), "since 44^2 =", 44 * 44, "and 45^2 =", 45 * 45)

    print()
    nums = [2, 1, 2, 4, 3]
    print("nums                :", nums)
    print("next_greater        :", next_greater(nums))
    temps = [73, 74, 75, 71, 69, 72, 76, 73]
    print("temperatures        :", temps)
    print("days until warmer   :", daily_temperatures(temps))
    hist = [2, 1, 5, 6, 2, 3]
    area, at = largest_rectangle(hist)
    print("histogram           :", hist)
    print("largest rectangle   :", area, "spanning [%d,%d) at height %d" % at)

Four details that decide whether your implementation is right.

mid = lo + (hi - lo) // 2, not (lo + hi) // 2. In Python they are equivalent because integers are arbitrary precision. In Java, C++ or Go they are not: lo + hi overflows for large arrays, and this exact bug sat in java.util.Arrays.binarySearch in the JDK for nine years before Joshua Bloch wrote it up in 2006. Writing the safe form in Python and saying why is a cheap, genuine signal.

The loop is while lo < hi with a half-open range, and the two branches are asymmetric. hi = mid keeps mid as a candidate, because pred(mid) was true and mid may be the first such index. lo = mid + 1 discards mid, because pred(mid) was false so mid definitively is not the answer. That asymmetry is what makes the loop terminate and be correct; a symmetric hi = mid - 1 alongside hi = mid is the classic infinite loop.

first_true returns hi when nothing satisfies the predicate, which is why lower_bound on an absent value returns the insertion point rather than -1. That is a feature, and it is why one function covers so many cases.

The sentinel in largest_rectangle. The loop iterates heights + [0], appending a zero-height bar. Without it, any bars still on the stack when the input ends are never resolved, and the answer is wrong whenever the tallest rectangle touches the right edge. The sentinel is not a hack; it is the standard way to say "the boundary condition is the same as a very short bar".

Worked example

array               : [1, 3, 3, 3, 5, 8, 8, 13]
lower_bound(3)      : 1
upper_bound(3)      : 4
count of 3          : 3
lower_bound(4)      : 4 (insertion point, 4 is absent)
agrees with bisect  : (1, 4)

rotated             : [12, 15, 18, 2, 5, 6, 8]
search_rotated(5)   : 4
search_rotated(12)  : 0
search_rotated(99)  : -1

weights             : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] sum = 55
min_capacity(days= 5) : 15
min_capacity(days= 3) : 21
min_capacity(days= 1) : 55
sqrt_floor(2000)    : 44 since 44^2 = 1936 and 45^2 = 2025

nums                : [2, 1, 2, 4, 3]
next_greater        : [4, 2, 4, -1, -1]
temperatures        : [73, 74, 75, 71, 69, 72, 76, 73]
days until warmer   : [1, 1, 4, 2, 1, 1, 0, 0]
histogram           : [2, 1, 5, 6, 2, 3]
largest rectangle   : 10 spanning [2,4) at height 5

The counting trick. upper_bound(3) - lower_bound(3) = 4 - 1 = 3, and there are indeed three 3s. This is how you count occurrences in a sorted array in $O(\log n)$ without a second data structure, and it falls out of having written the boundary form rather than the equality form. The bisect line confirms the implementation matches Python's standard library exactly, which is the cheapest possible correctness test and worth writing in an interview.

Read min_capacity as the shape of search-on-the-answer. The answer space is $[\max(w), \sum w] = [10, 55]$. Its lower end is forced (a capacity below the heaviest package can never ship it) and its upper end is trivially feasible (one day, everything). Feasibility is monotonic: if capacity 15 finishes in 5 days, 16 certainly does too. So binary search over the integers between 10 and 55, not over the array. With 5 days the answer is 15; with 3 days, 21; with 1 day, 55, which is the total, as it must be. Note the predicate simulates greedily and the greedy simulation is provably optimal here because order is fixed, so there is no choice to make. That justification is the part candidates skip and interviewers wait for.

Trace the histogram. Bars [2, 1, 5, 6, 2, 3], answer 10, spanning indices [2,4) at height 5. That is bars 5 and 6, two wide at height 5, giving 10. The alternatives are worth checking by hand: bar 6 alone is 6; height 2 across the whole array is $2 \times 6 = 12$, except bar 1 has height 1 so that rectangle does not exist; height 1 across all six is 6. Ten is right. When bar 2 at index 4 arrives, it pops index 3 (height 6, width 1, area 6), then pops index 2 (height 5, and now the stack top is index 1, so left = 2 and width = 4 - 2 = 2, area 10). The popping element supplies the right boundary and the new stack top supplies the left, which is the sentence to say out loud.

daily_temperatures shows why storing the index beats storing the value. The answer at index 2 is 4, meaning the 75-degree day waits four days for the 76. You can only produce a distance if the stack held indices, so push indices by default and read values through them.

Production evidence

git bisect is search on the answer. The commit history is the answer space, the predicate is "is the bug present at this commit", and the predicate is assumed monotonic: the bug was introduced once and persists. That assumption is exactly the precondition discussed above, and when it fails (a flaky bug, or a fix and a re-break) git bisect returns a wrong commit, which is the same failure mode as binary searching a non-monotonic predicate. It finds the culprit among 10,000 commits in about 14 builds.

Kafka's offset index. Kafka stores a sparse index mapping message offsets to physical file positions, and a consumer seeking an offset binary searches that index to find the nearest preceding entry, then scans forward within the segment. Sparse plus binary search plus a short linear scan is the standard shape, and it is why the index stays small enough to memory-map.

LSM-tree block indexes. LevelDB and RocksDB SSTables are sorted files divided into blocks, with a per-file index of block boundaries. A read binary searches the index to find the block, then binary searches or scans within the decompressed block. Same two-level structure, same reason.

Python's bisect. The standard library ships bisect_left and bisect_right, which are lower_bound and upper_bound under different names, and the docs explicitly document the "sorted list of records, search on a key" use. Java's Collections.binarySearch and C++'s std::lower_bound are the same API in different clothes.

Monotonic deques for running extrema. The $O(n)$ sliding window maximum, which is the monotonic stack turned into a deque so it can also drop elements leaving the window on the left, is the standard algorithm for a running max or min filter, including 1D morphological dilation and erosion in image processing. The naive version is $O(nk)$, and for a structuring element of any real size that difference is the difference between usable and not.

The debate

Should you ever write the equality-form binary search? It is shorter for the single case "does this exact value exist", and if the array has no duplicates and you need nothing else, it is fine. My position: write first_true and derive everything, every time. The reason is not elegance, it is that binary search is famously easy to get subtly wrong (Jon Bentley reported that around 90% of professional programmers failed to write a correct one given hours), and having exactly one loop whose invariant you have internalised beats having four variants you re-derive under pressure. The cost is one lambda.

When is search on the answer the wrong tool? When the predicate is not monotonic, and this is the failure that actually happens. If "capacity 20 works" does not guarantee "capacity 21 works", the search silently returns a wrong answer with no crash and no warning. Before using it, state the monotonicity argument out loud. The second case: when evaluating the predicate is expensive and the answer space is small. Binary search over 8 candidates costs 3 predicate evaluations against 8 for a linear scan, and if each evaluation is a 10-minute build, the constant factors and the code risk may favour the scan. The third: when you need all feasible answers rather than the boundary.

Monotonic stack versus a heap for "nearest greater" style problems. A heap gives you the global maximum, not the nearest one, so for nearest-element questions the heap is simply the wrong structure and reaching for it is a tell. Where they genuinely compete is sliding window maximum: a heap with lazy deletion is $O(n \log k)$ and is easier to write correctly, while the monotonic deque is $O(n)$ and is fiddlier. For $k$ up to a few thousand I would write the heap version and say I know the deque is $O(n)$, because the log factor is small and the deque's edge cases (equal values, expiry by index) are where bugs live. For a hot path over large windows, take the deque.

Follow-up Q&A

Prove the monotonic stack is $O(n)$ when it contains a nested while loop. Every index is pushed exactly once, so at most $n$ pushes happen across the entire run. Every iteration of the inner while performs one pop, and you cannot pop more than you push, so the inner loop body executes at most $n$ times in total across all iterations of the outer loop. Total work is $O(n)$. This is an amortised argument, not a per-iteration one, and stating it that way is the point of the question.

How do you handle duplicate values in a monotonic stack? By deciding whether the comparison is strict, and the right choice depends on the question. In next_greater the condition is <, so equal values do not pop each other and "next greater" means strictly greater. In largest_rectangle the condition is >=, so equal heights do pop. That looks like it produces a wrong (too narrow) rectangle for the popped bar, and it does, but the last bar of a run of equal heights computes the full width, so the maximum is still correct. Being able to explain why the seemingly wrong intermediate value does not affect the answer is a strong signal; if you are unsure in the room, use >= and verify on a [2,2,2] input.

Binary search on a rotated array with duplicates: what changes? The worst case degrades to $O(n)$ and there is no way around it. The algorithm decides which half is sorted by comparing arr[lo] to arr[mid]; with duplicates, arr[lo] == arr[mid] == arr[hi] tells you nothing about either half, as in [2,2,2,0,2,2]. The standard fix is to shrink the range by one from each end in that case, which is correct but is linear when the array is mostly one value. Say the bound honestly rather than claiming $O(\log n)$.

Your min_capacity search space starts at max(weights). Why not 0? Because a capacity below the heaviest single package makes the problem infeasible at any number of days, so the predicate is false throughout that region and including it is harmless but wasteful. It is not merely an optimisation though: if the feasibility function had been written to loop forever or divide by zero on an impossible capacity, starting at 0 would be a crash. Tying the search bounds to the problem's own constraints is what keeps the predicate total.

How would you binary search over floating point? Do not iterate to exact equality; it may never terminate. Either fix an iteration count (100 iterations of bisection on a float64 exhausts its precision, so a for _ in range(100) loop is both simple and provably converged) or loop while hi - lo > eps with an epsilon chosen from the problem's required precision. Stating the fixed-iteration version shows you have hit this before.

Give a real system where you would use search on the answer. Capacity and cost tuning. "What is the smallest instance count that keeps p99 under 200 ms?" is monotonic in instance count over the useful range, the predicate is a load test, and the search finds the boundary in $\log$ many tests instead of a linear sweep. The caveat is the same one as always: verify monotonicity, because with certain autoscaler and cache-warming behaviours it does not hold, and then you are bisecting noise.

Common misconceptions

"Binary search needs a sorted array." It needs a monotonic predicate. The rotated-array and search-on-the-answer cases in this file are both counterexamples, and both are common interview problems specifically because they test whether you learned the rule or the example.

"$O(\log n)$ means it is always the fastest way to search." For small $n$, a linear scan wins, because it is branch-predictable and cache-friendly while binary search jumps around memory. Real implementations, including several standard libraries' sort routines, switch to linear or insertion-based approaches under a threshold of a few dozen elements. The asymptotics are about growth, not about which is faster at $n = 16$.

"The monotonic stack stores the answers." It stores the questions: the elements still waiting for an answer. The answers are written into the output array at pop time. Getting this backwards is why people cannot adapt the pattern to a new variant.

"Trapping rain water needs a different algorithm." It is the same monotonic stack, or the same two pointers, depending on which formulation you pick. Recognising that a problem you have not seen is a re-skin of one you have is most of what the pattern list is for.

Interview delivery note

For any binary search, say the invariant before the code: "I am searching for the first index where the predicate is true. The predicate is monotonic because [reason]. lo is always a position where it might be true or beyond; hi is always a position I know satisfies it or the end." Then write first_true. This takes fifteen seconds and removes the single most common source of visible flailing on a whiteboard.

The senior-to-staff separator is recognising search-on-the-answer in a problem that does not look like a search at all. A senior candidate who is given "minimum capacity to ship in $k$ days" often starts constructing a greedy or a DP and gets tangled. The staff move is to stop and say: "I do not know how to compute the answer directly, but I can check an answer easily, and checking is monotonic, so I will binary search the answer space and spend my effort on the checker." Converting an optimisation problem into a decision problem plus a search is a transferable engineering instinct, not a trick, and interviewers who set these problems are looking for exactly that sentence.

The Staff & Team Lead Interview Reference