Prefix Sum Questions 2026: 16+ Problems [Solved]

Last Updated: June 2026

Why Prefix Sum is a Must-Know Technique

Candidates report prefix sum as one of the highest-frequency array optimization techniques across Amazon, Google, and service company assessments. Based on public preparation resources and candidate-reported interview threads, it converts O(n) per range query to O(1), and it is the core building block for subarray sum problems, 2D grid queries, and difference arrays.

Core Concept

Array:    [3, 1, 4, 1, 5, 9, 2]
Index:     0  1  2  3  4  5  6

Prefix:   [0, 3, 4, 8, 9, 14, 23, 25]
Index:     0  1  2  3  4   5   6   7

prefix[i] = sum of arr[0..i-1]
prefix[0] = 0 (base case)
prefix[i] = prefix[i-1] + arr[i-1]

Sum of arr[l..r] = prefix[r+1] - prefix[l]

Building the Prefix Sum Array

def build_prefix(arr):
    """
    Time: O(n)  Space: O(n)
    """
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]
    return prefix


def range_sum(prefix, l, r):
    """
    Sum of arr[l..r] inclusive. O(1) query.
    """
    return prefix[r + 1] - prefix[l]

Practice Questions with Solutions

Problem 1: Range Sum Query - Immutable (EASY)

Asked at: Amazon, Google, TCS

class NumArray:
    """
    Precompute prefix sums. O(1) per query after O(n) build.
    """
    def __init__(self, nums):
        self.prefix = [0] * (len(nums) + 1)
        for i, num in enumerate(nums):
            self.prefix[i + 1] = self.prefix[i] + num

    def sum_range(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

# Example
na = NumArray([-2, 0, 3, -5, 2, -1])
print(na.sum_range(0, 2))   # 1
print(na.sum_range(2, 5))   # -1
print(na.sum_range(0, 5))   # -3

Complexity: Build O(n), Query O(1), Space O(n)

Problem 2: Subarray Sum Equals K (MEDIUM)

Asked at: Amazon, Google, Microsoft, Facebook - very frequently asked

def subarray_sum(nums, k):
    """
    At index i, we want prefix[i] - k to exist in our map.
    If prefix[i] - prefix[j] = k, then arr[j..i-1] has sum k.
    Time: O(n)  Space: O(n)
    """
    from collections import defaultdict

    count = 0
    prefix_sum = 0
    freq = defaultdict(int)
    freq[0] = 1  # empty prefix has sum 0

    for num in nums:
        prefix_sum += num
        count += freq[prefix_sum - k]
        freq[prefix_sum] += 1

    return count

# Example
print(subarray_sum([1, 1, 1], 2))    # 2 ([1,1] at [0,1] and [1,2])
print(subarray_sum([1, 2, 3], 3))    # 2 ([1,2] and [3])

Complexity: Time O(n), Space O(n)

Problem 3: Product of Array Except Self (MEDIUM)

Asked at: Amazon, Google, Facebook, Microsoft

def product_except_self(nums):
    """
    prefix[i] = product of all elements to the left of i.
    suffix[i] = product of all elements to the right of i.
    result[i] = prefix[i] * suffix[i]
    Time: O(n)  Space: O(1) excluding output
    """
    n = len(nums)
    result = [1] * n

    # Left pass: result[i] = product of all nums[0..i-1]
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]

    # Right pass: multiply result[i] by product of nums[i+1..n-1]
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]

    return result

# Example
print(product_except_self([1, 2, 3, 4]))   # [24, 12, 8, 6]
print(product_except_self([-1, 1, 0, -3, 3]))  # [0, 0, 9, 0, 0]

Complexity: Time O(n), Space O(1)

Problem 4: Find Pivot Index (EASY)

Asked at: Amazon, Google, TCS

def pivot_index(nums):
    """
    Pivot: left sum == right sum.
    Total = left_sum + nums[i] + right_sum
    right_sum = total - left_sum - nums[i]
    Time: O(n)  Space: O(1)
    """
    total = sum(nums)
    left_sum = 0

    for i, num in enumerate(nums):
        right_sum = total - left_sum - num
        if left_sum == right_sum:
            return i
        left_sum += num

    return -1

