Longest Subarray With Sum

Tags

Longest Subarray With Sum

Category

Arrays

Difficulty

Hard

Problem Statement

Given an array of non-negative integers and a target sum, find the length of the longest contiguous subarray whose elements sum to exactly the target. If no such subarray exists, return 0.

Intuition

Because all values are non-negative, the subarray sum behaves monotonically as we expand or shrink a sliding window. When the window sum is less than the target, expanding the window (moving the right pointer) can only increase or maintain the sum. When the window sum exceeds the target, shrinking the window (moving the left pointer) can only decrease or maintain the sum. This monotonic property makes a two-pointer sliding window approach both correct and efficient.

Approach

  1. Initialize two pointers left = 0 and right = 0, a running currentSum = 0, and maxLength = 0.
  2. While right < n: a. Add array[right] to currentSum. b. While currentSum > target and left <= right:
    • Subtract array[left] from currentSum.
    • Increment left. c. If currentSum == target:
    • Update maxLength = max(maxLength, right - left + 1). d. Increment right.
  3. Return maxLength.

Pseudocode

function longestSubarrayWithSum(array, target):
    left = 0
    currentSum = 0
    maxLength = 0

    for right from 0 to length(array) - 1:
        currentSum += array[right]

        while currentSum > target and left <= right:
            currentSum -= array[left]
            left++

        if currentSum == target:
            maxLength = max(maxLength, right - left + 1)

    return maxLength

Time & Space Complexity

  • Time: O(n) — Each pointer moves at most n times, so the total number of operations is at most 2n.
  • Space: O(1) — Only a constant number of variables are used.

Key Insights

  • The non-negative constraint is essential for the sliding window approach. If negative numbers were allowed, expanding the window could decrease the sum, breaking the monotonicity assumption.
  • For arrays with negative numbers, a prefix sum with hash map approach would be needed instead.
  • We only shrink the window when the sum exceeds the target, and we check for equality after shrinking.

Edge Cases

  • Empty array: return 0.
  • Target is 0: the longest subarray of consecutive zeros (if the array contains zeros).
  • No subarray sums to target: return 0.
  • Entire array sums to target: return the full length.
  • Array contains zeros: zeros can extend a valid subarray without changing the sum, so they may increase the answer.

Linked mentions