Longest Subarray Sum Less Equal To Target
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^51 <= nums[i] <= 10^41 <= k <= 10^9
Complexity
Show Complexity
- Time:
O(n) - Space:
O(1)
Hints
Show 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
Show PY Solution
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