#78 · Arrays & Hashing

Subarray Sum Equals K

Given an integer array nums and an integer k, return the total number of contiguous subarrays whose sum equals k. Values may be negative.

MediumLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Prefix sums

prefix[e] is the sum of the first e elements. A subarray from i to e − 1 has sum prefix[e] − prefix[i], so a range sum becomes a subtraction of two stored numbers.

Memory layout

One extra array of n + 1 numbers, or just a running total if only the latest prefix is needed.

Operation	Cost
range sum	O(1)
build	O(n)

Hash map of prefix-sum counts

Maps a prefix-sum value to how many times it has occurred. At each end position, the number of valid starts is the count of the prefix (current − k).

Memory layout

A hash table with up to n + 1 entries; counts, not indices, because only the number of matches matters.

Operation	Cost
lookup / update	O(1) average
space	O(n)

Why it fits

Counting subarrays with a given sum is the same as counting pairs of prefixes whose difference is k, which is a lookup problem, ideal for a hash map.
Negative numbers break the sliding window (the sum no longer grows monotonically as the window expands), but prefix differences do not care about sign.
The map must count occurrences (not just remember existence) because the same prefix value can appear several times when elements sum to zero.

Why alternatives degrade

Sliding window:: Only works for non-negative numbers: with negatives, shrinking the window can increase the sum, so there is no safe direction to move.
Sorted prefix array + binary search:: Sorting loses the position order (starts must come before ends) and costs O(n log n).
Set of prefixes:: It misses repeats: if the prefix (current − k) occurred twice, two different subarrays qualify, which a set counts once.

Four approaches, from naive to production

1 · beginner

Try every subarray and re-add it

time O(n³)space O(1)

For each pair of start i and end j, sum nums[i … j] from scratch and count it when the sum equals k.

int subarraySum(vector<int>& nums, int k) {
    int count = 0;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            long long sum = 0;
            for (int t = i; t <= j; t++) sum += nums[t];
            if (sum == k) count++;
        }
    }
    return count;
}

public int subarraySum(int[] nums, int k) {
    int count = 0;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            long sum = 0;
            for (int t = i; t <= j; t++) sum += nums[t];
            if (sum == k) count++;
        }
    }
    return count;
}

def subarray_sum(nums, k):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i, n):
            total = 0
            for t in range(i, j + 1): total += nums[t]
            if total == k: count += 1
    return count

function subarraySum(nums: number[], k: number): number {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    for (let j = i; j < nums.length; j++) {
      let sum = 0;
      for (let t = i; t <= j; t++) sum += nums[t];
      if (sum === k) count++;
    }
  }
  return count;
}

Flaws & bottlenecks

Three nested loops: about n³ / 6 additions.
Adjacent subarrays share almost all of their elements, yet are re-summed from scratch.
Unusable beyond a few hundred elements.

Interviewer cross-questions

How do you remove the innermost loop?

Say: Extend the previous sum by one element as j increases, or use prefix sums to get any range sum in O(1).

Can the sum overflow?

Say: With LeetCode limits (2 · 10⁴ elements of magnitude up to 1000) the sum fits in 32 bits, but with larger inputs use 64-bit integers.

Does it count overlapping subarrays?

Say: Yes: every pair (i, j) is a different subarray, even when they overlap.

2 · intermediate

Running sum from each start

time O(n²)space O(1)

For each start i, extend j to the right keeping a running sum, and count each time it equals k.

int subarraySum(vector<int>& nums, int k) {
    int count = 0;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            if (sum == k) count++;
        }
    }
    return count;
}

public int subarraySum(int[] nums, int k) {
    int count = 0;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        long sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            if (sum == k) count++;
        }
    }
    return count;
}

def subarray_sum(nums, k):
    count = 0
    n = len(nums)
    for i in range(n):
        total = 0
        for j in range(i, n):
            total += nums[j]
            if total == k: count += 1
    return count

function subarraySum(nums: number[], k: number): number {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      if (sum === k) count++;
    }
  }
  return count;
}

Flaws & bottlenecks

Still quadratic: 2 · 10⁴ elements means about 2 · 10⁸ steps.
Cannot stop early: with negative numbers the sum can come back to k later.
Does not exploit the repeated structure across different starts.

