Longest subarray with given sum K(positives)

Medium

Sliding window, because all values are positive

Problem

Given an array of positive integers and K, return the length of the longest subarray with sum exactly K.

In simple words

Grow a window while the sum is too small and shrink it when too big — a sliding window.

The idea

With only positive numbers the running sum grows as the window widens and shrinks as it narrows, so a two-pointer window suffices: expand right while the sum is short, shrink left while it overshoots. That monotonicity is exactly what the general prefix-sum version cannot assume.

The trick

Only valid for positive values — a single zero or negative breaks the monotonicity.
Record the length whenever the sum equals k exactly.
O(n): each pointer only moves forward.

←→stepspaceplay

target5

1/23

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: [2, 3, 1, 1, 1, 4]

Memory

target: 5

Output

best length: —
answer: —

Check yourself

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

Examples

Example 1

Input:: nums = [1, 2, 1, 1, 1, 4, 2, 3], k = 5
Output:: 4
Explanation:: [1,1,1,4]? use two pointers; the longest window summing to 5 has length 4 ([2,1,1,1]).

Example 2

Input:: nums = [1, 1, 1, 1], k = 2
Output:: 2
Explanation:: Any two neighbours add to 2.

Example 3

Input:: nums = [3, 1, 1], k = 2
Output:: 2
Explanation:: [1,1] sums to 2.

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

Finished the walkthrough? Add it to your streak.