Binary Search on Sums with Prefix Sums

When a problem asks for a split point, threshold, or window length based on sum constraints, combine prefix sums with binary search on length or value.

Try this in Python

def longest_subarray_sum_leq(nums: list[int], limit: int) -> int:
    """Find longest length L such that some subarray of length L has sum <= limit (illustrative)."""
    p = [0]
    for x in nums:
        p.append(p[-1] + x)

    def exists_len(L: int) -> bool:
        if L == 0:
            return True
        for i in range(L, len(p)):
            if p[i] - p[i - L] <= limit:
                return True
        return False

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


print(longest_subarray_sum_leq([2, 1, 3, 4], 6))

Key takeaways

• exists_len can be optimized further; this version is readable for learning.
• If check is too slow, look for two-pointer alternatives.
• Always validate empty array.