Longest Subarray With Sum K: Prefix Sums, First Index Only

You're given an integer array nums, which may hold negative numbers and zeros, and an integer k, and I'd like you to return the length of the longest contiguous subarray whose elements add up to exactly k, or 0 if there isn't one anywhere in the array.

Examples

Input	Output	Why
`nums = [1, -1, 5, -2, 3], k = 3`	`4`	The first four elements add up to 3, and although the [3] at the very end does as well, it's only one element long.
`nums = [-2, -1, 2, 1], k = 1`	`2`	That's [-1, 2] in the middle, which beats the single [1] at the end.
`nums = [1, 2, 3], k = 7`	`0`	Even the whole array only reaches 6, so there is nothing to return but 0.

Constraints

1 ≤ n ≤ 2 × 10⁵
−10⁴ ≤ nums[i] ≤ 10⁴
−10⁹ ≤ k ≤ 10⁹
Values may be negative or zero

Hints

Hint 1

Once there are negative numbers in the array, a sliding window has nothing to steer by, so I'd think about prefix sums in the way you would for counting.

Hint 2

A range ending at j adds up to k whenever some earlier prefix equals P[j] − k, so ask yourself which of those earlier prefixes would give you the longest range.

Hint 3

It's the one with the smallest index, so you want to store the first index where each prefix value turns up, leave it alone afterwards, and start the map off with prefix 0 at index −1.

Where people lose marks

Overwriting the stored index whenever a prefix value repeats, which still runs without complaint and hands you a range that's too short.
Seeding the map with index 0 where it should be −1, so that every range starting at the front of the array comes out one shorter than it really is.
Reaching for a sliding window, which with a negative number in the array will miss ranges and won't tell you that it has.

Dry run on `[1,-1,5,-2,3],3`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 7

Step 1 / 7

nums
10-1152-2334
k3best0first[0]-1
The map starts as {0: −1}, the empty prefix, so a range from index 0 to j has length j + 1.
Step 2 / 7

nums
10j-1152-2334
prefix1want-2best0first[0]-1first[1]0
Take 1: prefix 1. No earlier prefix of -2, so nothing ends here. Store first[1] = 0.
Step 3 / 7

nums
10-11j52-2334
prefix0want-3best0first[0]-1first[1]0
Take -1: prefix 0. No earlier prefix of -3, so nothing ends here. Prefix 0 is already stored, so we keep its first index.
Step 4 / 7

nums
10-1152j-2334
prefix5want2best0first[0]-1first[1]0first[5]2
Take 5: prefix 5. No earlier prefix of 2, so nothing ends here. Store first[5] = 2.
Step 5 / 7

nums
10-1152-23j34
prefix3want0best4first[0]-1first[1]0first[5]2first[3]3
Take -2: prefix 3. That's k itself, so the empty prefix matches and the whole run from index 0, length 4, adds up to 3. Best 4. Store first[3] = 3.
Step 6 / 7

nums
10-1152-2334j
prefix6want3best4first[0]-1first[1]0first[5]2first[3]3first[6]4
Take 3: prefix 6. Prefix 3 first came at 3, length 1, which doesn't beat 4. Store first[6] = 4.
Step 7 / 7

nums
10-1152-2334
best4
One pass. The longest range adding up to 3 has length 4.

How to think about it

You'll usually find this one listed as Maximum Size Subarray Sum Equals k, and I think of it as the counting problem with something different kept in the map.

Write P[j] for the sum of the first j elements. A range that ends at j adds up to k once for every earlier prefix equal to P[j] − k. When we were counting, we needed every one of those, which is why the map held how many times each prefix had come up. Here we only want the longest range, and that always comes from the earliest matching prefix, so the map holds the first index at which each prefix value appeared.

There are two small details that I'd check in any answer to this. We seed the map with prefix 0 at index −1, which stands for the empty prefix, so that a range starting right at index 0 comes out with length j + 1. And when a prefix value comes back later, we leave the old index exactly where it is, because writing the new one over it could only ever make the ranges we find shorter.

If every value in the array were positive, you could get away with a sliding window and constant extra space. It's the negatives and the zeros that push us towards the map, and the map is what costs us O(n) space.

