Problem

Given an array of integers and an integer k > 0, find the length of the longest contiguous subarray whose sum of elements is at most k.

Examples

Example 1

1
2
3

Input: arr = [1, 2, 1, 0, 1, 1, 0], k = 4
Output: 5
Explanation: The subarray [1, 0, 1, 1, 0] has sum 3 and length 5, which is the longest possible with sum ≤ 4.

Example 2

1
2
3

Input: arr = [2, 1, 2, 3, 1], k = 5
Output: 3
Explanation: The subarray [2, 1, 2] has sum 5 and length 3.

Solution

Method 1 – Brute Force

Intuition

Try every possible subarray and check if its sum is at most k. Track the maximum length found.

Approach

  • For every starting index, try every possible ending index.
  • For each subarray, compute the sum and check if it is ≤ k.
  • Track the maximum length found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int longestSubarrayAtMostK(vector<int>& arr, int k) {
        int n = arr.size(), ans = 0;
        for (int i = 0; i < n; ++i) {
            int sum = 0;
            for (int j = i; j < n; ++j) {
                sum += arr[j];
                if (sum <= k) ans = max(ans, j - i + 1);
                else break;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func LongestSubarrayAtMostK(arr []int, k int) int {
    n, ans := len(arr), 0
    for i := 0; i < n; i++ {
        sum := 0
        for j := i; j < n; j++ {
            sum += arr[j]
            if sum <= k {
                if j-i+1 > ans { ans = j - i + 1 }
            } else {
                break
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int longestSubarrayAtMostK(int[] arr, int k) {
        int n = arr.length, ans = 0;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += arr[j];
                if (sum <= k) ans = Math.max(ans, j - i + 1);
                else break;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def longest_subarray_at_most_k(self, arr: list[int], k: int) -> int:
        n = len(arr)
        ans = 0
        for i in range(n):
            s = 0
            for j in range(i, n):
                s += arr[j]
                if s <= k:
                    ans = max(ans, j - i + 1)
                else:
                    break
        return ans

Complexity

  • ⏰ Time complexity: O(n^2), as we check all subarrays.
  • 🧺 Space complexity: O(1), only variables for sum and answer.

Method 2 – Sliding Window

Intuition

If all elements are non-negative, we can use a sliding window to efficiently find the longest subarray with sum at most k.

Approach

  • Initialize two pointers (left and right) and a running sum.
  • Expand the right pointer and add elements to the sum.
  • If the sum exceeds k, move the left pointer right and subtract elements from the sum until sum ≤ k.
  • Track the maximum window length found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int longestSubarrayAtMostK(vector<int>& arr, int k) {
        int n = arr.size(), ans = 0, sum = 0, left = 0;
        for (int right = 0; right < n; ++right) {
            sum += arr[right];
            while (sum > k && left <= right) {
                sum -= arr[left++];
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func LongestSubarrayAtMostK(arr []int, k int) int {
    n, ans, sum, left := len(arr), 0, 0, 0
    for right := 0; right < n; right++ {
        sum += arr[right]
        for sum > k && left <= right {
            sum -= arr[left]
            left++
        }
        if right-left+1 > ans { ans = right - left + 1 }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int longestSubarrayAtMostK(int[] arr, int k) {
        int n = arr.length, ans = 0, sum = 0, left = 0;
        for (int right = 0; right < n; right++) {
            sum += arr[right];
            while (sum > k && left <= right) {
                sum -= arr[left++];
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def longest_subarray_at_most_k(self, arr: list[int], k: int) -> int:
        n = len(arr)
        ans = s = left = 0
        for right in range(n):
            s += arr[right]
            while s > k and left <= right:
                s -= arr[left]
                left += 1
            ans = max(ans, right - left + 1)
        return ans

Complexity

  • ⏰ Time complexity: O(n), as each element is added and removed from the sum at most once.
  • 🧺 Space complexity: O(1), only variables for sum and pointers.