Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Longest Subarray with sum K (All Integers)

MEDIUMProblemSolveExternal Links

Description

Given an array arr[] containing integers (which may include both positive and negative values) and an integer k, find the length of the longest contiguous subarray whose elements sum to exactly k.

A subarray is a contiguous sequence of elements within the array. For example, in [1, 2, 3, 4], the subarrays include [1], [1, 2], [2, 3, 4], etc., but NOT [1, 3] (not contiguous).

If no subarray sums to k, return 0.

Why this problem matters: This is a foundational problem that teaches the powerful prefix sum + hash map technique — a pattern that appears in dozens of other problems (subarray sum equals K, count of subarrays with given sum, etc.). The presence of negative numbers makes this problem significantly harder than the positive-only version, because the sliding window technique breaks down.

Examples

Example 1

Input: arr = [10, 5, 2, 7, 1, -10], k = 15

Output: 6

Explanation: Several subarrays sum to 15:

  • [5, 2, 7, 1] → sum = 15, length = 4
  • [10, 5] → sum = 15, length = 2
  • [10, 5, 2, 7, 1, -10] → sum = 15, length = 6

The longest subarray with sum 15 has length 6 (the entire array). Notice how the -10 at the end brings the running sum back down to 15, extending the valid subarray.

Example 2

Input: arr = [-5, 8, -14, 2, 4, 12], k = -5

Output: 5

Explanation: Subarrays with sum = -5:

  • [-5] → sum = -5, length = 1
  • [-5, 8, -14, 2, 4] → sum = -5, length = 5

The longest is [-5, 8, -14, 2, 4] with length 5. The negative target value is perfectly valid.

Example 3

Input: arr = [10, -10, 20, 30], k = 5

Output: 0

Explanation: No contiguous subarray sums to 5. The possible subarray sums are: 10, 0, 20, 50, -10, 10, 40, 20, 30, 50. None equal 5, so we return 0.

Constraints

  • 1 ≤ arr.size() ≤ 10^5
  • -10^4 ≤ arr[i] ≤ 10^4
  • -10^9 ≤ k ≤ 10^9

Editorial

Brute Force

Intuition

The most straightforward approach is to consider every possible subarray, compute its sum, and check if it equals k. If it does, we compare its length against our running best.

A subarray is defined by its start index i and end index j (where i ≤ j). We can enumerate all possible (i, j) pairs, compute the sum of elements from index i to j, and track the maximum length among those that sum to k.

Think of it like reading a book page by page: for each starting page, you read forward one page at a time, keeping a running total of words. If at any point your total matches the target, you check if this is the longest stretch you've found.

Step-by-Step Explanation

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

Step 1 (i=0): Start a new subarray from index 0.

  • j=0: sum = 1. Is 1 == 3? No.
  • j=1: sum = 1 + (-1) = 0. Is 0 == 3? No.
  • j=2: sum = 0 + 5 = 5. Is 5 == 3? No.
  • j=3: sum = 5 + (-2) = 3. Is 3 == 3? YES! Length = 3-0+1 = 4. maxLen = 4.
  • j=4: sum = 3 + 3 = 6. Is 6 == 3? No.

Step 2 (i=1): Start from index 1.

  • j=1: sum = -1. No.
  • j=2: sum = -1 + 5 = 4. No.
  • j=3: sum = 4 + (-2) = 2. No.
  • j=4: sum = 2 + 3 = 5. No.

Step 3 (i=2): Start from index 2.

  • j=2: sum = 5. No.
  • j=3: sum = 5 + (-2) = 3. YES! Length = 3-2+1 = 2. maxLen stays 4 (4 > 2).
  • j=4: sum = 3 + 3 = 6. No.

Step 4 (i=3): sum = -2, then 1. No matches.
Step 5 (i=4): sum = 3. YES! Length = 1. maxLen stays 4.

Result: maxLen = 4 (subarray [1, -1, 5, -2]).

Brute Force — Enumerate All Subarrays — Watch how the brute force checks every possible subarray by fixing a start index i, then extending j rightward while maintaining a running sum.

Algorithm

  1. Initialize maxLen = 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 maxLen = max(maxLen, j - i + 1)
  3. Return maxLen

Code

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

