Longest Subarray With Sum at Most K: Monotonic Stack on Prefix Sums

Problem Statement#

Given an integer array nums (which can contain negative numbers) and an integer k, return the length of the longest contiguous subarray whose sum is at most k. If no such subarray exists, return 0. The all-positive variant collapses to a sliding window, but the general signed case is what makes the problem interesting and is what interviewers actually ask.

Why This Problem Matters#

This problem is the canonical signed-prefix-sum exercise. It teaches three transferable skills: turning a subarray-sum question into a prefix-sum lookup, recognising when a monotonic stack collapses an O(n^2) scan into O(n), and pivoting to a Fenwick tree (BIT) or segment tree when streaming or online queries are required. Google, Meta, and Amazon use this and its sibling Shortest Subarray With Sum at Least K (LeetCode 862) to test whether you can think in terms of prefix sums under the hood.

A clean linear solution shows that you can resist the urge to slap a sliding window on a problem that does not satisfy the monotonicity it requires. Negative numbers break the standard window because shrinking from the left can make the sum go up, not down.

The Core Insight#

Let prefix[0] = 0 and prefix[i] = nums[0] + ... + nums[i - 1]. A subarray sum from index l to r - 1 equals prefix[r] - prefix[l]. We want the longest pair (l, r) with prefix[r] - prefix[l] less than or equal to k, equivalently prefix[l] greater than or equal to prefix[r] - k.

Two structural observations make this linear.

1. Among all candidate left endpoints l, only those whose prefix[l] is strictly less than every later prefix[l'] with l' less than l + something are useful. If l1 is less than l2 and prefix[l1] is less than or equal to prefix[l2], then l1 always dominates l2 because it gives a longer subarray and a smaller (or equal) starting prefix. This means we only need a strictly decreasing stack of prefix values by index.
2. Sweep r from right to left. When prefix[r] - prefix[stack.top] is at most k, we record the length and pop the stack, because any later (smaller) r cannot use that same l to produce a longer subarray.

Each index is pushed once and popped at most once, giving O(n) time and O(n) space.

For online or streaming variants where the array grows over time, a Fenwick tree (BIT) keyed by compressed prefix-sum values supports the same queries in O(log n) per insertion. Keep position info in the tree so you can recover the leftmost valid index.

Visual Dry Run#

Take nums = [3, -1, 4, -2, 1] and k = 4.

prefix = [0, 3, 2, 6, 4, 5]    indices 0..5
 
Build decreasing stack of (index, prefix) by walking left to right,
pushing only when prefix is strictly smaller than current top:
  i=0 prefix=0 -> push (0,0)        stack: [(0,0)]
  i=1 prefix=3 -> 3 not < 0, skip   stack: [(0,0)]
  i=2 prefix=2 -> 2 not < 0, skip   stack: [(0,0)]
  i=3 prefix=6 -> skip              stack: [(0,0)]
  i=4 prefix=4 -> skip              stack: [(0,0)]
  i=5 prefix=5 -> skip              stack: [(0,0)]
 
Sweep r from 5 down to 1:
  r=5 prefix=5  top=(0,0)  diff=5 > 4, no pop, no answer here
  r=4 prefix=4  top=(0,0)  diff=4 <= 4 -> length 4-0=4, pop. stack empty.
  r=3 prefix=6  stack empty, skip
  r=2 prefix=2  stack empty, skip
  r=1 prefix=3  stack empty, skip
 
Answer = 4

The longest subarray with sum at most 4 has length 4 and corresponds to nums[0..3] whose sum is 3 + -1 + 4 + -2 = 4.

Solution (Optimal)#

from typing import List
 
class Solution:
    def longestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
 
        # Build strictly decreasing monotonic stack of indices by prefix value
        stack = []
        for i in range(n + 1):
            if not stack or prefix[i] < prefix[stack[-1]]:
                stack.append(i)
 
        best = 0
        # Sweep right endpoints from largest to smallest
        for r in range(n, 0, -1):
            while stack and prefix[r] - prefix[stack[-1]] <= k:
                if r - stack[-1] > best:
                    best = r - stack[-1]
                stack.pop()
        return best

function longestSubarray(nums, k) {
  const n = nums.length;
  const prefix = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) prefix[i + 1] = prefix[i] + nums[i];
 
  // Strictly decreasing monotonic stack of indices by prefix value
  const stack = [];
  for (let i = 0; i <= n; i++) {
    if (!stack.length || prefix[i] < prefix[stack[stack.length - 1]]) {
      stack.push(i);
    }
  }
 
  let best = 0;
  for (let r = n; r >= 1; r--) {
    while (stack.length && prefix[r] - prefix[stack[stack.length - 1]] <= k) {
      best = Math.max(best, r - stack[stack.length - 1]);
      stack.pop();
    }
  }
  return best;
}

