If a problem asks the same question — “what’s the sum of this range?” — over and over on a fixed array, recomputing the sum each time is wasted work. Precompute once, answer forever: that’s the entire idea behind a prefix sum, and it’s one of the highest-leverage $O(n)$-setup tricks in all of interview coding.

What you’ll learn

• Building a prefix sum array in $O(n)$, then answering any range-sum query in $O(1)$.
• Extending prefix sums to 2D for rectangle-sum queries over a matrix.
• The difference array — the mirror-image trick for applying many range updates efficiently.
• The hashmap + prefix sum combo that turns “subarray sums equal to k” from $O(n^2)$ into $O(n)$.

The pattern: precompute once, query in O(1)

A prefix sum array prefixprefix stores running totals, with prefix[0] = 0prefix[0] = 0 and prefix[i] = nums[0] + nums[1] + ... + nums[i-1]prefix[i] = nums[0] + nums[1] + ... + nums[i-1]. The sum of any range [left, right][left, right] (inclusive) is then just a subtraction:

class NumArray:
    def __init__(self, nums):
        self.prefix = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            self.prefix[i + 1] = self.prefix[i] + x   # O(n) build, once
 
    def sum_range(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]   # O(1) per query
 
 
arr = NumArray([-2, 0, 3, -5, 2, -1])
print(arr.sum_range(0, 2))   # expect 1
print(arr.sum_range(2, 5))   # expect -1
print(arr.sum_range(0, 5))   # expect -3

class NumArray:
    def __init__(self, nums):
        self.prefix = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            self.prefix[i + 1] = self.prefix[i] + x   # O(n) build, once
 
    def sum_range(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]   # O(1) per query
 
 
arr = NumArray([-2, 0, 3, -5, 2, -1])
print(arr.sum_range(0, 2))   # expect 1
print(arr.sum_range(2, 5))   # expect -1
print(arr.sum_range(0, 5))   # expect -3

The +1+1 offset is what makes sum_rangesum_range subtraction-only, with no special case for left == 0left == 0: prefix[0] = 0prefix[0] = 0 acts as “the sum of nothing before the array starts.”

How it works

  graph LR
    N0["nums[0] = -2"] --> P1["prefix[1] = -2"]
    N1["nums[1] = 0"] --> P2["prefix[2] = -2"]
    N2["nums[2] = 3"] --> P3["prefix[3] = 1"]
    N3["nums[3] = -5"] --> P4["prefix[4] = -4"]
    P0["prefix[0] = 0 (empty prefix)"] --> P1
    P1 --> P2
    P2 --> P3
    P3 --> P4
    P3 -- "prefix[3] - prefix[0] = sum(nums[0..2]) = 1" --> P0

Each prefix[i]prefix[i] folds in one more element than the last — once that chain is built, any range sum is just two array lookups and a subtraction, no matter how wide the range.

Worked example: Subarray Sum Equals K

Count subarrays summing to exactly kk. The brute-force way checks every (left, right)(left, right) pair, $O(n^2)$. The prefix-sum trick: a subarray nums[i+1..j]nums[i+1..j] sums to kk exactly when prefix[j] - prefix[i] == kprefix[j] - prefix[i] == k — so for every new running sum, look up how many earlier prefix sums are exactly kk less, using a hashmap instead of a nested loop.

def subarray_sum_equals_k(nums, k):
    count = 0
    prefix_sum = 0
    seen = {0: 1}   # empty prefix (sum 0) has been "seen" once, before the array starts
 
    for x in nums:
        prefix_sum += x
        count += seen.get(prefix_sum - k, 0)          # how many earlier prefixes make this a valid subarray?
        seen[prefix_sum] = seen.get(prefix_sum, 0) + 1  # record the current running sum
 
    return count
 
 
print(subarray_sum_equals_k([1, 1, 1], 2))   # expect 2
print(subarray_sum_equals_k([1, 2, 3], 3))   # expect 2

def subarray_sum_equals_k(nums, k):
    count = 0
    prefix_sum = 0
    seen = {0: 1}   # empty prefix (sum 0) has been "seen" once, before the array starts
 
    for x in nums:
        prefix_sum += x
        count += seen.get(prefix_sum - k, 0)          # how many earlier prefixes make this a valid subarray?
        seen[prefix_sum] = seen.get(prefix_sum, 0) + 1  # record the current running sum
 
    return count
 
 