class Solution {
public:
    int longestSubarrayWithSumK(vector<int>& arr, int k) {
        int n = arr.size();
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            long long sum = 0;
            for (int j = i; j < n; j++) {
                sum += arr[j];
                if (sum == k) {
                    maxLen = max(maxLen, j - i + 1);
                }
            }
        }
        
        return maxLen;
    }
};
class Solution:
    def longestSubarrayWithSumK(self, 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)
        
        return max_len
class Solution {
    int longestSubarrayWithSumK(int[] arr, int k) {
        int n = arr.length;
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            long sum = 0;
            for (int j = i; j < n; j++) {
                sum += arr[j];
                if (sum == k) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }
        
        return maxLen;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times, and for each starting index, the inner loop runs up to n times. Total iterations: n + (n-1) + ... + 1 = n(n+1)/2, which is O(n²).

Space Complexity: O(1)

We only use a few variables (maxLen, sum, loop counters). No additional data structures.

Why This Approach Is Not Efficient

With n up to 10^5, the brute force performs approximately 5 × 10^9 operations — well beyond the ~10^8 operations per second typical limit. It will time out for large inputs.

The fundamental inefficiency: for every starting index, we re-compute the subarray sum from scratch by scanning forward. We're doing redundant work because we don't remember the cumulative sums we've already computed.

Key insight — Prefix Sums: If we precompute the prefix sum array, then the sum of any subarray arr[i..j] can be computed in O(1) as prefix[j+1] - prefix[i]. But even with prefix sums, naively checking all pairs is still O(n²).

The breakthrough: If prefixSum[j] - prefixSum[i] = k, then prefixSum[i] = prefixSum[j] - k. So as we compute prefix sums left to right, we can use a hash map to check if we've previously seen a prefix sum equal to currentPrefixSum - k. If yes, the subarray between that earlier index and the current index sums to exactly k. This reduces the lookup from O(n) to O(1), giving us an overall O(n) solution.

Optimal Approach - Prefix Sum with Hash Map

Intuition

This approach is built on a powerful mathematical observation about prefix sums.

Define prefixSum[j] = sum of arr[0] through arr[j]. The sum of any subarray from index i+1 to j is:

sum(arr[i+1..j]) = prefixSum[j] - prefixSum[i]

We want this to equal k:

prefixSum[j] - prefixSum[i] = k
prefixSum[i] = prefixSum[j] - k

So the question becomes: as we compute prefix sums left to right, have we previously seen a prefix sum equal to currentSum - k?

If yes, then the subarray from that earlier position to the current position sums to exactly k.

We store prefix sums in a hash map: {prefixSum → earliest index where this sum occurred}. We store the earliest index because we want the longest subarray. If the same prefix sum occurs at index 2 and index 7, using index 2 as the start gives a longer subarray than index 7.

Critical edge case: We initialize the map with {0: -1}, meaning "a prefix sum of 0 was seen at the virtual index -1". This handles the case where the subarray starting from index 0 sums to k (i.e., prefixSum[j] - 0 = k).

Why sliding window fails here: Sliding window requires that adding elements increases the sum and removing decreases it (monotonic property). With negative numbers, this property breaks — adding an element can decrease the sum, making it impossible to decide whether to shrink or expand the window.

Step-by-Step Explanation

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

Initialize: prefixSum = 0, map = {0: -1}, maxLen = 0.

Step 1 (index 0): prefixSum = 0 + 1 = 1.

  • Need = 1 - 3 = -2. Is -2 in map? No.
  • Store {1: 0} in map.
  • Map: {0: -1, 1: 0}

Step 2 (index 1): prefixSum = 1 + (-1) = 0.

  • Need = 0 - 3 = -3. Is -3 in map? No.
  • Is 0 already in map? Yes (at index -1). Do NOT overwrite — keep the earliest index.
  • Map: {0: -1, 1: 0}

Step 3 (index 2): prefixSum = 0 + 5 = 5.

  • Need = 5 - 3 = 2. Is 2 in map? No.
  • Store {5: 2} in map.
  • Map: {0: -1, 1: 0, 5: 2}

Step 4 (index 3): prefixSum = 5 + (-2) = 3.

  • Need = 3 - 3 = 0. Is 0 in map? YES, at index -1!
  • Subarray from index (-1+1)=0 to index 3, length = 3 - (-1) = 4.
  • maxLen = max(0, 4) = 4.
  • Store {3: 3} in map.
  • Map: {0: -1, 1: 0, 5: 2, 3: 3}

Step 5 (index 4): prefixSum = 3 + 3 = 6.

  • Need = 6 - 3 = 3. Is 3 in map? YES, at index 3!
  • Subarray from index (3+1)=4 to index 4, length = 4 - 3 = 1.
  • maxLen = max(4, 1) = 4 (no update).
  • Store {6: 4} in map.

Result: maxLen = 4. The longest subarray with sum 3 is [1, -1, 5, -2] (indices 0-3).

Prefix Sum + Hash Map — O(1) Subarray Sum Lookup — Watch how we build a prefix sum while scanning left to right, using a hash map to instantly check if any earlier prefix sum creates a subarray summing to k.

Algorithm

  1. Initialize prefixSum = 0, maxLen = 0, hash map prefixMap = {0: -1}
  2. For each index i from 0 to n-1:
    a. Add arr[i] to prefixSum
    b. Compute need = prefixSum - k
    c. If need exists in prefixMap:
    • length = i - prefixMap[need]
    • Update maxLen = max(maxLen, length)
      d. If prefixSum is NOT already in prefixMap:
    • Store prefixMap[prefixSum] = i (keep earliest occurrence)
  3. Return maxLen

Important: Only store the prefix sum if it hasn't been seen before. Storing the earliest index ensures we get the longest subarray.

Code

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

class Solution {
public:
    int longestSubarrayWithSumK(vector<int>& arr, int k) {
        int n = arr.size();
        unordered_map<long long, int> prefixMap;
        prefixMap[0] = -1; // prefix sum 0 at virtual index -1
        
        long long prefixSum = 0;
        int maxLen = 0;
        
        for (int i = 0; i < n; i++) {
            prefixSum += arr[i];
            
            // Check if (prefixSum - k) was seen before
            long long need = prefixSum - k;
            if (prefixMap.count(need)) {
                maxLen = max(maxLen, i - prefixMap[need]);
            }
            
            // Store prefix sum only if not already present
            // (keeping earliest index for longest subarray)
            if (!prefixMap.count(prefixSum)) {
                prefixMap[prefixSum] = i;
            }
        }
        
        return maxLen;
    }
};
class Solution:
    def longestSubarrayWithSumK(self, arr, k):
        prefix_map = {0: -1}  # prefix sum 0 at virtual index -1
        prefix_sum = 0
        max_len = 0
        
        for i in range(len(arr)):
            prefix_sum += arr[i]
            
            # Check if (prefix_sum - k) was seen before
            need = prefix_sum - k
            if need in prefix_map:
                max_len = max(max_len, i - prefix_map[need])
            
            # Store prefix sum only if not already present
            # (keeping earliest index for longest subarray)
            if prefix_sum not in prefix_map:
                prefix_map[prefix_sum] = i
        
        return max_len
import java.util.HashMap;

class Solution {
    int longestSubarrayWithSumK(int[] arr, int k) {
        HashMap<Long, Integer> prefixMap = new HashMap<>();
        prefixMap.put(0L, -1); // prefix sum 0 at virtual index -1
        
        long prefixSum = 0;
        int maxLen = 0;
        
        for (int i = 0; i < arr.length; i++) {
            prefixSum += arr[i];
            
            // Check if (prefixSum - k) was seen before
            long need = prefixSum - k;
            if (prefixMap.containsKey(need)) {
                maxLen = Math.max(maxLen, i - prefixMap.get(need));
            }
            
            // Store prefix sum only if not already present
            if (!prefixMap.containsKey(prefixSum)) {
                prefixMap.put(prefixSum, i);
            }
        }
        
        return maxLen;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array exactly once. At each index, we perform one hash map lookup and at most one hash map insertion — both O(1) average. Total: n iterations × O(1) work = O(n).

Space Complexity: O(n)

In the worst case, every prefix sum is unique, so the hash map stores n+1 entries (including the initial {0: -1}). This happens when no prefix sum repeats, which is common with arrays containing both positive and negative values.

Why this approach works for negative numbers: Unlike the sliding window technique (which only works for positive-only arrays), the prefix sum + hash map approach makes no assumptions about the sign of elements. The mathematical identity prefixSum[j] - prefixSum[i] = k holds regardless of whether elements are positive, negative, or zero.