{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Subarray Sum Equals K – Solution & Complexity

Interview solutions
/
Subarray Sum Equals K

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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. Step 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?