560. Subarray Sum Equals K (Medium)

Problem

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k.

A subarray is a contiguous non-empty sequence of elements within the array.

Example

nums = [1,1,1], k = 2 → 2 (subarrays [1,1] at index 0-1 and 1-2)
nums = [1,2,3], k = 3 → 2 (subarrays [3] at index 2, and [1,2] at index 0-1)

LeetCode 560 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, check every subarray

Enumerate every start index i and accumulate the sum as we extend j. Reset for each new start.

def subarray_sum(nums: list[int], k: int) -> int:
    count = 0
    n = len(nums)
    for i in range(n):              # L1: outer loop, n iterations
        total = 0
        for j in range(i, n):       # L2: inner loop, n-i iterations
            total += nums[j]         # L3: O(1) accumulate
            if total == k:           # L4: O(1) check
                count += 1           # L5: O(1)
    return count

function subarraySum(nums: number[], k: number): number {
    let count = 0;
    const n = nums.length;
    for (let i = 0; i < n; i++) {         // L1: outer loop, n iterations
        let total = 0;
        for (let j = i; j < n; j++) {     // L2: inner loop, n-i iterations
            total += nums[j];             // L3: O(1) accumulate
            if (total === k) count++;     // L4/L5: O(1) check + increment
        }
    }
    return count;
}

func subarraySum(nums []int, k int) int {
  count := 0
  n := len(nums)
  for i := 0; i < n; i++ {              // L1: outer loop, n iterations
    total := 0
    for j := i; j < n; j++ {         // L2: inner loop, n-i iterations
      total += nums[j]              // L3: O(1) accumulate
      if total == k {              // L4: O(1) check
        count++                  // L5: O(1)
      }
    }
  }
  return count
}

