Maximum Size Subarray Sum Equals k

1. Define the problem

Maximum Size Subarray Sum Equals k

Given an integer array nums and an integer k, find the maximum length of a contiguous subarray that sums to exactly k . If no such subarray exists, return 0. Track the first index each running sum was seen. At every index, if sum - k has occurred before, the distance back to its first occurrence is a candidate length — the earliest occurrence always gives the longest subarray.

Constraints

1 ≤ nums.length ≤ 2 × 10⁵
-10⁴ ≤ nums_i ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹

Example

Inputnums = [1, -1, 5, -2, 3], k = 3

Output4

Explanation nums[0..3] = [1, -1, 5, -2] sums to 3 and has length 4, the longest such subarray.

2. Visualize the solution

Keep the earliest place each running sum was seen

p00

p1—

p2—

p3—

p4—

p5—

Statusstart · maxLen: 0

p0 = 0 is the running sum before the array starts. Every other cell is still blank.

What happens in this step

nums = [1, -1, 5, -2, 3], k = 3

p0 = 0

The padded first cell matters: it lets a subarray that starts at index 0
be measured the same way as any other one. In code this is the map entry
firstIndex = {0: -1} — the sum 0 was already "seen" before the array began.

firstIndex = {0: -1}   maxLen = 0

Step 1 of 5

Steps to visualize

The row is the padded prefix array for nums = [1, -1, 5, -2, 3]. p0 is 0, the running sum before the array starts, and p_j is the sum of the first j values. Cells fill in as you walk the array; — means not computed yet.
Because p_j - p_i is the sum of the values between those two cells, the gap between two cells is exactly the length of the subarray they bracket.
At each new cell, look for an earlier cell holding the current sum minus k. If one exists, the gap between them is a candidate length.
Only record a running sum the first time it appears, so later matches reach back as far as possible.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Keep the earliest place each running sum was seen

p00

p1—

p2—

p3—

p4—

p5—

Statusstart · maxLen: 0

p0 = 0 is the running sum before the array starts. Every other cell is still blank.

What happens in this step

nums = [1, -1, 5, -2, 3], k = 3

p0 = 0

The padded first cell matters: it lets a subarray that starts at index 0
be measured the same way as any other one. In code this is the map entry
firstIndex = {0: -1} — the sum 0 was already "seen" before the array began.

firstIndex = {0: -1}   maxLen = 0

Step 1 of 5

4. Solution

Solution

solution.tsTypeScript

function maxSubArrayLen(nums, k) {
  const firstIndex = new Map([[0, -1]]);
  let sum = 0;
  let maxLen = 0;

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i];
    const need = sum - k;

    if (firstIndex.has(need)) {
      maxLen = Math.max(maxLen, i - firstIndex.get(need));
    }
    if (!firstIndex.has(sum)) {
      firstIndex.set(sum, i);
    }
  }

  return maxLen;
}

Time: O(n)
Space: O(n)

5. Test cases

Test cases

Input	Expected	Covers
`nums = [1, -1, 5, -2, 3], k = 3`	`4`	example from the docstring
`nums = [-2, -1, 2, 1], k = 1`	`2`	negative values with the longest match in the middle
`nums = [1, 2, 3], k = 100`	`0`	target unreachable, no subarray sums to k
`nums = [3, 3], k = 6`	`2`	the entire array is the longest matching subarray
`nums = [7], k = 7`	`1`	smallest valid input, a single element equal to k
`nums = [7], k = 3`	`0`	smallest valid input where the element does not match k

Maximum Size Subarray Sum Equals k