Subarray sum

2 snippets in Interview Prep

DSAInterview Prep

Prefix Sum

syntax

Build a cumulative sum array so any range sum can be computed in O(1).
prefix[i] = sum of arr[0..i-1]
Range sum [l..r] = prefix[r+1] - prefix[l]

example

// JavaScript
function buildPrefix(arr) {
  const prefix = [0];
  for (const val of arr) {
    prefix.push(prefix[prefix.length - 1] + val);
  }
  return prefix;
}
function rangeSum(prefix, left, right) {
  return prefix[right + 1] - prefix[left];
}

# Python
def build_prefix(arr):
    prefix = [0]
    for val in arr:
        prefix.append(prefix[-1] + val)
    return prefix

def range_sum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

output

arr=[3,1,4,1,5] → prefix=[0,3,4,8,9,14]
rangeSum(1,3) = prefix[4]-prefix[1] = 9-3 = 6

Note Build: O(n) time, O(n) space. Query: O(1). Extremely useful when you need many range sum queries. Variant: prefix XOR for range XOR problems. For 2D grids, use 2D prefix sums with inclusion-exclusion.

Subarray Sum Equals K

DSA · Hash Maps & Sets

syntax

Use prefix sum + hash map.
At each index, check if (currentPrefix - k) was seen before.
Store prefix sum frequencies in the map.

example

// JavaScript
function subarraySum(nums, k) {
  const prefixCount = new Map([[0, 1]]);
  let prefix = 0, count = 0;
  for (const num of nums) {
    prefix += num;
    if (prefixCount.has(prefix - k)) {
      count += prefixCount.get(prefix - k);
    }
    prefixCount.set(prefix, (prefixCount.get(prefix) || 0) + 1);
  }
  return count;
}

# Python
def subarray_sum(nums, k):
    prefix_count = {0: 1}
    prefix = 0
    count = 0
    for num in nums:
        prefix += num
        count += prefix_count.get(prefix - k, 0)
        prefix_count[prefix] = prefix_count.get(prefix, 0) + 1
    return count

output

subarray_sum([1,1,1], 2) → 2
subarray_sum([1,2,3], 3) → 2 (subarrays [1,2] and [3])

Note Time O(n), Space O(n). Initialize map with {0: 1} to handle subarrays starting at index 0. This pattern is reusable: subarray sum divisible by k, subarray with equal 0s and 1s. One of the most asked medium-level problems.