Longest Subarray Sum Less Equal To Target

medium
sliding-window

Description

Given an array of positive integers nums and a target k, find the length of the longest contiguous subarray whose sum is less than or equal to k. Return 0 if no such subarray exists.

Example 1:
Input: nums = [3, 1, 2, 7, 4, 2, 1, 1, 5], k = 8
Output: 4
Explanation: The longest subarray with sum <= 8 is [4, 2, 1, 1] with sum = 8 and length = 4.

Example 2:
Input: nums = [1, 2, 3], k = 6
Output: 3
Explanation: The entire array [1, 2, 3] has sum = 6 which is <= 6, so length = 3.

Example 3:
Input: nums = [5, 1, 3], k = 2
Output: 1
Explanation: Only single elements [1] with sum 1 <= 2 works. Length = 1.

Example 4:
Input: nums = [10, 20, 30], k = 5
Output: 0
Explanation: Every element is > 5, so no valid subarray exists.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^4
  • 1 <= k <= 10^9

Signature

def solution(nums: list[int], k: int) -> int: ...

Complexity
  • Time: O(n)
  • Space: O(1)

Hints
Pattern
Use a variable-size sliding window
Approach
Add nums[right] to sum. While sum > k, subtract nums[left] and move left. Track max length.
Complexity
Expand right to include elements, shrink left when sum exceeds k

Solutions

def solution(nums, target):
    left = 0
    curr = 0
    length = 0
    for right in range(len(nums)):
        curr += nums[right]
        while curr > target:
            curr -= nums[left]
            left += 1
        length = max(length, right - left + 1)
    return length