Prefix Sum Technique
High ImportancePrecompute cumulative sums in a single O(N) pass to answer any contiguous range sum query in O(1) time and detect target subarray sums in O(N) using Hash Map frequency tracking.
When to Use Prefix Sum:
Key problem characteristics and signals indicating that this technique is the optimal choice.
Multiple range sum queries sum(L ... R) on a static array where precomputing enables instant O(1) responses.
Subarray sum equal to K search, especially when elements can be negative, zero, or non-monotonic (rendering sliding window invalid).
Subarray sum divisible by K or modulo remainder matching using remainder hash maps: (prefix[j] - prefix[i]) % K == 0.
2D submatrix or bounding rectangle sum queries on fixed grids using 2D Inclusion-Exclusion precomputation.
Difference array techniques for batch range updates arr[L ... R] += val in O(1) followed by a final prefix reconstruction.
Prerequisite Rule: Static Array & Non-Monotonic Capability: Prefix Sum is ideal for static arrays where elements do not undergo frequent point updates (for dynamic updates, use a Fenwick / Binary Indexed Tree or Segment Tree). Unlike sliding window, Prefix Sum handles negative integers and zeros without breaking correctness.
Example Problem — Subarray Sum Equals K
The benchmark interview problem demonstrating the transition from quadratic brute force to linear optimality.
Problem Statement
Given an array of integers arr[] and an integer K, find the total number of continuous subarrays whose sum equals to K. Return the count of matching subarrays.
arr = [1, 2, 3, -2, 2], K = 3
4 (Subarrays: [1, 2], [3], [2, 3, -2], and [3, -2, 2])
Explanation: Subarrays summing to 3 are: arr[0..1] (1 + 2 = 3), arr[2..2] (3), arr[1..3] (2 + 3 - 2 = 3), and arr[2..4] (3 - 2 + 2 = 3). Total valid subarrays = 4.
Naive Method — O(n²) Time and O(1) Space
The baseline brute force approach recalculating candidates through nested loops.
The brute force approach iterates over every possible subarray starting index i from 0 to n - 1, and for each start, accumulates elements up to index j from i to n - 1, checking if the accumulated sum equals K.
def subarray_sum_equals_k_naive(arr: list[int], k: int) -> int: n = len(arr) count = 0 # Check every subarray starting at i and ending at j for i in range(n): current_sum = 0 for j in range(i, n): current_sum += arr[j] if current_sum == k: count += 1 return countWhy Naive Fails in Production & Interviews
For an array with n = 10⁵ elements, checking all n(n + 1)/2 subarrays requires ~5 × 10⁹ operations, causing Time Limit Exceeded (TLE). Because negative numbers can appear, expanding a subarray can increase or decrease the sum unpredictably, making two pointers impossible without hashing prefix states.
Prefix Sum + Hash Map Technique — O(n) Time and O(n) Space
The optimal strategy leveraging prefix sum mechanics to achieve optimal time complexity.
By maintaining a cumulative prefix sum and storing the frequency of observed prefix sums in a Hash Map, any subarray arr[i ... j] with sum K satisfies prefix[j] - prefix[i - 1] = K, which rearranges to prefix[i - 1] = prefix[j] - K. We look up this required complement in O(1) time at each step.
1. Initialize Frequency Map: Set prefix_counts = {0: 1} to account for subarrays starting directly from index 0 whose sum equals K.
2. Track Running Cumulative Sum: Iterate through arr and accumulate current_prefix += num at each index in O(1).
3. Query Target Complement: Check if complement = current_prefix - K exists in prefix_counts. If present, add its count prefix_counts[complement] to total_subarrays.
4. Record Current Prefix: Increment the frequency of current_prefix in the map: prefix_counts[current_prefix] = prefix_counts.get(current_prefix, 0) + 1.
5. Return Total Count: After a single linear pass of length N, return total_subarrays. Runtime is strictly O(N).
Interactive Trace
Interactive Trace: Subarray Sum Equals K (arr = [1, 2, 3, -2, 2], K = 3)
Interactive Trace: Subarray Sum Equals K (arr = [1, 2, 3, -2, 2], K = 3)
arr = [1, 2, 3, -2, 2], K = 3
4 Valid Subarrays
State Mutation Inspector
Decision & Invariant Action
Process arr[0]=1. Current prefix = 1. Complement 1 - 3 = -2 not in map. Map updated to {0: 1, 1: 1}.
Prefix Sum Algorithm Code
Complete runnable solution in Python, C++, Java, and JavaScript.
from collections import defaultdict def subarray_sum_equals_k(arr: list[int], k: int) -> int: """ Standard Prefix Sum + Hash Map Template Time Complexity: O(N) | Space Complexity: O(N) """ prefix_counts = defaultdict(int) prefix_counts[0] = 1 # Base case: sum of empty prefix is 0 current_prefix = 0 total_subarrays = 0 for num in arr: current_prefix += num complement = current_prefix - k if complement in prefix_counts: total_subarrays += prefix_counts[complement] prefix_counts[current_prefix] += 1 return total_subarraysHow does this work?
The Subarray Sum Identity & Why Complement Hashing Guarantees O(N) Optimality
The sum of elements between indices i and j equals prefix[j] - prefix[i - 1]. By algebraic rearrangement, searching for a subarray sum equal to K is equivalent to checking if an earlier prefix equals current_prefix - K in O(1).
1. Subarray Sum Fundamental Theorem
Let prefix[k] = arr[0] + arr[1] + ... + arr[k]. The sum of any contiguous segment arr[i ... j] equals prefix[j] - prefix[i - 1] (with prefix[-1] = 0). Every contiguous subarray sum in existence is strictly the difference between two cumulative prefixes.
2. The Complement Rearrangement Equation
Setting sum(arr[i ... j]) = K gives prefix[j] - prefix[i - 1] = K, which rearranges algebraically to prefix[i - 1] = prefix[j] - K. For the current index j, every past index i - 1 whose prefix sum equals prefix[j] - K defines a valid contiguous subarray ending at j with sum K.
3. One-Pass Linear Guarantee Without Sorting
By incrementally updating the frequency map as we traverse from left to right, we guarantee that only prefixes occurring strictly before the current index are queried. This avoids false forward-matches and ensures an exact O(N) single-pass execution.
4. Universal Robustness over Negative Numbers
Sliding window requires monotonic sums (where advancing the window strictly increases sum). Prefix sum makes zero assumptions about monotonicity: whether numbers are positive, negative, or zero, the algebraic identity prefix[j] - prefix[i - 1] = K remains 100% exact.
Core Pattern Variations & Blueprints
Explore the 3 structural variations that power all prefix sum interview problems. Click each variation to expand its blueprint, interactive dry run, and implementation.
Precompute cumulative sums prefix[i] = prefix[i-1] + arr[i]. Any range sum query sum(L ... R) is answered in strictly O(1) time via prefix[R] - (L > 0 ? prefix[L - 1] : 0).
The Algorithmic Invariant
sum(arr[L ... R]) = prefix[R] - prefix[L - 1] (or prefix[R+1] - prefix[L] with 1-based indexing).
Pointer Traversal Flow
Array: [ 2, 4, 1, 3, 5 ]
Prefix Array: [ 2, 6, 7, 10, 15 ]
Query: sum(1 ... 3) = arr[1] + arr[2] + arr[3] = 4 + 1 + 3 = 8
Formula: prefix[3] - prefix[0] = 10 - 2 = 8 (O(1) time!)Worked Example: Range Sum Query (arr = [2, 4, 1, 3, 5], Query: L = 1, R = 3)
arr = [2, 4, 1, 3, 5], L = 1, R = 3Step 1: Compute prefix array -> [2, 6, 7, 10, 15].
Step 2: Fetch prefix[R] = prefix[3] = 10.
Step 3: Fetch prefix[L - 1] = prefix[0] = 2.
Step 4: Subtract: prefix[3] - prefix[0] = 10 - 2 = 8. Output = 8.
Interactive Dry Run Simulator
1D Prefix Trace: Range Sum sum(1 ... 3)
arr = [2, 4, 1, 3, 5], Query: L = 1, R = 3
Sum = 8 (4 + 1 + 3)
State Mutation Inspector
Decision & Invariant Action
Prefix cumulative sum: prefix[0]=2, prefix[1]=6, prefix[2]=7, prefix[3]=10, prefix[4]=15.
Production-Grade Implementation
class NumArray: """ 1D Prefix Sum Range Query Precomputation: O(N) | Query: O(1) | Space: O(N) """ def __init__(self, nums: list[int]): # Use 1-based indexing to avoid boundary checks self.prefix = [0] * (len(nums) + 1) for i in range(len(nums)): self.prefix[i + 1] = self.prefix[i] + nums[i] def sumRange(self, left: int, right: int) -> int: return self.prefix[right + 1] - self.prefix[left]Landmine to Avoid: Subtracting prefix[L] instead of prefix[L - 1], which accidentally excludes element arr[L] from the sum.
Curated Practice Ladder
Master this pattern progressively through verified interview questions.
Create a free account to track progress and unlock your free practice set.
Premium also includes the full problem library, detailed solutions, hints, and advanced revision tools.
Already have an account? Log in
“Master the invariants,
and the solution
writes itself.”
