Longest Subarray with Sum K

+10

Given the integers nums and a target k, return the length of the longest subarray whose elements total exactly k. A subarray is a stretch of consecutive elements, at least one long. Some values may be zero or below zero. If no subarray adds up to k, return 0.

Function

longestSubarrayWithSumK(nums: integer-array, k: integer) → integer

numsinteger-array: the integers to search, negatives and zeros included
kinteger: the exact sum the subarray must have
Returnsinteger: the length of the longest subarray that adds up to k, or 0 when none does

Constraints

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹
Every prefix sum stays between -2 × 10⁸ and 2 × 10⁸, so 32-bit integers are enough.
Return 0 when no subarray adds up to k.

Examples

Input: nums = [2, -1, 3, 1, -4, 2, 3]k = 5
Output: 5
Explanation: Three runs add up to 5: [2, 3] at the end, [2, -1, 3, 1] at the start, and [3, 1, -4, 2, 3] at indices 2 to 6. The last is the longest, with 5 elements.

Input: nums = [4, 1, 1, 2, -1, 1]k = 3
Output: 4
Explanation: [1, 1, 2, -1] at indices 1 to 4 and [1, 2, -1, 1] at indices 2 to 5 both add up to 3 with 4 elements. You return a length, so the tie does not matter.

Follow-up

How would you find the longest subarray whose sum is at most k, with negative values still allowed?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Running totals turn any subarray's sum into one subtraction: the elements after index s up to index i add up to prefix[i] - prefix[s]. Remember the first index where each total appears, and one pass finds the longest match ending at every position.

Grow every subarray from each start

Correct, but does not finish on the largest tests

Intuition

From each start, extend to the right and add each element to a running total. Whenever the total equals k, record the length. Every subarray is one pair of start and end, so none is missed. Keep extending after the total passes k: from index 2 in the first example the totals are 3, 4, 0, 2, 5, and the -4 is why the last one reaches 5.

There are about n²/2 pairs: 2 × 10^8 additions for n = 2 × 10^4.

Algorithm

Set best to 0.
For each start, set total to 0.
Move end from start to the last index and add nums[end] to total.
When total equals k, set best to the larger of best and end - start + 1.
Return best.

def longestSubarrayWithSumK(nums, k):
    n = len(nums)
    best = 0
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            # A match may come after the total has passed k, so never stop early
            if total == k and end - start + 1 > best:
                best = end - start + 1
    return best

Prefix sums with the first index of each sum

Intuition

A run ending at index i sums to k exactly when some earlier total equals prefix - k. If several earlier totals qualify, the first one starts the longest run, so the map stores each total only the first time it appears. A later copy could only start a shorter run. Seed the map with total 0 at index -1, so a match that starts at index 0 gets length i + 1.

In the first example the totals are 2, 1, 4, 5, 1, 3, 6. At index 6, 6 - 5 = 1 first appeared at index 1, which gives length 5. Total 1 comes back at index 4, and keeping index 1 is what finds that run.

One lookup per element gives O(n) time, and the map holds at most n + 1 totals.

Algorithm

Create a map first holding total 0 at index -1, and set prefix and best to 0.
For each index i, add nums[i] to prefix.
If prefix - k is in the map at index start, set best to the larger of best and i - start.
If prefix is not in the map yet, store it with index i.
Return best.

def longestSubarrayWithSumK(nums, k):
    # first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
    first = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += num
        # The earliest prefix equal to prefix - k starts the longest match that ends at i
        start = first.get(prefix - k)
        if start is not None and i - start > best:
            best = i - start
        # Keep the first index only: a later one could only start a shorter subarray
        if prefix not in first:
            first[prefix] = i
    return best

Pitfalls and edge cases

Overwriting the stored index each time a total repeats keeps the latest start and finds a shorter match. The first example returns 4 instead of 5, because total 1 moves from index 1 to index 4.
A window that shrinks while its sum is above k also returns 4 on the first example. It ends holding [-1, 3, 1, -4, 2, 3] with sum 4 and never drops the -1.
Leaving out total 0 at index -1 misses every match that starts at index 0: [5, 0, 0, 0] with k = 5 returns 0 instead of 4.
The stored index is the position before the subarray, so the length is i - start. Adding 1 counts one element too many.

Frequently asked questions3

What is the time complexity of Longest Subarray with Sum K?

O(n) time and O(n) extra space with running totals and a map of first indexes: one lookup and at most one insert per element. Growing every subarray from each start costs O(n²) time and O(1) space.

Why does a sliding window fail when the array has negative numbers?

A sliding window assumes that adding an element raises the sum and removing one lowers it. With negative values, a window whose sum is too big can still reach k once a negative element arrives, and one whose sum is too small may need to drop a negative element on its left. The window cannot tell which move is right.

Can Longest Subarray with Sum K be solved in O(1) extra space?

Only when no value is negative. Then the sum never drops as the window grows, and two pointers find the longest window with sum k in O(n) time and O(1) space. With negative values you need the map of totals, or the O(n²) scan.

def longestSubarrayWithSumK(nums, k):
    # Write code here

Test #1

Test #2

Test #3

Arguments

nums = [2, -1, 3, 1, -4, 2, 3]
k = 5

Expected Output