Interviewer cross-questions

If all numbers were positive, could you stop early?

Say: Yes: once the sum exceeds k it can only grow, so break out. Even better, use a two-pointer sliding window in O(n).

Why does that not work with negatives?

Say: A later negative number can bring the sum back down to k, so no prefix of the scan can be discarded.

What would make this linear?

Say: Remember how often each prefix sum has occurred and look up (current − k) in a hash map.

3 · advanced

Prefix array with a counting hash map

time O(n)space O(n)

Build the prefix array, then walk the ends. For each end e, the answer grows by the number of earlier prefixes equal to prefix[e] − k. Seed the map with the empty prefix 0.

int subarraySum(vector<int>& nums, int k) {
    vector<long long> prefix{0};
    for (int x : nums) prefix.push_back(prefix.back() + x);
    unordered_map<long long, int> seen{{0, 1}};
    int count = 0;
    for (int end = 1; end < (int)prefix.size(); end++) {
        auto it = seen.find(prefix[end] - k);
        count += (it == seen.end()) ? 0 : it->second;
        seen[prefix[end]]++;
    }
    return count;
}

public int subarraySum(int[] nums, int k) {
    List<Long> prefix = new ArrayList<>(); prefix.add(0L);
    for (int x : nums) prefix.add(prefix.get(prefix.size() - 1) + x);
    Map<Long, Integer> seen = new HashMap<>(); seen.put(0L, 1);
    int count = 0;
    for (int end = 1; end < prefix.size(); end++) {
        count += seen.getOrDefault(prefix.get(end) - k, 0);
        seen.merge(prefix.get(end), 1, Integer::sum);
    }
    return count;
}

def subarray_sum(nums, k):
    prefix = [0]
    for x in nums: prefix.append(prefix[-1] + x)
    seen = {0: 1}
    count = 0
    for end in range(1, len(prefix)):
        count += seen.get(prefix[end] - k, 0)
        seen[prefix[end]] = seen.get(prefix[end], 0) + 1
    return count

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

Flaws & bottlenecks

Two O(n) structures: the prefix array and the map.
Forgetting the seed (0 → 1) misses subarrays that start at index 0.
Hash collisions could degrade the worst case.

Interviewer cross-questions

Why store counts and not a set?

Say: The same prefix can occur many times (elements summing to zero), and each earlier occurrence is a distinct valid start.

Why add the current prefix AFTER the lookup?

Say: A subarray must be non-empty, so the current prefix must not match itself when k = 0.

Is the prefix array necessary?

Say: No, only the latest prefix is used; keep a running sum instead.

4 · expert

Single pass with a running prefix

time O(n)space O(n)

Keep one running sum and the count map. For each element: update the sum, add seen[sum − k] to the answer, then record the sum.

int subarraySum(vector<int>& nums, int k) {
    unordered_map<long long, int> seen{{0, 1}};
    long long sum = 0; int count = 0;
    for (int x : nums) {
        sum += x;
        long long need = sum - k;
        auto it = seen.find(need);
        count += (it == seen.end()) ? 0 : it->second;
        seen[sum]++;
    }
    return count;
}

public int subarraySum(int[] nums, int k) {
    Map<Long, Integer> seen = new HashMap<>(); seen.put(0L, 1);
    long sum = 0; int count = 0;
    for (int x : nums) {
        sum += x;
        long need = sum - k;
        count += seen.getOrDefault(need, 0);
        seen.merge(sum, 1, Integer::sum);
    }
    return count;
}

def subarray_sum(nums, k):
    seen = {0: 1}
    total = count = 0
    for x in nums:
        total += x
        need = total - k
        count += seen.get(need, 0)
        seen[total] = seen.get(total, 0) + 1
    return count

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

Flaws & bottlenecks

O(n) map space in the worst case (all prefix sums distinct).
Use 64-bit integers for the sum and counts when inputs are large.
Hash map overhead is real: constants matter for very large n.

Interviewer cross-questions

What changes if you only need to know whether such a subarray exists?

Say: Replace the count map with a set and return as soon as (sum − k) is found.

Can you do it in O(1) space?