Complexity. Time O(n) · Space O(n)

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def longest_sum_k(nums, k):
    first = {0: -1}              # the empty prefix sits just before index 0
    prefix = best = 0
    for j, x in enumerate(nums):
        prefix += x
        i = first.get(prefix - k)
        if i is not None:
            best = max(best, j - i)
        if prefix not in first:  # keep the earliest index only
            first[prefix] = j
    return best

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

int solve(vector<int> nums, long long k) {
    unordered_map<long long, int> first;
    first[0] = -1;                       // the empty prefix
    long long prefix = 0;
    int best = 0;
    for (int j = 0; j < (int)nums.size(); ++j) {
        prefix += nums[j];
        auto it = first.find(prefix - k);
        if (it != first.end()) best = max(best, j - it->second);
        first.emplace(prefix, j);        // emplace leaves an existing key alone
    }
    return best;
}

import java.util.*;

class Solution {
    public int longestSumK(int[] nums, long k) {
        Map<Long, Integer> first = new HashMap<>();
        first.put(0L, -1);                   // the empty prefix
        long prefix = 0;
        int best = 0;
        for (int j = 0; j < nums.length; j++) {
            prefix += nums[j];
            Integer i = first.get(prefix - k);
            if (i != null) best = Math.max(best, j - i);
            first.putIfAbsent(prefix, j);    // keep the earliest index only
        }
        return best;
    }
}

function longestSumK(nums, k) {
  const first = new Map([[0, -1]]);   // the empty prefix
  let prefix = 0, best = 0;
  for (let j = 0; j < nums.length; j++) {
    prefix += nums[j];
    const i = first.get(prefix - k);
    if (i !== undefined) best = Math.max(best, j - i);
    if (!first.has(prefix)) first.set(prefix, j);   // keep the earliest index only
  }
  return best;
}

use std::collections::HashMap;

fn solve(nums: &[i64], k: i64) -> i64 {
    let mut first: HashMap<i64, i64> = HashMap::new();
    first.insert(0, -1);                 // the empty prefix
    let mut prefix = 0i64;
    let mut best = 0i64;
    for (j, &x) in nums.iter().enumerate() {
        let j = j as i64;
        prefix += x;
        if let Some(&i) = first.get(&(prefix - k)) {
            best = best.max(j - i);
        }
        first.entry(prefix).or_insert(j); // keep the earliest index only
    }
    best
}

import qualified Data.Map.Strict as M

solve :: [Int] -> Int -> Int
solve xs k = go (M.singleton 0 (-1)) 0 0 (zip [0 ..] xs)
  where
    -- carry the map of first indices, the running prefix and the best length so far
    go _ _ best [] = best
    go m p best ((j, x) : rest) =
      let p'    = p + x
          best' = maybe best (\i -> max best (j - i)) (M.lookup (p' - k) m)
          m'    = M.insertWith (\_ old -> old) p' j m
      in go m' p' best' rest

Variants to try

How would you return the shortest such range in place of the longest? (I'd keep the latest index of each prefix and overwrite it every time.)
What about the longest range with equal numbers of 0s and 1s? (Turn every 0 into −1 and look for the longest range that adds up to 0.)
If all of the values are positive, how much extra space do you really need? (A sliding window does the job with O(1) extra space.)

Next problems

Medium20 min

Longest subarray with a given sum

Examples

Constraints

Hints

Where people lose marks

Dry run on `[1,-1,5,-2,3],3`

How to think about it

The solution, in six languages

Variants to try

Next problems

Count subarrays with a given sum

Product of every element except itself

Count subarrays with a sum divisible by k

Keep going

Count subarrays with a given sum

Product of every element except itself

Count subarrays with a sum divisible by k

The pattern behind it

Longest subarray with a given sum

Examples

Constraints

Hints

Where people lose marks

Dry run on [1,-1,5,-2,3],3

How to think about it

The solution, in six languages

Variants to try

Next problems

Count subarrays with a given sum

Product of every element except itself

Count subarrays with a sum divisible by k

Keep going

Count subarrays with a given sum

Product of every element except itself

Count subarrays with a sum divisible by k

The pattern behind it

Dry run on `[1,-1,5,-2,3],3`