MediumArrayHash TablePrefix SumUpdated Sep 2026

560. Subarray Sum Equals K

Asked at Google, Meta, Microsoft, Apple and 2 more

Difficulty

Medium

Time

O(n)

Space

O(n)

Pattern

Array

Companies

6

Problem

You are given an integer array nums and an integer k. Count how many subarrays of nums have a sum exactly equal to k.

A subarray is a block of next to each other elements. It must be non-empty. So nums[i..j] counts, but picking elements from different places does not. Two subarrays count as different if they start or end at different positions, even if their values look the same.

Return the total count as an integer.

Which blocks sum to k

numssum 3123012nums[0..1] = [1,2] adds up to 3numssum 3123012nums[2..2] = [3] also adds up to 3, so the answer is 2
For nums = [1,2,3] and k = 3, two blocks hit the target: [1,2] and [3].

Constraints

  • ●1 <= nums.length <= 2 * 10^4
  • ●-1000 <= nums[i] <= 1000
  • ●-10^7 <= k <= 10^7

Examples

Example 1
Inputnums = [1,1,1], k = 2
Output2
WhyThe subarrays that sum to 2 are nums[0..1] = [1,1] and nums[1..2] = [1,1]. The whole array sums to 3, so it does not count.
Example 2
Inputnums = [1,2,3], k = 3
Output2
Whynums[0..1] = [1,2] sums to 3, and nums[2..2] = [3] sums to 3. That is 2 subarrays.

Asked At

6 companies
CompanyDifficulty
GoogleMediumView all Google questions →
MetaMediumView all Meta questions →
MicrosoftMediumView all Microsoft questions →
AppleMediumView all Apple questions →
SalesforceMediumView all Salesforce questions →
VisaMediumView all Visa questions →

How to Think About It

1

Brute force: check every subarray (i to j). Calculate sum in O(n) per subarray. Total: O(n²). Too slow.

2

Key insight: prefix sum. If prefix_sum[j] - prefix_sum[i] == k, then the subarray from i+1 to j sums to k. Store prefix sums in a hash map for O(1) lookup.

3

The formula: for each position j, check if (prefix_sum[j] - k) exists in the map. If yes, there are that many subarrays ending at j that sum to k.

4

Critical edge case: initialize the map with {0: 1}. This handles subarrays that start from index 0. Without it, you miss subarrays where the prefix sum itself equals k.

Optimal Approach

Step 1: Initialize prefix_sum = 0, map = {0: 1}, count = 0.
Step 2: For each num in the array:

  • Add num to prefix_sum
  • Check if (prefix_sum - k) is in the map
    - If yes, add map[prefix_sum - k] to count
    - Increment map[prefix_sum]
    Step 3: Return count.

Why it works: if prefix_sum[j] - prefix_sum[i] == k, the subarray from i+1 to j sums to k. The map stores how many times each prefix sum has occurred.

Time: O(n). Space: O(n).

Prefix sums in a hash map

nums123012jWalk left to right, keeping a running total (prefixsum)map012011131After nums[0..1] the total is 3, and 3 - k = 0 is inthe map, so count grows by 1count += map[total - k]map[total] += 1start with map = {0: 1}
At each step we ask: how many earlier prefix sums equal the current prefix sum minus k?
ComplexityTime O(n)Space O(n)One pass over the array, and the hash map may hold up to n+1 different prefix sums.

What Trips People Up in Real Interviews

1

Confusing "subarray" with "subsequence." A subarray is contiguous. A subsequence can skip elements.

2

Not using prefix sums. The brute force is O(n²). Prefix sums with a hash map give O(n).

3

Forgetting that the prefix sum map needs a count of 0: 1. This handles the case where a subarray starting from index 0 sums to k.

4

Not handling negative numbers. The prefix sum approach works with negatives, but you can't use two pointers (the array isn't sorted).

5

Forgetting that prefix sums can repeat. If the same prefix sum occurs at multiple indices, the map must store COUNTS, not just the most recent index. Missing this undercounts subarrays.

Solution Code

O(n) time
from collections import Counter

def subarraySum(nums, k):
    prefix = Counter()
    prefix[0] = 1
    total = count = 0
    for num in nums:
        total += num
        count += prefix[total - k]
        prefix[total] += 1
    return count

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Subarray Sum Equals K problem?

Given an array of integers and an integer k, count the total number of continuous subarrays whose sum equals k. This problem tests your understanding of prefix sums and `hash map` counting.

How do you solve Subarray Sum Equals K?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Subarray Sum Equals K?

Subarray Sum Equals K is asked at Google, Meta, Microsoft, Apple, Salesforce, Visa. It is a medium difficulty problem.

What are common mistakes on Subarray Sum Equals K?
  • Confusing "subarray" with "subsequence." A subarray is contiguous. A subsequence can skip elements.
  • Not using prefix sums. The brute force is `O(n²)`. Prefix sums with a `hash map` give `O(n)`.
  • Forgetting that the prefix sum map needs a count of 0: 1. This handles the case where a subarray starting from index 0 sums to k.
  • Not handling negative numbers. The prefix sum approach works with negatives, but you can't use two pointers (the array isn't sorted).
  • Forgetting that prefix sums can repeat. If the same prefix sum occurs at multiple indices, the map must store COUNTS, not just the most recent index. Missing this undercounts subarrays.