Longest Subarray with Sum K

You are given an integer array arr — it may contain positives, negatives, and zeros — and an integer k.

Find the length of the longest subarray whose elements sum to exactly k. A subarray is a contiguous block of the array.

If no subarray sums to k, return 0.

Hints

· Stuck? Reveal one nudge at a time.

A subarray is defined by where it starts and where it ends. What single quantity, computed once left to right, gives you any subarray's sum in O(1)?

If the running total up to index j is S, then a subarray ending at j sums to k exactly when some earlier running total equals S - k.

Store each prefix sum's earliest index in a hash map, seeded with 0 -> -1. At each index look up sum - k; the index gap is a candidate length.

Common doubts

Sliding windows need the invariant grow → sum rises, shrink → sum falls, which only holds when all elements are non-negative. With negatives, growing the window can make the sum drop, so there is no correct rule for when to expand or shrink — the window silently skips valid answers.

We want the longest subarray. For a fixed prefix sum value, the earliest index maximizes the gap i - first[s - k]. Overwriting with a later index can only shorten future answers.

It represents the empty prefix before the array starts. Without it, any subarray beginning at index 0 (where prefix[j] itself equals k) is never detected — arr = [15], k = 15 would wrongly return 0.

No — the same logic works. A zero-sum subarray appears exactly when a prefix sum value repeats, and the earliest-occurrence map captures that automatically.

Interview follow-ups

· What an interviewer asks next.

Same prefix-sum idea, but the map stores how many times each prefix sum has occurred instead of its earliest index. At each step add count[s - k] to the answer, then increment count[s] — still one pass, O(n).

Yes — with non-negative elements the running sum is monotonic, so a two-pointer sliding window works in O(n) time and O(1) space: extend the right end, shrink from the left while the sum exceeds k.

Replace every 0 with -1; now you need the longest subarray with sum 0 — this exact algorithm with k = 0.

Fun facts

The prefix-sum + hash-map trick collapses a question about pairs of positions (n²/2 candidates) into n single-value lookups — a dimensionality drop that powers a whole family of subarray problems.
One skeleton, many disguises: set k = 0 and you detect zero-sum stretches; map 0 → -1 in a binary array and you solve the longest balanced run of 0s and 1s; swap earliest-index for a counter and you count subarrays instead of measuring them.

Asked at

AmazonGoogleMicrosoftAdobe

Frequently Sometimes Occasionally

Example 1

Input: arr = [10, 5, 2, 7, 1, -10], k = 15
Output: 6
Three subarrays sum to 15: [10, 5], [5, 2, 7, 1], and the whole array [10, 5, 2, 7, 1, -10]. The longest has length 6.

Example 2

Input: arr = [-5, 8, -14, 2, 4, 12], k = -5
Output: 5
[-5] and [-5, 8, -14, 2, 4] both sum to -5. The longest has length 5.

Example 3

Input: arr = [10, -10, 20, 30], k = 5
Output: 0
No subarray sums to 5, so the answer is 0.

Constraints

- 1 <= arr.size <= 10^5 - -10^4 <= arr[i] <= 10^4 - -10^9 <= k <= 10^9

A nested loop can enumerate every subarray, but with n up to 10^5 you need to look them up instead. The idea that gets you there — a subarray sum is the difference of two prefix sums — is one of the most reused tricks in interviews, and this problem (negatives included, so no sliding window) is its purest form.

Prerequisites

Before you start

· Concepts used directly in the solution.

Prefix sums. The running total prefix[j] = arr[0] + … + arr[j] turns any subarray sum into a difference: sum(i..j) = prefix[j] - prefix[i-1].

Hash maps. Average O(1) insert and lookup — used here to ask, in constant time, whether a prefix sum has appeared before and where it appeared first.

Subarray vs subsequence. A subarray is contiguous; a subsequence can skip elements. This problem is strictly about contiguous runs.

Understand the problem

In plain words: find the longest contiguous run of elements adding up to exactly k; if none exists, answer 0.

