Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Longest Subarray with sum K (Positives)

MEDIUMProblemSolveExternal Links

Description

Given an array arr[] of positive integers and an integer k, find the length of the longest contiguous subarray whose elements sum to exactly k.

A subarray is a contiguous (non-empty) portion of the array — it consists of consecutive elements from arr. You need to find the subarray with sum equal to k that has the maximum possible length. If no subarray sums to k, return 0.

Important: All elements in the array are positive (greater than 0). This property is crucial because it means that as you extend a subarray by including more elements, the sum strictly increases — and as you shrink it, the sum strictly decreases. This monotonic behavior enables efficient solutions.

Examples

Example 1

Input: arr = [1, 2, 3, 1, 1, 1, 1], k = 3

Output: 3

Explanation: There are multiple subarrays that sum to 3:

  • [1, 2] (indices 0-1, length 2)
  • [3] (index 2, length 1)
  • [1, 1, 1] (indices 3-5, length 3)

The longest among them is [1, 1, 1] with length 3.

Example 2

Input: arr = [2, 3, 5, 1, 9], k = 10

Output: 3

Explanation: Subarrays summing to 10:

  • [2, 3, 5] (indices 0-2, length 3)
  • [1, 9] (indices 3-4, length 2)

The longest is [2, 3, 5] with length 3.

Example 3

Input: arr = [1, 1, 1, 1, 1], k = 100

Output: 0

Explanation: The total sum of the entire array is only 5, which is far less than 100. No subarray can possibly sum to 100, so the answer is 0.

Constraints

  • 1 ≤ arr.length ≤ 10^5
  • 1 ≤ arr[i] ≤ 10^4
  • 1 ≤ k ≤ 10^9

Editorial

Brute Force

Intuition

The most straightforward approach is to examine every possible subarray, compute its sum, and check if it equals k. If it does, compare its length against the longest we've found so far.

A subarray is defined by its starting index i and ending index j (where i ≤ j). So we enumerate all possible (i, j) pairs and calculate the sum of elements from index i to j.

Imagine you have a row of coins with different values. To find the longest consecutive group of coins summing to a target amount, you'd pick every possible starting coin, then keep adding coins to the right until you either hit the target, exceed it, or run out of coins. You'd track the longest group that matched exactly.

Step-by-Step Explanation

Let's trace with arr = [1, 2, 3, 1, 1, 1, 1], k = 3:

Step 1: Fix i=0. Try all subarrays starting at index 0:

  • j=0: sum = 1. Not equal to 3.
  • j=1: sum = 1+2 = 3. Match! Length = 2. Update max_len = 2.
  • j=2: sum = 1+2+3 = 6. Exceeds 3. Since all elements are positive, extending further only increases the sum. But we still check to be thorough.
  • j=3: sum=7, j=4: sum=8, j=5: sum=9, j=6: sum=10. None match.

Step 2: Fix i=1. Try subarrays starting at index 1:

  • j=1: sum=2. No match.
  • j=2: sum=2+3=5. No match.
  • j=3: sum=2+3+1=6. No match. Continue through remaining, none match.

Step 3: Fix i=2. j=2: sum=3. Match! Length = 1. max_len stays 2 (already better).

Step 4: Fix i=3. j=3: sum=1, j=4: sum=2, j=5: sum=1+1+1=3. Match! Length = 3. Update max_len = 3.

Step 5: Fix i=4. j=4: sum=1, j=5: sum=2, j=6: sum=3. Match! Length = 3. max_len stays 3 (tied).

Step 6: Fix i=5. j=5: sum=1, j=6: sum=2. No match. Fix i=6. j=6: sum=1. No match.

Result: max_len = 3.

Brute Force — Enumerate All Subarrays — For each starting index i, extend j rightward and accumulate the sum. When sum equals k, record the subarray length. Track the longest match found.

Algorithm

  1. Initialize max_len = 0
  2. For each starting index i from 0 to n-1:
    a. Initialize sum = 0
    b. For each ending index j from i to n-1:
    • Add arr[j] to sum
    • If sum == k, update max_len = max(max_len, j - i + 1)
    • If sum > k, break (since all elements are positive, extending further won't help)
  3. Return max_len

Code

#include <vector>
#include <algorithm>
using namespace std;

int longestSubarrayWithSumK(vector<int>& arr, int k) {
    int n = arr.size();
    int maxLen = 0;
    
    for (int i = 0; i < n; i++) {
        int sum = 0;
        for (int j = i; j < n; j++) {
            sum += arr[j];
            if (sum == k) {
                maxLen = max(maxLen, j - i + 1);
            }
            if (sum > k) break; // Optimization for positive integers
        }
    }
    
    return maxLen;
}
def longest_subarray_with_sum_k(arr, k):
    n = len(arr)
    max_len = 0
    
    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += arr[j]
            if current_sum == k:
                max_len = max(max_len, j - i + 1)
            if current_sum > k:
                break  # Optimization for positive integers
    
    return max_len
class Solution {
    public int longestSubarrayWithSumK(int[] arr, int k) {
        int n = arr.length;
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum += arr[j];
                if (sum == k) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
                if (sum > k) break;
            }
        }
        
        return maxLen;
    }
}

Complexity Analysis

Time Complexity: O(n²) in the worst case

The outer loop runs n times. For each starting index i, the inner loop can run up to n-i times. With the early break optimization (since elements are positive, we stop when sum > k), the average case can be better. But in the worst case — for example, when k is very large and no early break triggers — the total work is n + (n-1) + ... + 1 = n(n+1)/2 = O(n²).

Space Complexity: O(1)

We only use a few integer variables. No additional data structures that scale with input size.

Why This Approach Is Not Efficient

With n up to 10^5, the brute force approach can require up to ~5×10^9 operations in the worst case — far too slow for typical time limits.

The fundamental inefficiency is that we restart the sum computation from scratch for every new starting index i. When we move from i to i+1, we discard all the accumulated knowledge from the previous inner loop and start summing all over again.

There are two key observations that can help:

  1. Prefix Sum + Hash Map: If we precompute prefix sums, then the sum of any subarray arr[i..j] equals prefix[j+1] - prefix[i]. Finding whether any previous prefix sum equals current_prefix - k becomes a hash map lookup in O(1). This works for arrays with positive, negative, or zero values.

  2. Sliding Window / Two Pointers: Since all elements are positive, subarray sums have a monotonic property — adding an element always increases the sum, and removing one always decreases it. This means we can use two pointers that only move forward, achieving O(n) time.

Let's explore both approaches.

Better Approach - Prefix Sum with Hash Map

Intuition

The prefix sum technique transforms the problem of computing subarray sums into simple subtraction.

Define prefix[i] as the sum of the first i elements: prefix[0] = 0, prefix[1] = arr[0], prefix[2] = arr[0] + arr[1], and so on. Then the sum of any subarray arr[i..j] is simply prefix[j+1] - prefix[i].

Now the question becomes: for each index j, does there exist an earlier index i such that prefix[j+1] - prefix[i] = k? Rearranging: prefix[i] = prefix[j+1] - k.

So at each position, we compute the current prefix sum and ask: "Have I seen the value current_prefix - k before?" This is a classic hash map lookup.

To find the longest subarray, we store the earliest index where each prefix sum value was first seen. If the same prefix sum appears later, we don't overwrite — keeping the earliest occurrence maximizes the subarray length.

Think of it like a GPS tracking your cumulative distance walked. If at mile 15 you realize you need a stretch of exactly 3 miles, you ask: "When was I at mile 12?" If you crossed mile 12 at checkpoint #4, then the stretch from checkpoint #4 to now is exactly 3 miles long.

Step-by-Step Explanation

Let's trace with arr = [1, 2, 3, 1, 1, 1, 1], k = 3:

Step 1: Initialize hash map with {0: -1} (prefix sum 0 occurs "before" index 0). prefix_sum = 0, max_len = 0.

Step 2: Process index 0: prefix_sum = 0 + 1 = 1. Need = 1 - 3 = -2. Is -2 in map? No. Store {1: 0}. Map: {0:-1, 1:0}.

Step 3: Process index 1: prefix_sum = 1 + 2 = 3. Need = 3 - 3 = 0. Is 0 in map? YES, at index -1. Length = 1 - (-1) = 2. Update max_len = 2. Store {3: 1}.

Step 4: Process index 2: prefix_sum = 3 + 3 = 6. Need = 6 - 3 = 3. Is 3 in map? YES, at index 1. Length = 2 - 1 = 1. max_len stays 2. Store {6: 2}.

Step 5: Process index 3: prefix_sum = 6 + 1 = 7. Need = 7 - 3 = 4. Is 4 in map? No. Store {7: 3}.

Step 6: Process index 4: prefix_sum = 7 + 1 = 8. Need = 8 - 3 = 5. Is 5 in map? No. Store {8: 4}.

Step 7: Process index 5: prefix_sum = 8 + 1 = 9. Need = 9 - 3 = 6. Is 6 in map? YES, at index 2. Length = 5 - 2 = 3. Update max_len = 3.

Step 8: Process index 6: prefix_sum = 9 + 1 = 10. Need = 10 - 3 = 7. Is 7 in map? YES, at index 3. Length = 6 - 3 = 3. max_len stays 3.

Result: max_len = 3.

Prefix Sum + Hash Map — Find Earliest Complement — Build the prefix sum as we scan. At each position, look up whether (prefix_sum - k) appeared earlier in the hash map. The earliest occurrence gives the longest subarray.

Algorithm

  1. Initialize a hash map with {0: -1} (prefix sum 0 is seen before the array starts)
  2. Initialize prefix_sum = 0, max_len = 0
  3. For each index i from 0 to n-1:
    a. Add arr[i] to prefix_sum
    b. Compute need = prefix_sum - k
    c. If need exists in the hash map at index j, then length = i - j. Update max_len = max(max_len, length)
    d. If prefix_sum is NOT already in the hash map, store {prefix_sum: i} (keep earliest occurrence only)
  4. Return max_len

Code

#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int longestSubarrayWithSumK(vector<int>& arr, int k) {
    int n = arr.size();
    unordered_map<long long, int> prefixMap;
    prefixMap[0] = -1; // Prefix sum 0 before array starts
    
    long long prefixSum = 0;
    int maxLen = 0;
    
    for (int i = 0; i < n; i++) {
        prefixSum += arr[i];
        long long need = prefixSum - k;
        
        if (prefixMap.count(need)) {
            maxLen = max(maxLen, i - prefixMap[need]);
        }
        
        // Only store the first occurrence of each prefix sum
        if (!prefixMap.count(prefixSum)) {
            prefixMap[prefixSum] = i;
        }
    }
    
    return maxLen;
}
def longest_subarray_with_sum_k(arr, k):
    prefix_map = {0: -1}  # Prefix sum 0 before array starts
    prefix_sum = 0
    max_len = 0
    
    for i, num in enumerate(arr):
        prefix_sum += num
        need = prefix_sum - k
        
        if need in prefix_map:
            max_len = max(max_len, i - prefix_map[need])
        
        # Only store the first occurrence of each prefix sum
        if prefix_sum not in prefix_map:
            prefix_map[prefix_sum] = i
    
    return max_len
import java.util.HashMap;