print(subarray_sum_equals_k([1, 1, 1], 2))   # expect 2
print(subarray_sum_equals_k([1, 2, 3], 3))   # expect 2

The same seenseen hashmap trick (running value -> how many times seen) solves Contiguous Array too: treat each 00 as -1-1 and each 11 as +1+1, then the longest subarray with equal 00s and 11s is the longest gap between two indices sharing the same running sum.

2D prefix sums: rectangle-sum queries

The same idea extends one dimension further. prefix[r][c]prefix[r][c] holds the sum of every cell in the rectangle from (0, 0)(0, 0) to (r-1, c-1)(r-1, c-1). Building it uses inclusion-exclusion to avoid double-counting the overlapping corner; querying a rectangle does the same subtraction in reverse.

class NumMatrix:
    def __init__(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
 
        for r in range(rows):
            for c in range(cols):
                self.prefix[r + 1][c + 1] = (
                    matrix[r][c]
                    + self.prefix[r][c + 1]      # sum above
                    + self.prefix[r + 1][c]      # sum to the left
                    - self.prefix[r][c]           # remove double-counted corner
                )
 
    def sum_region(self, row1, col1, row2, col2):
        p = self.prefix
        return (
            p[row2 + 1][col2 + 1]
            - p[row1][col2 + 1]
            - p[row2 + 1][col1]
            + p[row1][col1]
        )
 
 
matrix = [
    [3, 0, 1, 4, 2],
    [5, 6, 3, 2, 1],
    [1, 2, 0, 1, 5],
    [4, 1, 0, 1, 7],
    [1, 0, 3, 0, 5],
]
nm = NumMatrix(matrix)
print(nm.sum_region(2, 1, 4, 3))   # expect 8
print(nm.sum_region(1, 1, 2, 2))   # expect 11

class NumMatrix:
    def __init__(self, matrix):
        rows, cols = len(matrix), len(matrix[0])
        self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
 
        for r in range(rows):
            for c in range(cols):
                self.prefix[r + 1][c + 1] = (
                    matrix[r][c]
                    + self.prefix[r][c + 1]      # sum above
                    + self.prefix[r + 1][c]      # sum to the left
                    - self.prefix[r][c]           # remove double-counted corner
                )
 
    def sum_region(self, row1, col1, row2, col2):
        p = self.prefix
        return (
            p[row2 + 1][col2 + 1]
            - p[row1][col2 + 1]
            - p[row2 + 1][col1]
            + p[row1][col1]
        )
 
 
matrix = [
    [3, 0, 1, 4, 2],
    [5, 6, 3, 2, 1],
    [1, 2, 0, 1, 5],
    [4, 1, 0, 1, 7],
    [1, 0, 3, 0, 5],
]
nm = NumMatrix(matrix)
print(nm.sum_region(2, 1, 4, 3))   # expect 8
print(nm.sum_region(1, 1, 2, 2))   # expect 11

The plus/minus pattern in sum_regionsum_region is the 2D inclusion-exclusion principle: adding back p[row1][col1]p[row1][col1] corrects for subtracting the top-left overlap region twice.

The mirror image: difference arrays for range updates

Prefix sums answer “what’s the sum over this range?” fast. A difference array answers the opposite question fast: “add valval to every element in this range”, applied many times, each in $O(1)$ — by marking only the range’s two endpoints, then reconstructing the final array with a single prefix-sum pass at the very end.

def apply_range_updates(n, updates):
    diff = [0] * (n + 1)
 
    for left, right, val in updates:
        diff[left] += val          # start adding val from `left` onward
        diff[right + 1] -= val     # cancel that addition after `right`
 
    result = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]         # this IS a prefix sum over the diff array
        result[i] = running
 
    return result
 
 
# Add +2 to indices [1, 3], and +1 to indices [0, 2].
print(apply_range_updates(5, [(1, 3, 2), (0, 2, 1)]))   # expect [1, 3, 3, 2, 0]

def apply_range_updates(n, updates):
    diff = [0] * (n + 1)
 
    for left, right, val in updates:
        diff[left] += val          # start adding val from `left` onward
        diff[right + 1] -= val     # cancel that addition after `right`
 
    result = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]         # this IS a prefix sum over the diff array
        result[i] = running
 
    return result
 
 
