DATA STRUCTURES • ALGORITHMS

Longest Subarray with Sum K

Given an array, find the maximum length of a contiguous subarray whose elements sum to exactly K.

Time

O(N)

Space

O(N) (for Hashmap)

Key Principle 1

Prefix Sum technique

Key Principle 2

Hashmap stores (sum, first_occurrence_index)

Key Principle 3

Handle negatives by storing sum

Key Principle 4

One-pass optimal solution

SUBARRAY_SUM_K_LAB
ARRAY:
K:
Current Step
Find longest subarray with sum equal to 3.
Playback
Subarray Stats ⠿
PREFIX SUM0
MAX LENGTH0
Prefix Sum Map ⠿
SUMFIRST INDEX
Prefix Logic ⠿
1int maxLen = 0, sum = 0;
2Map<Integer, Integer> map = new HashMap<>();
3for (int i = 0; i < n; i++) {
4    sum += arr[i];
5    if (sum == k) maxLen = i + 1;
6    if (map.containsKey(sum - k))
7        maxLen = max(maxLen, i - map.get(sum - k));
8    if (!map.containsKey(sum)) map.put(sum, i);
9}
10return maxLen;
1
[0]
2
[1]
3
[2]
1
[3]
1
[4]
1
[5]
1
[6]
4
[7]
2
[8]

Loading Lab...

Longest Subarray Sum K

Longest Subarray Sum K

Longest Subarray with Sum K

Longest Subarray with Sum K