final class Solution {
    func subarraySum(_ nums: [Int], _ k: Int) -> Int {
        var matches = 0
        for start in nums.indices {
            var sum = 0
            for end in start..<nums.count { sum += nums[end]; if sum == k { matches += 1 } }
        }
        return matches
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (outer loop)	$O(1)$	n	$O(n)$
L2, L3, L4 (inner loop)	$O(1)$	n^2 / 2	$O(n^2)$ ← dominates
L5 (increment)	$O(1)$	at most n^2/2	$O(n^2)$

Complexity

Time: $O(n^2)$ , driven by L2/L3/L4 (all pairs of start and end indices).
Space: $O(1)$ .

Approach 2: Prefix sums with a hash map (optimal)

Define prefix[i] = sum of nums[0..i-1]. The sum of subarray nums[i..j] equals prefix[j+1] - prefix[i]. We want this difference to equal k, i.e., prefix[j+1] - k must equal some earlier prefix sum prefix[i].

Scan left to right, maintaining a running prefix sum and a frequency map count of all prefix sums seen so far. Initialize count[0] = 1 to account for subarrays that start at index 0.

from collections import defaultdict

def subarray_sum(nums: list[int], k: int) -> int:
    count = defaultdict(int)      # L1: O(1)
    count[0] = 1                  # L2: O(1), seed for subarrays starting at index 0
    prefix = 0                    # L3: O(1)
    result = 0                    # L4: O(1)
    for x in nums:                # L5: loop, n iterations
        prefix += x               # L6: O(1) extend prefix sum
        result += count[prefix - k]   # L7: O(1) hash lookup: how many times has (prefix-k) appeared?
        count[prefix] += 1        # L8: O(1) record this prefix sum
    return result                 # L9: O(1)

function subarraySum(nums: number[], k: number): number {
    const count = new Map<number, number>();  // L1: O(1)
    count.set(0, 1);                          // L2: O(1), seed for subarrays starting at index 0
    let prefix = 0;                           // L3: O(1)
    let result = 0;                           // L4: O(1)
    for (const x of nums) {                  // L5: loop, n iterations
        prefix += x;                          // L6: O(1) extend prefix sum
        result += count.get(prefix - k) ?? 0; // L7: O(1) map lookup
        count.set(prefix, (count.get(prefix) ?? 0) + 1);  // L8: O(1) record
    }
    return result;
}

func subarraySum(nums []int, k int) int {
  count := make(map[int]int)    // L1: O(1)
  count[0] = 1                  // L2: O(1), seed for subarrays starting at index 0
  prefix := 0                   // L3: O(1)
  result := 0                   // L4: O(1)
  for _, x := range nums {      // L5: loop, n iterations
    prefix += x               // L6: O(1) extend prefix sum
    result += count[prefix-k] // L7: O(1) map lookup
    count[prefix]++           // L8: O(1) record
  }
  return result
}

final class Solution {
    func subarraySum(_ nums: [Int], _ k: Int) -> Int {
        var prefixCounts = [0: 1]
        var prefix = 0, matches = 0
        for number in nums {
            prefix += number
            matches += prefixCounts[prefix - k, default: 0]
            prefixCounts[prefix, default: 0] += 1
        }
        return matches
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1-L4 (init)	$O(1)$	1	$O(1)$
L5 (loop)	$O(1)$ body	n	$O(n)$ ← dominates
L6 (prefix update)	$O(1)$	n	$O(n)$
L7 (hash lookup)	$O(1)$ avg	n	$O(n)$
L8 (hash insert)	$O(1)$ avg	n	$O(n)$
L9 (return)	$O(1)$	1	$O(1)$

Complexity

Time: $O(n)$ , driven by L5-L8 (single pass, all operations $O(1)$ average).
Space: $O(n)$ . The frequency map stores at most n distinct prefix sums.

Why `count[0] = 1`?

If the subarray starting at index 0 sums to k, then prefix - k = 0 at that point. We need count[0] to be 1 so that L7 adds 1 to the result. Without the seed, subarrays that begin at the array’s start would be missed.

Worked example

nums = [1,1,1], k = 2

count = {0: 1}, prefix = 0, result = 0

x=1: prefix=1, result += count[1-2=-1]=0  → result=0, count={0:1, 1:1}
x=1: prefix=2, result += count[2-2=0]=1   → result=1, count={0:1, 1:1, 2:1}
x=1: prefix=3, result += count[3-2=1]=1   → result=2, count={0:1, 1:1, 2:1, 3:1}

return 2

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Brute force	$O(n^2)$	$O(1)$
Prefix sums + hash map	$O(n)$	$O(n)$

Test cases

# Quick smoke tests, paste into a REPL or save as test_560.py and run.

from collections import defaultdict

def subarray_sum(nums: list[int], k: int) -> int:
    count = defaultdict(int)
    count[0] = 1
    prefix = 0
    result = 0
    for x in nums:
        prefix += x
        result += count[prefix - k]
        count[prefix] += 1
    return result

def _run_tests():
    assert subarray_sum([1,1,1], 2) == 2
    assert subarray_sum([1,2,3], 3) == 2
    assert subarray_sum([1], 0) == 0
    assert subarray_sum([1], 1) == 1
    assert subarray_sum([-1,-1,1], 0) == 1
    assert subarray_sum([0,0,0,0], 0) == 10   # C(4,2) + 4 single-element zeros
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function subarraySum(nums: number[], k: number): number {
    const count = new Map<number, number>();
    count.set(0, 1);
    let prefix = 0, result = 0;
    for (const x of nums) {
        prefix += x;
        result += count.get(prefix - k) ?? 0;
        count.set(prefix, (count.get(prefix) ?? 0) + 1);
    }
    return result;
}

console.assert(subarraySum([1, 1, 1], 2) === 2);
console.assert(subarraySum([1, 2, 3], 3) === 2);
console.assert(subarraySum([1], 0) === 0);
console.assert(subarraySum([1], 1) === 1);
console.assert(subarraySum([-1, -1, 1], 0) === 1);
console.assert(subarraySum([0, 0, 0, 0], 0) === 10);
console.log("all tests pass");

func subarraySum(nums []int, k int) int {
  count := make(map[int]int)
  count[0] = 1
  prefix, result := 0, 0
  for _, x := range nums {
    prefix += x
    result += count[prefix-k]
    count[prefix]++
  }
  return result
}

Range Sum Query Immutable, prefix sums for static range queries
Two Sum, same “store what you’ve seen, look up the complement” pattern

Hash Map Counting, frequency-table tactics for turning membership, complement, and multiplicity questions into direct lookups.
Prefix Sums, accumulation tactics for answering range-sum and subarray-count questions from differences between checkpoints.

560. Subarray Sum Equals K (Medium)

Problem

Try it yourself

Approach 1: Brute force, check every subarray

Approach 2: Prefix sums with a hash map (optimal)

Why count[0] = 1?

Worked example

Summary

Test cases

Related topics

Related concepts

Why `count[0] = 1`?