Binary Search on Values (Answer Space)

This is the same big idea as search-on-answer, but the check often uses prefix sums, greedy packing, or simulation. Think: "Is answer ≤ mid?" vs "Is answer ≥ mid?"

Try this in Python

def max_k_with_prefix_constraint(nums: list[int], limit: int) -> int:
    """Toy: largest k such that sum of first k elements <= limit (monotone in k)."""
    p = [0]
    for x in nums:
        p.append(p[-1] + x)

    def ok(k: int) -> bool:
        return p[k] <= limit

    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if ok(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo


print(max_k_with_prefix_constraint([2, 2, 2, 2], 5))

Key takeaways

• Prefix sums make range sums O(1) inside check.
• Be careful with upper-mid mid = (lo+hi+1)//2 when maximizing k.
• Write ok(0) and ok(n) edge checks.