Complexity. Time is O(n) because each index is pushed at most once and popped at most once, and the prefix-sum build is O(n). Space is O(n) for the prefix array and the stack. This is asymptotically optimal: any solution must read the input.

For online variants where elements stream in and the longest valid subarray must be reported after each push, escalate to a Fenwick tree (BIT) keyed by compressed prefix-sum values. Each insertion and query is O(log n). A segment tree with point-update and range-min query on prefix-sum positions also works and gives more flexibility if you later need range deletes.

Common Mistakes#

• Reaching for a sliding window. Sliding window assumes monotone behaviour as the window grows or shrinks, which fails with negative numbers because shrinking from the left can increase the sum.
• Sweeping r left to right while popping. You must sweep right to left so that earlier r cannot produce a longer answer using the same l.
• Building a non-strict stack. If equal prefix values are kept, the stack pops incorrect candidates and lengths are wrong.
• Forgetting to include prefix[0] = 0 as a candidate. Many subarrays start at index 0, and missing this drops correct answers.
• Confusing this problem with LeetCode 862 Shortest Subarray With Sum at Least K. The shortest-at-least version uses a monotonic deque on prefix sums, not a stack, and the comparison flips.

Interview Tips#

• State explicitly: "Sliding window does not work because of negative numbers; I will use prefix sums plus a monotonic stack." This pre-empts the interviewer's first question.
• Sketch the prefix array and circle the strictly decreasing subsequence. The visual makes the stack invariant obvious.
• Compare the structure with LeetCode 862. Same prefix-sum framing, different monotonic structure (stack versus deque), opposite comparison.
• Mention the Fenwick tree (BIT) extension if the interviewer asks about streaming. "I would compress prefix sums and store positions in a BIT for log-time queries." That is the senior-level ending.
• Walk through one push and one pop. Many candidates write the code and never trace it; tracing builds interviewer confidence.

Follow-up Questions#

• LeetCode 862 Shortest Subarray With Sum at Least K. Use a deque to maintain a strictly increasing prefix-sum stack and pop from the front.
• All-positive variant. Replace the stack with a sliding window in O(n) and O(1) extra space.
• Online streaming variant. Coordinate-compress prefix sums and use a Fenwick tree (BIT) or segment tree for O(log n) queries per update.
• Return the actual subarray, not just its length. Track the indices alongside the length when you update best.
• Multiple bounds. Find the longest subarray with sum between lo and hi inclusive. Same prefix-sum idea with a sorted multiset and two-bound queries.

Key Takeaways#

• Convert the subarray-sum constraint into a prefix-sum query: prefix[r] - prefix[l] at most k.
• A strictly decreasing monotonic stack of prefix values captures every left endpoint that can ever win.
• Sweep r from right to left and pop greedily: each index is pushed and popped at most once for O(n) time.
• Sliding window does not work in the signed case; this is the prototypical problem that breaks the window pattern.
• For streaming inputs, a Fenwick tree (BIT) over compressed prefix sums upgrades the structure to O(log n) per update and query.
• The mirror problem, Shortest Subarray With Sum at Least K, uses a monotonic deque rather than a stack; mastering both completes the prefix-sum-with-monotonic-structure family.