Coding interview problems › Arrays & Hashing

#️⃣ Arrays & Hashing Medium

Subarray Sum Equals K

Subarray Sum Equals K explained: prefix sums plus a hash map of counts count every subarray summing to k in O(n), even with negatives. Tested Python.

Also searched as: count subarrays with sum k · prefix sum hash map · number of subarrays with given sum

📈

Try it live Free

Prefix Sums & Kadane

Watch the prefix-sum array build up and see a range sum become one subtraction of two prefix values. This problem flips that around: it looks up the matching earlier prefix in a hash map instead of subtracting.

Also useful: Hash Tables

Open the playground →

The problem

Given a list of integers nums (which may include negatives and zeros) and an integer k, count how many contiguous subarrays have a sum exactly equal to k.

Inputnums = [1, 1, 1], k = 2
Output2

[1,1] at positions 0-1 and 1-2.

Inputnums = [1, 2, 3], k = 3
Output2

[1,2] and [3].

The key insight

The sum of a subarray from i+1 to j is prefix[j] - prefix[i]. So a subarray ending at j sums to k exactly when some earlier prefix equals prefix[j] - k. Keep a hash map counting how often each prefix sum has occurred, and add that count at every step.

Brute force first: Trying every start and end and summing is O(n²) even with a running sum.

Step-by-step approach

  1. Start with counts = {0: 1}: the empty prefix, so subarrays starting at index 0 are counted.
  2. Walk the list keeping a running prefix sum s.
  3. Add counts.get(s - k, 0) to the answer: that many earlier prefixes make a subarray ending here with sum k.
  4. Then record the current prefix with counts[s] += 1.
  5. Return the total.

Python solution

PYTHON 3tested
def subarray_sum(nums, k):
    counts = {0: 1}                # prefix sum -> how many times seen
    s = total = 0
    for x in nums:
        s += x
        total += counts.get(s - k, 0)
        counts[s] = counts.get(s, 0) + 1
    return total

Complexity

TimeO(n)
SpaceO(n)

One pass with O(1) average dictionary work per element. The map stores up to n + 1 distinct prefix sums.

Common mistakes

Frequently asked questions

What is the time and space complexity of Subarray Sum Equals K?

The prefix sum plus hash map solution is O(n) time and O(n) space. The brute force over all start and end pairs is O(n²).

Why does a sliding window fail here?

A sliding window assumes that growing the window increases the sum and shrinking decreases it. With negative numbers that is false, so you cannot decide which side to move.

How do I return the subarrays instead of the count?

Store a list of indices for each prefix sum instead of a count, and for each match emit the range from that index plus one to the current index.

What does the initial {0: 1} mean?

It represents the empty prefix before the first element, whose sum is 0. It lets a subarray starting at index 0 be counted when the running sum itself equals k.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Arrays & Hashing Hash Tables lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.