Formally: return the maximum j - i + 1 over all pairs 0 ≤ i ≤ j < n with arr[i] + arr[i+1] + … + arr[j] = k, or 0 if no such pair exists.

Worked example — arr = [10, 5, 2, 7, 1, -10], k = 15

index:    -1     0     1     2     3     4     5
element:        10     5     2     7     1   -10
prefix:    0    10    15    17    24    25    15

prefix[1] - prefix[-1] = 15 - 0  = 15  → arr[0..1], length 2
prefix[4] - prefix[0]  = 25 - 10 = 15  → arr[1..4], length 4
prefix[5] - prefix[-1] = 15 - 0  = 15  → arr[0..5], length 6  ✓

answer: 6

Clarifying questions

Two or three sharp questions before coding show you design for the real input, not the happy path.

Questions to ask first

· Signals seniority before you write a line of code.

Input validity

“Can the array contain negative numbers and zeros?”

Yes — and it changes everything. With negatives the running sum is not monotonic, which rules out the two-pointer sliding window and points straight at prefix sums.

“Can k itself be negative or zero?”

Yes. k = 0 is a classic trap: only prefix sums that repeat produce zero-sum subarrays, which is exactly why the map must keep earliest occurrences.

Edge cases

“What should I return when no subarray sums to k?”

0 — not -1. Confirming the sentinel up front avoids a silent wrong answer.

“Can a single element be the whole answer?”

Yes — arr = [15], k = 15 must return 1, which is precisely what the 0 → -1 seed in the optimal solution guarantees.

Constraints and scale

“How large can the array get?”

Up to 10^5 elements — O(n²) means roughly 5 × 10⁹ pair checks and will time out; aim for a single pass.

“Can the running sum overflow a 32-bit integer?”

The sum itself stays within about ±10⁹, but s - k can reach ±2 × 10⁹ — in fixed-width languages keep the arithmetic in 64 bits.

The ideal opening — say it like this

Before I code — can the array contain negatives and zeros, and can k be negative too?

If no subarray sums to k, I will return 0 — is that the expected sentinel?

Since negatives break the sliding window, I will use prefix sums with a hash map of earliest occurrences for a single O of n pass.

Key observations

1Aha

A subarray sum is the difference of two prefix sums

Let prefix[j] be the sum of the first j + 1 elements, with prefix[-1] = 0. Then

sum(arr[i..j]) = prefix[j] - prefix[i-1]

So sum(arr[i..j]) = k exactly when prefix[i-1] = prefix[j] - k. The question at every index j is no longer which subarray ends here? but simply: has the value prefix[j] - k appeared before? A hash map answers that in O(1).

2Aha

Longest gap needs the earliest occurrence — record each sum once

Several indices can share the same prefix sum (only possible thanks to negatives and zeros). To maximize j - i, you want i as small as possible — so store each prefix sum's first index and never overwrite it.

prefix:  0   10   15   17   24   25   15
              ↑    ↑                   ↑
                 first 15         15 again — keep index 1

3Aha

Negatives kill the sliding window

A sliding window relies on the invariant grow the window → sum rises, shrink it → sum falls. With -10 in the array, growing the window can make the sum drop — the window has no valid direction to move, and it silently misses answers like the full length-6 array in example 1. Prefix sums make no monotonicity assumption at all.

Brute force vs optimal

	Brute force	Optimal
Time	O(n²)	O(n)
Space	O(1)	O(n)
Idea	try every (start, end) pair	hash map of earliest prefix sums

Full code for both approaches is in the Approaches selector below.

Summary

Key takeaway

A target-sum subarray is two prefix sums that differ by k. One pass, a hash map of each prefix sum's earliest index, and the answer is the widest such pair. This pattern reappears anywhere a contiguous range must hit an exact aggregate — counting subarrays with sum k, longest stretch of equal 0s and 1s, and beyond.

first = {0: -1}                  # prefix sum → earliest index
s = 0, best = 0
for i in 0..n-1:
    s += arr[i]
    if (s - k) in first: best = max(best, i - first[s - k])
    if s not in first:   first[s] = i
return best