Longest Subarray with Sum K
A medium Arrays interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Arrays
- Sheets
- 2
- Core for
- 26 roles
The problem
Find the length of the longest contiguous subarray whose elements sum to a given value k.
Example 1
- Input
- [1,-1,5,-2,3], k=3
- Output
- 4
Example 2
- Input
- [-2,-1,2,1], k=1
- Output
- 2
Example 3
- Input
- [1,2,3], k=6
- Output
- 3
Constraints
- 1 <= n <= 10^5
- -10^4 <= arr[i] <= 10^4
- -10^9 <= k <= 10^9
How to think about it
Updated 2026-09-29To maximize span length (j - i), any prefix sum equal to currentSum - k should have occurred as early as possible. Storing only the very first index at which each prefix sum was observed ensures that any future match immediately pairs with its furthest left anchor, yielding the maximum possible subarray length.
Approaches, worst first
Quadratic range search
time O(n^2) · space O(1)
Examine all pairs (i, j) with i <= j, summing elements from i to j. If the range sum equals k, update max length with j - i + 1. Correct but requires quadratic operations, timing out for arrays of 10^5 elements.
First-occurrence prefix mapWrite this one
time O(n) · space O(n)
Track running sum. If running sum is k, length is i + 1. If running sum - k exists in map, length candidate is i - map[runningSum - k]. Only record running sum in map if it is not already present, preserving its earliest appearance.
Where people lose marks · 3
- Overwriting earlier index entries in the hash map when a prefix sum repeats: doing so shortens subsequent subarray spans instead of keeping the earliest anchor.
- Using a two-pointer sliding window: negative array values cause running sums to fluctuate non-monotonically, breaking sliding window invariants.
- Forgetting to check if running sum itself equals k, which misses full prefixes starting at index 0 unless handled via an initial `{0: -1}` map seed.
The theory behind it
Arrays — the ground this problem stands on. All Arrays problems
What Arrays is
An array is a row of fixed boxes laid side by side in computer memory, like numbered lockers in a hallway. Because each box occupies identical space and sits directly next to its neighbors, jumping to locker zero or locker ten thousand takes the exact same tiny fraction of time. Every box holds an item of the same type, addressed by an offset number called an index.
When to reach for it
Reach for an array when items arrive in a known sequence and need immediate retrieval by position number. Problems asking for running totals, prefix accumulations, cyclic rotations, or in-place rearrangements signal array mechanics. Whenever constraints require constant-time random lookups or contiguous cache scans across fixed collections, a flat sequence is the default container.
How the pattern works
Visualize a tape with zero-indexed slots stretching from start to end. Keep track of write and read cursors when modifying contents without allocating helper buffers. For running computations, maintain an invariant such as having processed all elements left of the current index while pending elements wait to the right. When modifying entries in place, consider scanning backwards from the end so unread data is not overwritten.
More Arrays problems
Target Roles
Core requirement for 26 roles:
Asked at
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .