Longest Subarray With Sum At Most K

Problem

Given an array of positive integers, find the length of the longest subarray whose sum is at most a given value k.

Input:  nums = [1,2,1,0,1,1,0], k = 4
Output: 5

Python Solution

def longest_subarray_sum_at_most_k(nums, k):
    left = 0
    window_sum = 0
    best = 0
    for right, num in enumerate(nums):
        window_sum += num
        while window_sum > k:
            window_sum -= nums[left]
            left += 1
        best = max(best, right - left + 1)
    return best

C++ Solution

int longestSubarraySumAtMostK(vector<int>& nums, int k) {
    int left = 0, windowSum = 0, best = 0;
    for (int right = 0; right < nums.size(); right++) {
        windowSum += nums[right];
        while (windowSum > k) {
            windowSum -= nums[left];
            left++;
        }
        best = max(best, right - left + 1);
    }
    return best;
}

Java Solution

class Solution {
    public int longestSubarraySumAtMostK(int[] nums, int k) {
        int left = 0, windowSum = 0, best = 0;
        for (int right = 0; right < nums.length; right++) {
            windowSum += nums[right];
            while (windowSum > k) {
                windowSum -= nums[left];
                left++;
            }
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Complexity

Time: O(n) — the left pointer only moves forward, so total pointer movement is bounded by n. Space: O(1) — only the window sum and two pointers are tracked. This only works because all elements are non-negative, so shrinking the window strictly decreases the sum.