Maximum Size Subarray Sum Equals k

medium prefix sum hash map

Problem

Given an array of integers nums and a target k, return the maximum length of a contiguous subarray summing to k.

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

Output4

Subarray [1,-1,5,-2] has length 4 with sum 3.

nums (comma-separated)

def max_subarray_len(nums, k):
    first = {0: -1}
    s = 0; best = 0
    for i, x in enumerate(nums):
        s += x
        if s - k in first:
            best = max(best, i - first[s - k])
        if s not in first:
            first[s] = i
    return best

function maxSubArrayLen(nums, k) {
  const first = new Map(); first.set(0, -1);
  let s = 0, best = 0;
  for (let i = 0; i < nums.length; i++) {
    s += nums[i];
    if (first.has(s - k)) best = Math.max(best, i - first.get(s - k));
    if (!first.has(s)) first.set(s, i);
  }
  return best;
}

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map first = new HashMap<>();
        first.put(0, -1);
        int s = 0, best = 0;
        for (int i = 0; i < nums.length; i++) {
            s += nums[i];
            if (first.containsKey(s - k)) best = Math.max(best, i - first.get(s - k));
            first.putIfAbsent(s, i);
        }
        return best;
    }
}

int maxSubArrayLen(vector& nums, int k) {
    unordered_map first; first[0] = -1;
    int s = 0, best = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        s += nums[i];
        if (first.count(s - k)) best = max(best, i - first[s - k]);
        if (!first.count(s)) first[s] = i;
    }
    return best;
}

Explanation

The sum of a subarray from index a+1 to i equals prefix[i] - prefix[a], where prefix is the running total. So a subarray sums to k exactly when prefix[i] - prefix[a] = k, i.e. when some earlier prefix equals prefix[i] - k. This is the prefix sum trick.

We stream through the array keeping a running sum s. At each index we check the map first for the value s - k; if it was seen at some earlier index j, the subarray after j up to here sums to k and has length i - j.

To make the subarray as long as possible, we want the earliest index where each prefix sum appeared. So we only record a sum the first time we meet it, using if s not in first. We also seed first[0] = -1 so subarrays starting at index 0 are handled.

Example: nums = [1,-1,5,-2,3], k = 3. Prefix sums are 1, 0, 5, 3, 6. At the value 6 we look for 6 - 3 = 3... but earlier, at prefix 3 (index 3) we look for 0, first seen at index -1, giving length 4 for [1,-1,5,-2]. The answer is 4.

Each lookup and insert is constant time, so the whole scan is linear.

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