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

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❯

Step-by-Step Beginner-Friendly Solution: Longest Subarray with Given Sum (k)

Understanding the Problem

We are given an array of positive integers and a target value k. Our task is to find the longest contiguous subarray whose elements sum up exactly to k.

Let’s break this down:

A subarray is a part of the array with consecutive elements.
We are not interested in all such subarrays — only the one that has the maximum length and whose total sum is k.

Example to Understand

arr = [1, 2, 3, 1, 1, 1, 4, 2, 3], k = 6

Let’s walk through this manually:

[1, 2, 3] → sum = 6 → valid, length = 3
[1, 1, 1, 1, 2] → sum = 6 → valid, length = 5
[4, 2] → sum = 6 → valid, length = 2

So, the longest subarray with sum = 6 is length 5.

How Can We Solve This Efficiently?

We use a powerful technique called the sliding window, which is ideal when all array elements are positive.

Why Sliding Window Works for Positive Numbers

When elements are positive:

Adding more elements to the window increases the sum.
To reduce the sum, we can safely remove elements from the beginning of the window.

Approach: Sliding Window Algorithm

Initialize two pointers start and end at index 0.
Maintain a variable curr_sum to store the current sum of the window.
Also keep track of max_len to record the maximum length of a valid subarray found so far.

Edge Cases: What Happens Then?

No Valid Subarray: max_len remains 0.
Empty Array: Nothing to process, so return 0.
Single Element Equals k: Return 1 as that single element forms the subarray.
Target Sum is 0: With all elements positive, we cannot reach a sum of 0, so return 0.

This solution is very efficient. It visits each element at most twice — once when expanding the window and once when shrinking it — giving it a time complexity of O(n).

Note: This technique only works when all elements in the array are positive. If negative numbers are allowed, we’ll need a different approach such as prefix sums with a hashmap.

Algorithm Steps❯

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

Code

C++

Python

Java

Rust

Kotlin

Swift

#include <stdio.h>

int longestSubarraySumK(int arr[], int n, int k) {
    int start = 0, curr_sum = 0, max_len = 0;
    for (int end = 0; end < n; end++) {
        curr_sum += arr[end];
        while (curr_sum > k) {
            curr_sum -= arr[start++];
        }
        if (curr_sum == k) {
            if (max_len < end - start + 1)
                max_len = end - start + 1;
        }
    }
    return max_len;
}

int main() {
    int arr[] = {1, 2, 3, 1, 1, 1, 1, 2};
    int k = 5;
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Longest Subarray Length: %d\n", longestSubarraySumK(arr, n, k));
    return 0;
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n)	In the best case, the subarray with the desired sum is found early without many window adjustments.
Average Case	O(n)	Each element is added and removed from the window at most once, resulting in linear time complexity.
Worst Case	O(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.

⬅ Previous TopicFind Kth Smallest Element

Next Topic ⮕Longest Subarray with Given Sum (Positives and Negatives)

Comments

Loading comments...