Maximum Size Subarray Sum Equals k

Medium
672.

Maximum Size Subarray Sum Equals k

Maximum Size Subarray Sum Equals k is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon, Microsoft, Meta and Palantir interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxSubArrayLen = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Size Subarray Sum Equals k — Problem & Solution

Maximum Size Subarray Sum Equals k solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximum Size Subarray Sum Equals k is a medium coding problem on arrays, hash table and prefix sum, asked in Amazon, Microsoft, Meta and Palantir interviews.

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

Hints for Maximum Size Subarray Sum Equals k

  1. Hint 1

    Negative values rule out a sliding window — use prefix sums instead.

  2. Hint 2

    nums[i+1..j] sums to k exactly when P[j] - P[i] == k, so look up P[j] - k.

  3. Hint 3

    Keep only the first index at which each prefix sum appears; that maximises the distance.

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

Java

public static int maxSubArrayLen(int[] nums, int k) {
    Map<Long, Integer> first = new HashMap<>();
    first.put(0L, -1);
    long sum = 0;
    int best = 0;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        Integer at = first.get(sum - k);
        if (at != null && i - at > best) best = i - at;
        if (!first.containsKey(sum)) first.put(sum, i);
    }
    return best;
}

C++

int maxSubArrayLen(vector<int>& nums, int k) {
    unordered_map<long long, int> first;
    first[0] = -1;
    long long sum = 0;
    int best = 0;
    for (int i = 0; i < (int) nums.size(); i++) {
        sum += nums[i];
        auto it = first.find(sum - k);
        if (it != first.end() && i - it->second > best) best = i - it->second;
        if (!first.count(sum)) first[sum] = 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets