TechPrep
Arrays and stringsReadLabPracticeCheck

Prefix sums

Precompute running totals so any range sum is one subtraction, and pair them with a hash map to count ranges.

Subarray Sum Equals K. Count the contiguous subarrays of nums whose sum is exactly k. Values may be negative.

Signals that point here

The idea

Let P[j] be the sum of the first j elements. The subarray from i to j - 1 sums to P[j] - P[i]. So a subarray ending here sums to k exactly when some earlier prefix equals prefix - k.

Counting how many earlier prefixes had each value turns the search into a lookup. The sliding window fails here because negative numbers break monotonicity; this does not care.

def count_subarrays(nums: list[int], k: int) -> int:
    seen = {0: 1}                    # prefix value -> how many times seen
    prefix = count = 0
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

Complexity

O(n) time and O(n) space. A plain prefix array for range queries is O(n) to build and O(1) per query.

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: count_subarrays([3, 4, -7, 1, 3], 7)

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. Count subarrays whose sum is divisible by k.
  2. Find the longest subarray with equal numbers of 0s and 1s.
  3. Answer many sub-rectangle sum queries on a matrix in O(1) each.

Check yourself

What identity does the pattern rest on?

The sum of nums[i..j-1] equals P[j] - P[i].

Why does a sliding window fail on this problem?

Negative values mean growing a window can lower its sum, so the window condition is not monotone.

Saved in this browser.