{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsChat
New
Blog
Ctrl + K

Subarray Sum Equals K – Solution & Complexity

Interview solutions
/
Subarray Sum Equals K

Solution Walkthrough

1. Reframe as prefix sums

  • Let prefix[i] be the sum of the first i elements.
  • The sum of the subarray (i, j] is prefix[j] - prefix[i].
  • We want pairs where that difference equals k.

2. Brute-force every subarray

  • Try every start index and extend a running sum to every end index.
  • Count whenever the running sum hits k. This is O(n^2).
def subarray_sum(nums, k):
    total = 0
    for start in range(len(nums)):
        running = 0
        for end in range(start, len(nums)):
            running += nums[end]
            if running == k:
                total += 1
    return total

3. Count complementary prefixes

  • Walk once, keeping the running prefix sum.
  • For each prefix, the number of valid subarrays ending here equals how many earlier prefixes equalled prefix - k.
  • Seed the map with {0: 1} so subarrays starting at index 0 are counted.

4. One-pass hashmap solution

  • Store how many times each prefix sum has occurred.
  • Add counts[prefix - k] to the answer before recording the current prefix.
def subarray_sum(nums, k):
    counts = {0: 1}
    prefix = 0
    total = 0
    for num in nums:
        prefix += num
        total += counts.get(prefix - k, 0)
        counts[prefix] = counts.get(prefix, 0) + 1
    return total

5. Dry run

Trace nums = [1, 1, 1], k = 2, starting with counts = {0: 1}.

numprefixprefix - kaddedcounts
11-10{0:1, 1:1}
1201{0:1, 1:1, 2:1}
1311{0:1, 1:1, 2:1, 3:1}

Total = 2.

6. Final solution and complexity

The prefix-sum hashmap counts every qualifying subarray in O(n) time and O(n) extra space.

def subarray_sum(nums: list[int], k: int) -> int:
    counts = {0: 1}
    prefix = 0
    total = 0
    for num in nums:
        prefix += num
        total += counts.get(prefix - k, 0)
        counts[prefix] = counts.get(prefix, 0) + 1
    return total

FAQ

See also

Practice Subarray Sum Equals K online (run code in the browser)3Sum solution (medium)Contains Duplicate solution (easy)Group Anagrams solution (medium)Longest Consecutive Sequence solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?