# Example
print(pivot_index([1, 7, 3, 6, 5, 6]))  # 3
print(pivot_index([1, 2, 3]))           # -1

Complexity: Time O(n), Space O(1)

Problem 5: Continuous Subarray Sum (MEDIUM)

Asked at: Amazon, Goldman Sachs, Microsoft

def check_subarray_sum(nums, k):
    """
    Subarray of length >= 2 with sum multiple of k.
    If prefix[i] % k == prefix[j] % k, subarray arr[j..i-1] sum is multiple of k.
    Store first occurrence of each remainder.
    Time: O(n)  Space: O(k)
    """
    remainder_map = {0: -1}
    prefix_sum = 0

    for i, num in enumerate(nums):
        prefix_sum += num
        remainder = prefix_sum % k

        if remainder in remainder_map:
            if i - remainder_map[remainder] >= 2:  # length at least 2
                return True
        else:
            remainder_map[remainder] = i

    return False

# Example
print(check_subarray_sum([23, 2, 4, 6, 7], 6))   # True (subarray [2,4])
print(check_subarray_sum([23, 2, 6, 4, 7], 6))   # True (entire array)

Complexity: Time O(n), Space O(k)

Problem 6: Maximum Size Subarray Sum Equals k (MEDIUM)

Asked at: Amazon, Google, Facebook

def max_sub_array_len(nums, k):
    """
    Find longest subarray with sum exactly k.
    Store first occurrence of each prefix sum.
    Time: O(n)  Space: O(n)
    """
    prefix_map = {0: -1}  # prefix_sum -> first index
    prefix_sum = 0
    max_len = 0

    for i, num in enumerate(nums):
        prefix_sum += num
        target = prefix_sum - k

        if target in prefix_map:
            max_len = max(max_len, i - prefix_map[target])

        if prefix_sum not in prefix_map:
            prefix_map[prefix_sum] = i  # store only first occurrence

    return max_len

# Example
print(max_sub_array_len([1, -1, 5, -2, 3], 3))   # 4 (subarray [1,-1,5,-2])
print(max_sub_array_len([-2, -1, 2, 1], 1))       # 2 (subarray [-1,2] or [2,-1])

Complexity: Time O(n), Space O(n)

Problem 7: Count of Subarrays with Sum in Range (MEDIUM)

Asked at: Amazon, Google

def count_subarrays_in_range(nums, lower, upper):
    """
    Count subarrays with sum in [lower, upper].
    = count(sum <= upper) - count(sum <= lower - 1)
    Use merge sort for O(n log n) or prefix + sorted structure.
    Time: O(n^2) simple  O(n log n) with merge sort
    """
    # O(n^2) approach for clarity
    count = 0
    n = len(nums)

    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]

    for i in range(1, n + 1):
        for j in range(i):
            s = prefix[i] - prefix[j]
            if lower <= s <= upper:
                count += 1

    return count

Problem 8: Range Sum Query 2D - Immutable (MEDIUM)

Asked at: Amazon, Google, Microsoft

class NumMatrix:
    """
    2D prefix sum. matrix[r1..r2][c1..c2] sum in O(1).
    Build in O(m*n), query in O(1).
    """
    def __init__(self, matrix):
        m, n = len(matrix), len(matrix[0])
        self.prefix = [[0] * (n + 1) for _ in range(m + 1)]

        for r in range(m):
            for c in range(n):
                self.prefix[r+1][c+1] = (
                    self.prefix[r][c+1] +
                    self.prefix[r+1][c] -
                    self.prefix[r][c] +
                    matrix[r][c]
                )

    def sum_region(self, row1, col1, row2, col2):
        return (self.prefix[row2+1][col2+1]
                - self.prefix[row1][col2+1]
                - self.prefix[row2+1][col1]
                + self.prefix[row1][col1])

# Example
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))   # 8
print(nm.sum_region(1, 1, 2, 2))   # 11

Complexity: Build O(mn), Query O(1), Space O(mn)

Problem 9: Difference Array (Range Update in O(1))

Asked at: Amazon, Google

Pattern: Apply range updates efficiently using a difference array.

