Get started

Maximum Size Subarray Sum Equals k — Medium Problem & Solution

Given an array nums that may contain negative numbers and an integer k, return the length of the longest contiguous subarray whose sum equals k.

Problem statement

Given an array nums that may contain negative numbers and an integer k, return the length of the longest contiguous subarray whose sum equals k.

If no such subarray exists, return 0.

Example 1

Input: nums = [1,-1,5,-2,3], k = 3
Output: 4
Explanation: [1,-1,5,-2] sums to 3 and is the longest such subarray.

Example 2

Input: nums = [-2,-1,2,1], k = 1
Output: 2
Explanation: [-1,2] sums to 1.

Example 3

Input: nums = [1,2,3], k = 100
Output: 0

Constraints

  • 1 <= nums.length <= 200000
  • -10000 <= nums[i] <= 10000
  • -1000000000 <= k <= 1000000000

How to solve Maximum Size Subarray Sum Equals k

With prefix sums, a subarray summing to k is a pair of prefixes differing by k. Recording the earliest index for each prefix value turns 'longest' into a single lookup per position.

Approach

  1. Seed the map with prefix sum 0 at index -1, representing the empty prefix.
  2. Sweep the array keeping the running sum.
  3. Look up sum - k; if present, the subarray after that index sums to k, giving a candidate length of i - first[sum - k].
  4. Record sum at index i only if it has not been seen before.

Why it works

For a fixed right end, the longest qualifying subarray starts at the leftmost prefix with the required value — which is exactly what 'never overwrite' preserves. The -1 seed makes subarrays starting at index 0 reachable.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Overwriting the stored index yields the shortest such subarray, not the longest.
  • Omitting the {0: -1} seed misses every subarray that starts at the beginning.
  • A sliding window is wrong here: negative values break the monotonicity it depends on.

Reference solution

Python

from typing import List

def maxSubArrayLen(nums: List[int], k: int) -> int:
    first = {0: -1}
    total = 0
    best = 0
    for i, x in enumerate(nums):
        total += x
        if total - k in first:
            best = max(best, i - first[total - k])
        if total not in first:
            first[total] = i
    return best

JavaScript

var maxSubArrayLen = function(nums, k) {
    var first = {};
    first["0"] = -1;
    var sum = 0, best = 0;
    for (var i = 0; i < nums.length; i++) {
        sum += nums[i];
        var want = String(sum - k);
        if (first[want] !== undefined && i - first[want] > best) best = i - first[want];
        var own = String(sum);
        if (first[own] === undefined) first[own] = i;
    }
    return best;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue