Find Longest Subarray with Given Sum Using Sliding Window - Optimal Solution

Contents

ProblemExamplesVisualizationSolutionAlgorithmCodeTimeSpace

Problem Statement❯

Given an array of positive integers and a target sum k, your task is to find the length of the longest contiguous subarray whose elements sum up to exactly k.

If no such subarray exists, return 0.

This problem assumes all elements in the array are positive, which allows us to use an efficient sliding window approach.

Examples❯

Input Array Target Sum (k) Output Description
[1, 2, 3, 7, 5] 12 3 Subarray [2, 3, 7] is the longest that gives sum 12Visualization
[1, 1, 1, 1, 1, 1] 3 3 Subarray [1, 1, 1] gives sum 3, longest such subarray is of length 3Visualization
[5, 1, 2, 3, 1] 6 3 Subarray [1, 2, 3] and subarray [2, 3, 1] are validVisualization
[10, 2, 3] 15 3 Entire array sums to 15Visualization
[1, 2, 3] 7 0 No subarray sums to 7Visualization
[] 5 0 Empty array cannot have any subarrayVisualization
[5] 5 1 Single-element subarray equals targetVisualization
[1, 2, 3] 0 0 All elements are positive, can't reach 0 sumVisualization

Visualization Player

Solution❯

To solve the problem of finding the longest subarray with a given sum k, we can take advantage of a technique called the sliding window. This approach works efficiently when all elements in the array are positive.

Understanding the Goal

We need to find a sequence of contiguous elements (a subarray) in the array that adds up exactly to k. But among all such valid subarrays, we're interested in the one with the maximum length.

Why Sliding Window Works Here

Since all numbers are positive, the sum of a subarray can only increase if we add more elements. If at any point the current sum becomes greater than k, we know we need to shrink the window from the left to try reducing the sum.

How We Approach It

  • We start with two pointers: start and end, both at index 0 initially.
  • We also maintain a curr_sum variable to store the current subarray sum, and max_len to track the maximum length found.
  • As we move the end pointer through the array:
    • We add the current element to curr_sum.
    • If curr_sum becomes greater than k, we move the start pointer right, subtracting those values from curr_sum, until it is ≤ k.
    • If curr_sum == k, we calculate the window length (end - start + 1) and update max_len if it's larger than before.

What Happens in Special Cases?

  • No matching subarray: If no window ever sums to k, max_len remains 0.
  • Empty array: There's no subarray to check, so return 0.
  • Single element equals k: Then max_len is 1.
  • Target sum is 0: Since all elements are positive, we can't reach 0, so return 0.

Conclusion

This method is optimal and runs in linear time O(n) since each element is visited at most twice (once by end, once by start). It works beautifully for arrays with only positive numbers.

Algorithm Steps❯

  1. Given an array arr and a target sum k.
  2. Initialize variables: start = 0, curr_sum = 0, and max_len = 0.
  3. Traverse the array using a loop with index end:
  4. → Add arr[end] to curr_sum.
  5. → While curr_sum > k, subtract arr[start] from curr_sum and increment start.
  6. → If curr_sum == k, update max_len as max(max_len, end - start + 1).
  7. Return max_len as the result after the loop.

Code

Python
JavaScript
Java
C++
C
def longest_subarray_sum_k(arr, k):
    start = 0
    curr_sum = 0
    max_len = 0
    for end in range(len(arr)):
        curr_sum += arr[end]
        while curr_sum > k:
            curr_sum -= arr[start]
            start += 1
        if curr_sum == k:
            max_len = max(max_len, end - start + 1)
    return max_len

# Sample Input
arr = [1, 2, 3, 1, 1, 1, 1, 2]
k = 5
print("Longest Subarray Length:", longest_subarray_sum_k(arr, k))

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n)In the best case, the subarray with the desired sum is found early without many window adjustments.
Average CaseO(n)Each element is added and removed from the window at most once, resulting in linear time complexity.
Worst CaseO(n)Even if no valid subarray is found, the window expands and contracts linearly across the array.

Space Complexity

O(1)

Explanation: The algorithm uses constant extra space — only a few variables are maintained (start, end, curr_sum, max_len), regardless of input size.