Subarray Sum Equals K | DSA & Design, Connected

Picture

For [2, −1, 1], the running totals at the four boundaries are 0, 2, 1, 2. A stretch is what remains after subtracting an earlier total from a later one. This works even when negative numbers break the simple window rule.

Predict

At current total s, which earlier total would make the intervening stretch sum to k?

Walk through the small example

s − k. Each earlier occurrence is a different starting boundary. For k=2, both later totals of 2 can pair with the initial 0.

Mental model and complete Python solution

Imagine folding the prefix before the stretch out of the total. Algebra says current − earlier = k, so earlier = current − k. The dictionary answers how many folds work. Seed the empty prefix with frequency one, and query before recording the current prefix; otherwise k=0 could count an empty stretch. After each iteration the map contains exactly the boundaries seen so far.

What the function promises: Return the number of nonempty contiguous subarrays summing to k. Values and k may be negative; an empty input returns zero.

def count_subarrays(nums, k):
    frequency = {0: 1}
    total = answer = 0
    for value in nums:
        total += value
        answer += frequency.get(total - k, 0)
        frequency[total] = frequency.get(total, 0) + 1
    return answer

assert count_subarrays([2, -1, 1], 2) == 2
assert count_subarrays([0, 0], 0) == 3
assert count_subarrays([], 0) == 0

Work and storage: Expected O(n) time and O(n) space under ordinary hash-table assumptions. Frequencies, not a set, preserve multiple possible starts.

When to recognize it: A stretch is the difference between two running totals. Count earlier totals equal to current − k.

Check before applying it: A sliding window cannot decide which way to move when negatives can reverse the sum. Store frequencies, not just whether a total appeared.

Change one rule

The question asks only for the longest such stretch, not the count. What changes?

See what changes

Keep the earliest position for each prefix total. That earliest boundary gives the longest ending stretch; adding frequencies answers the wrong objective.

Connect

windows: Compare the nonnegative guarantee that made a window safe.

Word Break: A string boundary can also become a useful state.

Problem reference: Subarray Sum Equals K (Medium). The walkthrough and Python solution above are original course material.