# Add +2 to indices [1, 3], and +1 to indices [0, 2].
print(apply_range_updates(5, [(1, 3, 2), (0, 2, 1)]))   # expect [1, 3, 3, 2, 0]

Each update touches only 2 positions instead of the entire range, no matter how wide it is — $m$ updates cost $O(m)$ total, then one final $O(n)$ pass reconstructs the array. A difference array is quite literally a prefix sum array run in reverse.

Time and space complexity

When to use it

• Many range-sum queries on a fixed array or matrix — prefix sums turn each query from $O(n)$ into $O(1)$ after one $O(n)$ (or $O(rows \cdot cols)$) build.
• Many range updates (add a value to every element in [l, r][l, r]) followed by reading the final array once — a difference array does each update in $O(1)$ instead of $O(\text{range length})$.
• “Count subarrays/substrings matching some sum/parity condition” — pair a running prefix value with a hashmap of “seen so far” counts.
• Note the array must stay fixed between queries for a pure prefix sum to help; if elements change frequently between range-sum queries, a Fenwick tree / segment tree (outside this pattern) is the right upgrade.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output — then paste the same code into leetcode.com.

LC 303 — Range Sum Query, Immutable · Easy

Problem. Design NumArrayNumArray supporting sumRange(left, right)sumRange(left, right), returning the inclusive sum of nums[left..right]nums[left..right]. The array never changes, and there may be many queries.

Constraints. 1 <= len(nums) <= 10^41 <= len(nums) <= 10^4, -10^5 <= nums[i] <= 10^5-10^5 <= nums[i] <= 10^5, up to 10^410^4 calls.

Examples. For [-2,0,3,-5,2,-1][-2,0,3,-5,2,-1]: sumRange(0,2)sumRange(0,2) gives 11, sumRange(2,5)sumRange(2,5) gives -1-1, sumRange(0,5)sumRange(0,5) gives -3-3

LC 238 — Product of Array Except Self · Medium

Problem. Return an array where answer[i]answer[i] is the product of every element except nums[i]nums[i]. You must not use division, and it must run in $O(n)$.

Constraints. 2 <= len(nums) <= 10^52 <= len(nums) <= 10^5, -30 <= nums[i] <= 30-30 <= nums[i] <= 30, and the answer is guaranteed to fit in a 32-bit integer.

Examples. [1,2,3,4][1,2,3,4] gives [24,12,8,6][24,12,8,6] · [-1,1,0,-3,3][-1,1,0,-3,3] gives [0,0,9,0,0][0,0,9,0,0]

LC 1109 — Corporate Flight Bookings · Medium

Problem. Given nn flights labelled 1..n1..n and bookings [first, last, seats][first, last, seats] meaning seatsseats were reserved on every flight from firstfirst to lastlast inclusive, return the total seats reserved on each flight.

Constraints. 1 <= n <= 2 * 10^41 <= n <= 2 * 10^4, 1 <= len(bookings) <= 2 * 10^41 <= len(bookings) <= 2 * 10^4, 1 <= first <= last <= n1 <= first <= last <= n, 1 <= seats <= 10^41 <= seats <= 10^4.

Examples. bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5 gives [10,55,45,25,25][10,55,45,25,25] · bookings = [[1,2,10],[2,2,15]], n = 2bookings = [[1,2,10],[2,2,15]], n = 2 gives [10,25][10,25]

LeetCode problem set

Recap

• A prefix sum array turns repeated range-sum queries into $O(1)$ lookups after one $O(n)$ build; the +1+1 offset avoids special-casing left == 0left == 0.
• The same inclusion-exclusion idea extends to 2D for rectangle sums over a matrix.
• A difference array is the mirror image: many range updates, each $O(1)$, reconstructed into the real array with one final prefix-sum pass.
• Pairing a running prefix sum with a hashmap of “seen so far” counts solves subarray-sum-matching questions in $O(n)$ instead of $O(n^2)$.

You’ve now covered the core interview-pattern toolkit — top-k heaps, k-way merges, binary search on the answer, monotonic stacks, and prefix sums — the five patterns that recur across the widest range of DSA interview questions.