Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesMathReviewsAbout
Language
EnglishTürkçe

Prefix Sum

Guide 3 of 6 · Path 3 of 6

← PreviousNext →

Interactive

Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 6
1
1
1
map0→1

k = 2

Subarray sum equals k=2 on [1,1,1]. Count prefixes whose complement pref−k was seen.

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumprefix-sum

Subarray Sum Equals K

Problem (restated)

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

Intuition

Prefix sums: count how often (pref - k) has occurred. Each such earlier prefix forms a valid subarray ending here.

Approaches

Prefix sum + hash map

Unverified
Time O(n)Space O(n)

Idea. count[0]=1. Walk array updating pref; ans += count[pref-k]; count[pref]++.

Walkthrough. nums=[1,1,1], k=2 → subarrays [1,1] twice → answer 2.

Trade-offs. Handles negatives (sliding window does not). Must seed count[0]=1.

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

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

Template connection

Prefix sum + hashmap from the Prefix Sum template.

Reflection