Say: Not in general with negatives: O(1) space solutions require non-negative numbers (sliding window).

How would you handle a stream?

Say: This is already online: process each element as it arrives and keep the running count; memory grows with distinct prefix sums.

Synchronized code walkthrough

Showing: Try every subarray and re-add it — shares the player above; click any step to jump.

int subarraySum(vector<int>& nums, int k) {
    int count = 0;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            long long sum = 0;
            for (int t = i; t <= j; t++) sum += nums[t];
            if (sum == k) count++;
        }
    }
    return count;
}

public int subarraySum(int[] nums, int k) {
    int count = 0;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            long sum = 0;
            for (int t = i; t <= j; t++) sum += nums[t];
            if (sum == k) count++;
        }
    }
    return count;
}

def subarray_sum(nums, k):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i, n):
            total = 0
            for t in range(i, j + 1): total += nums[t]
            if total == k: count += 1
    return count

function subarraySum(nums: number[], k: number): number {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    for (let j = i; j < nums.length; j++) {
      let sum = 0;
      for (let t = i; t <= j; t++) sum += nums[t];
      if (sum === k) count++;
    }
  }
  return count;
}

int subarraySum(vector<int>& nums, int k) {
    int count = 0;
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            if (sum == k) count++;
        }
    }
    return count;
}

public int subarraySum(int[] nums, int k) {
    int count = 0;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        long sum = 0;
        for (int j = i; j < n; j++) {
            sum += nums[j];
            if (sum == k) count++;
        }
    }
    return count;
}

def subarray_sum(nums, k):
    count = 0
    n = len(nums)
    for i in range(n):
        total = 0
        for j in range(i, n):
            total += nums[j]
            if total == k: count += 1
    return count

function subarraySum(nums: number[], k: number): number {
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      if (sum === k) count++;
    }
  }
  return count;
}

int subarraySum(vector<int>& nums, int k) {
    vector<long long> prefix{0};
    for (int x : nums) prefix.push_back(prefix.back() + x);
    unordered_map<long long, int> seen{{0, 1}};
    int count = 0;
    for (int end = 1; end < (int)prefix.size(); end++) {
        auto it = seen.find(prefix[end] - k);
        count += (it == seen.end()) ? 0 : it->second;
        seen[prefix[end]]++;
    }
    return count;
}

public int subarraySum(int[] nums, int k) {
    List<Long> prefix = new ArrayList<>(); prefix.add(0L);
    for (int x : nums) prefix.add(prefix.get(prefix.size() - 1) + x);
    Map<Long, Integer> seen = new HashMap<>(); seen.put(0L, 1);
    int count = 0;
    for (int end = 1; end < prefix.size(); end++) {
        count += seen.getOrDefault(prefix.get(end) - k, 0);
        seen.merge(prefix.get(end), 1, Integer::sum);
    }
    return count;
}

def subarray_sum(nums, k):
    prefix = [0]
    for x in nums: prefix.append(prefix[-1] + x)
    seen = {0: 1}
    count = 0
    for end in range(1, len(prefix)):
        count += seen.get(prefix[end] - k, 0)
        seen[prefix[end]] = seen.get(prefix[end], 0) + 1
    return count

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

int subarraySum(vector<int>& nums, int k) {
    unordered_map<long long, int> seen{{0, 1}};
    long long sum = 0; int count = 0;
    for (int x : nums) {
        sum += x;
        long long need = sum - k;
        auto it = seen.find(need);
        count += (it == seen.end()) ? 0 : it->second;
        seen[sum]++;
    }
    return count;
}

public int subarraySum(int[] nums, int k) {
    Map<Long, Integer> seen = new HashMap<>(); seen.put(0L, 1);
    long sum = 0; int count = 0;
    for (int x : nums) {
        sum += x;
        long need = sum - k;
        count += seen.getOrDefault(need, 0);
        seen.merge(sum, 1, Integer::sum);
    }
    return count;
}

def subarray_sum(nums, k):
    seen = {0: 1}
    total = count = 0
    for x in nums:
        total += x
        need = total - k
        count += seen.get(need, 0)
        seen[total] = seen.get(total, 0) + 1
    return count

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