def apply_range_updates(n, updates):
    """
    updates = [(l, r, val), ...]: add val to arr[l..r].
    Difference array: diff[l] += val, diff[r+1] -= val.
    Prefix sum of diff gives the final array.
    Time: O(n + q) where q = number of updates  Space: O(n)
    """
    diff = [0] * (n + 1)

    for l, r, val in updates:
        diff[l] += val
        if r + 1 <= n:
            diff[r + 1] -= val

    # Prefix sum to reconstruct final array
    result = [0] * n
    running = 0
    for i in range(n):
        running += diff[i]
        result[i] = running

    return result

# Example
# Array of size 5, updates: add 1 to [1..3], add 2 to [2..4]
print(apply_range_updates(5, [(1, 3, 1), (2, 4, 2)]))
# [0, 1, 3, 3, 2]

Complexity: Time O(n + q), Space O(n)

Problem 10: Number of Subarrays with Odd Sum (MEDIUM)

Asked at: Amazon, Google

def num_of_subarrays(arr):
    """
    Subarray has odd sum iff it has odd number of odd elements.
    Track count of even/odd prefix sums.
    Time: O(n)  Space: O(1)
    """
    MOD = 10**9 + 7
    even_count = 1  # prefix sum of 0 is even
    odd_count = 0
    prefix_sum = 0
    result = 0

    for num in arr:
        prefix_sum += num
        if prefix_sum % 2 == 0:
            result += odd_count   # even - odd = odd
            even_count += 1
        else:
            result += even_count  # odd - even = odd
            odd_count += 1

    return result % MOD

# Example
print(num_of_subarrays([1, 3, 5]))   # 4
print(num_of_subarrays([2, 4, 6]))   # 0

Complexity: Time O(n), Space O(1)

Prefix Sum vs Sliding Window vs Segment Tree

The Hash Map + Prefix Sum Pattern

This pattern solves "count/find subarrays with sum = k" in O(n):

1. Maintain running prefix_sum
2. At each index i, check if (prefix_sum - k) is in the hash map
3. If yes, all subarrays ending at i with sum k are counted
4. Store prefix_sum in hash map (key=sum, value=count or first index)

Key insight: prefix[i] - prefix[j] = sum of arr[j..i-1]
So arr[j..i-1] has sum k iff prefix[i] - k = prefix[j]

When Prefix Sum Fails

Prefix sum only works on static arrays. If the array gets updated between queries, you need a segment tree or Fenwick tree (Binary Indexed Tree). Prefix sums work for linear aggregations (sum, XOR) but not for non-linear ones like max or min range queries, which require sparse tables or segment trees.

For 2D prefix sums, the inclusion-exclusion formula requires four rectangle subtractions. Drawing the four rectangles on paper before coding eliminates sign errors more reliably than trying to memorize the formula.

The difference array is the inverse of prefix sum: it enables O(1) range updates, and a final prefix-sum pass reconstructs the array. This is underused in interviews but directly applicable to range-update-then-read problems.

The Hash Map Plus Prefix Sum Pattern Explained

The core insight: if prefix_sum at index j equals prefix_sum at index i, the subarray between j and i has sum zero. Extending this, if prefix_sum[i] - prefix_sum[j] = k, the subarray arr[j..i-1] has sum k. By storing every prefix sum in a hash map as we traverse, we can check in O(1) whether the required complement exists.

This pattern is why you should always initialize the hash map with {0: 1} (or {0: -1} for first-occurrence). The empty prefix of sum 0 must be accounted for, otherwise subarrays starting at index 0 are missed.

Choosing the Right Range Query Structure

The right data structure depends on whether updates happen, what the aggregation is, and query count.

For offline problems where all queries are known in advance, sorting plus prefix sums often beats segment trees in implementation speed. In interviews, stating this tradeoff explicitly signals depth.

Common Mistakes

1. Off-by-one in prefix array: prefix[i] should be sum of arr[0..i-1], making prefix[0]=0 the base case.
2. Not including 0 in hash map: Always start with freq[0] = 1 or first_seen[0] = -1 before the loop.
3. Updating hash map before or after checking: For counting, update after checking. For first-occurrence, update only if not present.

Related Articles

• Sliding Window Pattern Questions 2026
• Arrays Questions Placement
• Binary Search Patterns 2026
• Dynamic Programming Patterns 2026
• Must-Do Coding Questions