AlgoViz
HomeArrays & Hashing

Longest subarray with sum K

Medium

Prefix sums plus a map of first occurrences

Problem

Given an array nums of size n and an integer k, find the length of the longest sub-array that sums to k. If no such sub-array exists, return 0.

In simple words

Track running sums; if an earlier sum equals current minus k, the slice between them totals k.

The idea

A subarray summing to k exists between two positions whose prefix sums differ by k. Store the earliest index at which each prefix sum appeared and look up prefix - k; taking the earliest index is what makes the subarray longest.

The trick

  • Store only the first occurrence of each prefix sum — later ones give shorter subarrays.
  • Seed the map with prefix 0 at index -1 so subarrays starting at 0 are found.
  • Handles negatives, which the sliding-window version cannot.
1
2
1
1
1
0
1
2
3
4
target3

Step 1 of 17. Brute force: check every subarray for the longest one summing to 3. Values: 1, 2, 1, 1, 1. target 3.

1/17
Brute force
timeO(n²)spaceO(1)

Every subarray.

1for (let i = 0; i < n; i++) {2  let sum = 0;3  for (let j = i; j < n; j++) {4    sum += nums[j];5    if (sum === k) best = Math.max(best, j - i + 1);6  }7}

Input

array
[1, 2, 1, 1, 1]

Memory

target
3

Output

best length
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 2, 3, 1, 1, 1, 1], k = 3
Output:
3
Explanation:
[1,1,1] near the end has sum 3 and length 3.

Example 2

Input:
nums = [2, 0, 0, 3], k = 3
Output:
3
Explanation:
Trailing 0s stretch a sum-3 window.

Example 3

Input:
nums = [1, 2, 3], k = 10
Output:
0
Explanation:
No window sums to 10, so length 0.

Constraints

  • 1<=n<=10^5
  • -10^5<=nums[i]<=10^5
  • -10^9<= k<=10^9

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.