class Solution {
    public int longestSubarrayWithSumK(int[] arr, int k) {
        HashMap<Long, Integer> prefixMap = new HashMap<>();
        prefixMap.put(0L, -1); // Prefix sum 0 before array starts
        
        long prefixSum = 0;
        int maxLen = 0;
        
        for (int i = 0; i < arr.length; i++) {
            prefixSum += arr[i];
            long need = prefixSum - k;
            
            if (prefixMap.containsKey(need)) {
                maxLen = Math.max(maxLen, i - prefixMap.get(need));
            }
            
            // Only store the first occurrence of each prefix sum
            if (!prefixMap.containsKey(prefixSum)) {
                prefixMap.put(prefixSum, i);
            }
        }
        
        return maxLen;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array once. Each iteration involves computing the prefix sum (O(1)), a hash map lookup (O(1) average), and a conditional hash map insertion (O(1) average). Total: n × O(1) = O(n).

Space Complexity: O(n)

In the worst case, every prefix sum is unique, so the hash map stores n+1 entries. This requires O(n) additional space.

Why This Approach Is Not Efficient

The prefix sum + hash map approach is O(n) in time, which is asymptotically optimal. However, it uses O(n) space for the hash map. For this specific problem where all elements are positive, we can do better.

The key observation: since every element is positive (≥ 1), adding an element to a subarray always increases its sum, and removing an element always decreases it. This means subarray sums are monotonically increasing as we extend and monotonically decreasing as we shrink.

This monotonic property means we never need to "jump back" — we can use a sliding window (two pointers) that only moves forward. If the current window sum is too small, we expand the right end. If it's too large, we shrink the left end. This achieves O(n) time with O(1) space.

Note: this optimization is ONLY valid when all elements are positive. If the array could contain zeros or negatives, the sum wouldn't be monotonically increasing with window size, and the hash map approach would be necessary.

Optimal Approach - Sliding Window (Two Pointers)

Intuition

Since all elements are positive, we can maintain a sliding window defined by two pointers left and right, both starting at 0. We track the sum of elements inside the window.

  • Expand: Move right forward to include a new element, increasing the window sum.
  • Shrink: Move left forward to exclude the leftmost element, decreasing the window sum.

The strategy:

  1. Keep expanding right to grow the window.
  2. If the window sum exceeds k, shrink from the left until the sum is ≤ k.
  3. If the window sum equals k exactly, record the window length if it's a new maximum.

Why does this work? Because all values are positive:

  • When sum > k: no matter how far we extend right, the sum will only get larger. The only way to reduce it is to move left forward. So we shrink.
  • When sum < k: we haven't accumulated enough yet, so extend right.
  • When sum == k: we've found a valid subarray. Record it and keep going to see if a longer one exists.

Both pointers only move forward (never backward), so each element is added at most once and removed at most once. This gives exactly 2n pointer movements = O(n) time.

Think of a rubber band stretched between your two hands over a ruler. You slide both hands rightward along the ruler, but never leftward. Your right hand moves to stretch the band (increase sum), and your left hand catches up to release tension (decrease sum). The longest stretch where the band tension equals exactly k is your answer.

Step-by-Step Explanation

Let's trace with arr = [1, 2, 3, 1, 1, 1, 1], k = 3:

Step 1: Initialize left=0, right=0, window_sum=0, max_len=0.

Step 2: Expand right=0: window_sum = 0+1 = 1. sum < k. Window: [1].

Step 3: Expand right=1: window_sum = 1+2 = 3. sum == k! Length = 1-0+1 = 2. Update max_len = 2. Window: [1, 2].

Step 4: Expand right=2: window_sum = 3+3 = 6. sum > k. Need to shrink.

Step 5: Shrink left=0→1: window_sum = 6-1 = 5. Still > k. Shrink again.

Step 6: Shrink left=1→2: window_sum = 5-2 = 3. sum == k! Length = 2-2+1 = 1. max_len stays 2. Window: [3].

Step 7: Expand right=3: window_sum = 3+1 = 4. sum > k. Shrink left=2→3: window_sum = 4-3 = 1. sum < k. Window: [1].

Step 8: Expand right=4: window_sum = 1+1 = 2. sum < k. Window: [1, 1].

Step 9: Expand right=5: window_sum = 2+1 = 3. sum == k! Length = 5-3+1 = 3. Update max_len = 3. Window: [1, 1, 1].

Step 10: Expand right=6: window_sum = 3+1 = 4. sum > k. Shrink left=3→4: window_sum = 4-1 = 3. sum == k! Length = 6-4+1 = 3. max_len stays 3. Window: [1, 1, 1].

Result: max_len = 3.

Sliding Window — Expand Right, Shrink Left — Watch the two pointers slide forward through the array. The window expands when the sum is too small, and shrinks when the sum is too large. When the sum exactly equals k, we record the window length.

Algorithm

  1. Initialize left = 0, window_sum = 0, max_len = 0
  2. For right from 0 to n-1 (expand window):
    a. Add arr[right] to window_sum
    b. While window_sum > k (window too large):
    • Subtract arr[left] from window_sum
    • Increment left
      c. If window_sum == k:
    • Update max_len = max(max_len, right - left + 1)
  3. Return max_len

Code

#include <vector>
#include <algorithm>
using namespace std;

int longestSubarrayWithSumK(vector<int>& arr, int k) {
    int n = arr.size();
    int left = 0;
    long long windowSum = 0;
    int maxLen = 0;
    
    for (int right = 0; right < n; right++) {
        windowSum += arr[right];
        
        // Shrink window from left while sum exceeds k
        while (windowSum > k) {
            windowSum -= arr[left];
            left++;
        }
        
        // Check if current window sums to exactly k
        if (windowSum == k) {
            maxLen = max(maxLen, right - left + 1);
        }
    }
    
    return maxLen;
}
def longest_subarray_with_sum_k(arr, k):
    n = len(arr)
    left = 0
    window_sum = 0
    max_len = 0
    
    for right in range(n):
        window_sum += arr[right]
        
        # Shrink window from left while sum exceeds k
        while window_sum > k:
            window_sum -= arr[left]
            left += 1
        
        # Check if current window sums to exactly k
        if window_sum == k:
            max_len = max(max_len, right - left + 1)
    
    return max_len
class Solution {
    public int longestSubarrayWithSumK(int[] arr, int k) {
        int n = arr.length;
        int left = 0;
        long windowSum = 0;
        int maxLen = 0;
        
        for (int right = 0; right < n; right++) {
            windowSum += arr[right];
            
            // Shrink window from left while sum exceeds k
            while (windowSum > k) {
                windowSum -= arr[left];
                left++;
            }
            
            // Check if current window sums to exactly k
            if (windowSum == k) {
                maxLen = Math.max(maxLen, right - left + 1);
            }
        }
        
        return maxLen;
    }
}

Complexity Analysis

Time Complexity: O(n)

Although there's a while loop inside the for loop, the total work across all iterations is bounded. The right pointer moves from 0 to n-1 (n moves). The left pointer also only moves forward and can move at most n times total (it never moves backward). So the total number of pointer moves is at most 2n = O(n).

Each element is added to window_sum exactly once (when right passes over it) and removed at most once (when left passes over it). This amortized analysis confirms O(n) total work.

Space Complexity: O(1)

We only use three variables (left, window_sum, max_len) plus the loop variable right. No hash map, no prefix array — just constant extra space. This is an improvement over the prefix sum approach's O(n) space.

Why this is optimal: We must examine each element at least once → Ω(n) is a lower bound. The sliding window achieves O(n) time and O(1) space, matching the lower bound for both. No algorithm can do better.