Longest Subarray with Sum ≤ K — Monotonic Queue + Prefix

Problem

Return the length of the longest subarray with sum <= k.

Approach — Prefix Sum + Monotonic Stack

Build prefix sum array. For right endpoint, find leftmost prefix sum such that prefix[r] - prefix[l] <= k.

Preprocess: build decreasing stack of prefix sum indices (only smaller prefix sums are useful as left endpoints).

Time: O(n) | Space: O(n)

Solutions

Python

class Solution:
    def longestSubarray(self, nums: list[int], k: int) -> int:
        n=len(nums)
        prefix=[0]*(n+1)
        for i,x in enumerate(nums): prefix[i+1]=prefix[i]+x
        stack=[]
        for i in range(n+1):
            if not stack or prefix[i]<prefix[stack[-1]]: stack.append(i)
        ans=0
        for r in range(n,0,-1):
            while stack and prefix[r]-prefix[stack[-1]]<=k:
                ans=max(ans,r-stack[-1]); stack.pop()
        return ans

Complexity

Time: O(n) | Space: O(n)