Longest Subarray With Sum Equal to K

Medium20–25 min

Topics

ArrayPrefix SumHash Table

Companies

AmazonMicrosoftGoogleFlipkart

Given an array of integers nums (which may include negative numbers) and an integer k, find the length of the longest contiguous subarray whose elements sum to exactly k. Return 0 if no such subarray exists. Checking every window works, but re-summing from scratch for every (start, end) pair wastes the fact that a running total only changes by one element at a time. The prefix sum technique turns this into a single pass: if two prefixes differ by exactly k, the subarray between them sums to k — and a hash map that remembers the first index each prefix sum was seen at finds the longest such subarray in O(n).

Test Case 1:

Input:nums = [10, 5, 2, 7, 1, -10], k = 15

Output:6

Explanation:The whole array sums to 15 (10+5+2+7+1-10=15), so the longest match is the entire array.

Test Case 2:

Input:nums = [-5, 8, -14, 2, 4, 12], k = -5

Output:5

Explanation:The subarray [8, -14, 2, 4, 12] (indices 1-5) sums to -5.

Test Case 3:

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

Output:0

Explanation:No subarray sums to 100, so the answer is 0.

Constraints

◆1 ≤ nums.length ≤ 10⁵
◆-10⁴ ≤ nums[i] ≤ 10⁴
◆-10⁹ ≤ k ≤ 10⁹

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 3-10 integers, -20 to 20k (target sum)

1	class Solution {
2	public int longestSubarrayWithSumK(int[] nums, int k) {
3	Map<Integer, Integer> firstIndex = new HashMap<>();
4	firstIndex.put(0, -1);
5	int sum = 0, maxLen = 0;
6	for (int i = 0; i < nums.length; i++) {
7	sum += nums[i];
8	if (firstIndex.containsKey(sum - k)) {
9	maxLen = Math.max(maxLen, i - firstIndex.get(sum - k));
10	}
11	firstIndex.putIfAbsent(sum, i);
12	}
13	return maxLen;
14	}
15	}
16

Array

-10

HashMap

0→-1

Variables

sum0

maxLen0

INITIALIZE

Seed the map with prefix sum 0 at index -1 — the empty prefix, before the array starts. This lets a match that begins at index 0 be found too.

Step 1 / 20

Approach & Solutions

Brute Force

Brute

For every possible start index, extend forward one element at a time and keep a running sum. Whenever that running sum equals k, record the window's length as a candidate. Because the array can contain negative numbers, a running sum that overshoots k can still come back down to k later — so every (start, end) pair has to be checked, with no early exit.

TimeO(n²)

SpaceO(1)

Java

Try it out

class Solution {
    public int longestSubarrayWithSumK(int[] nums, int k) {
        int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum == k) {
                    maxLen = Math.max(maxLen, j - i + 1);
                }
            }
        }
        return maxLen;
    }
}

Optimal — Prefix Sum + Hash Map

Optimal

Track a running prefix sum while walking the array once, and remember the FIRST index at which every prefix-sum value was seen (seed the map with prefix sum 0 at index -1, for a match that starts at index 0). At each index i, if sum - k has been seen before, the subarray between that earlier index and i sums to exactly k — and since only the first occurrence of each prefix sum is kept, that gives the longest possible such subarray ending at i.

TimeO(n)

SpaceO(n)