Prefix Sum Coding Problems: 63 Questions with Solutions

How prefix sum works, step by step

1. prefix[k] will hold the sum of the first k numbers, so the row is one longer than nums and starts with prefix[0] = 0, the empty sum. Each entry sits under the boundary where its numbers end.
2. prefix[1] = prefix[0] + nums[0] = 0 + 2 = 2. Each entry is the one before it plus one more number, so no stretch is ever added up twice.
3. prefix[2] = prefix[1] + nums[1] = 2 + 4 = 6, the same as 2 + 4 without adding those again.
4. prefix[3] = prefix[2] + nums[2] = 6 + 1 = 7, the same as 2 + 4 + 1 without adding those again.
5. prefix[4] = prefix[3] + nums[3] = 7 + 3 = 10, the same as 2 + 4 + 1 + 3 without adding those again.
6. prefix[5] = prefix[4] + nums[4] = 10 + 5 = 15, the same as 2 + 4 + 1 + 3 + 5 without adding those again.
7. prefix[6] = prefix[5] + nums[5] = 15 + 2 = 17, the total of all 6 numbers. The whole row took 6 additions: O(n), paid once.
8. Now the sum of nums[1..4]. prefix[5] covers indices 0 to 4 and prefix[1] covers index 0 alone, so taking one from the other leaves exactly indices 1 to 4.
9. 15 − 2 = 13, the same as 4 + 1 + 3 + 5. Any range now costs one subtraction, O(1), after the O(n) build, instead of up to n additions per query.

Prefix Sum study plan

14 of the 63 Prefix Sum problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 49 in the full list below are practice at your own pace. Then move on to Sorting.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

• Running Sum of 1d Array Easy
• Find Pivot Index Easy
• Find the Highest Altitude Easy

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

• Left and Right Sum Differences Easy
• Product of Array Except Self Medium

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Minimum Size Subarray Sum Medium
• Subarray Sum Equals K Medium

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Contiguous Array Medium
• Continuous Subarray Sum Medium

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Car Pooling Medium
• Subarray Product Less Than K Medium

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

• Count of Range Sum Hard

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Shortest Subarray with Sum at Least K Hard

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Minimum Number of K Consecutive Bit Flips Hard

Next topic: Sorting

Prefix Sum: the essentials

When to reach for it

Many sum queries over ranges of an array that does not change; "subarrays whose sum equals, or is divisible by, k" when values can be negative, which breaks a Sliding Window; "the index where the left and right sums balance"; many range updates applied at once, which is the difference array, the prefix sum run backwards.

The pattern

Define pre[0] = 0 and pre[i + 1] = pre[i] + nums[i]; the sum of nums[l..r] is then pre[r + 1] - pre[l]. To count subarrays that sum to k in one pass, keep a map from each prefix total to how often it has occurred: a subarray ending at the current index sums to k exactly when an earlier prefix equals the current total minus k.

def subarray_sum(nums, k):
    seen = {0: 1}                   # the empty prefix
    total = count = 0
    for x in nums:
        total += x
        count += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return count

Cost

O(n) to build and O(1) per range query. The two-dimensional table costs O(m × n) to build and answers the sum of any rectangle with four lookups.

Common mistakes

• Leaving out the empty prefix ({0: 1}), which misses every subarray that starts at index 0.
• An off-by-one between pre[r] - pre[l] and pre[r + 1] - pre[l]; settle the convention once and keep it.
• Recording the current total before looking it up, which counts the empty subarray when k is 0.
• Overflow: 10⁵ values up to 10⁹ sum to 10¹⁴, which needs 64-bit integers.

Start with

• Running Sum of 1d Array: the prefix array itself.
• Find Pivot Index: the left sum compared with the total.
• Subarray Sum Equals K: prefix totals in a hash map.

All prefix sum problems

Easy (15)

• Minimum Sum of Mountain Triplets I Array
• Find the Pivot Integer Math
• Find the Distinct Difference Array Array, Hash Table
• Points That Intersect With Cars Array
• Ant on the Boundary Array, Simulation
• Maximum Population Year Array, Counting
• Minimum Value to Get Positive Step by Step Sum Array
• Partition Array Into Three Parts With Equal Sum Array, Greedy
• Equilibrium Point Array
• Maximum Score After Splitting a String String
• Left and Right Sum Differences Array
• Sum of All Odd Length Subarrays Array, Math
• Find the Highest Altitude Array
• Running Sum of 1d Array Array
• Find Pivot Index Array

Medium (38)

• Corporate Flight Bookings Array
• Longest Subsequence With Limited Sum Array, Binary Search, Greedy
• Minimum Sum of Mountain Triplets II Array
• Maximum Value of an Ordered Triplet II Array
• Construct Product Matrix Array, Matrix
• Matrix Block Sum Array, Matrix
• Find the N-th Value After K Seconds Array, Math, Simulation
• Number of Ways to Select Buildings String, Dynamic Programming
• Stone Game II Array, Dynamic Programming, Game Theory
• Minimum Number of Operations to Move All Balls to Each Box Array, String, Greedy
• Find the Student That Will Replace the Chalk Array, Binary Search, Simulation
• Get Equal Substrings Within Budget String, Sliding Window, Binary Search
• Maximize the Confusion of an Exam String, Sliding Window, Binary Search
• K Radius Subarray Averages Array, Sliding Window
• Maximum Points You Can Obtain from Cards Array, Sliding Window
• Maximum OR Bit Manipulation, Array, Greedy
• Number of Wonderful Substrings Bit Manipulation, Hash Table, String
• Find the Longest Substring Containing Vowels in Even Counts Bit Manipulation, Hash Table, String
• Maximum XOR for Each Query Bit Manipulation, Array
• XOR Queries of a Subarray Bit Manipulation, Array
• Find The Original Array of Prefix Xor Bit Manipulation, Array
• Maximum Value of an Ordered Triplet I Array, Math
• Maximum Size Subarray Sum Equals k Array, Hash Table
• Longest Well-Performing Interval Array, Hash Table, Stack
• Subarray Sums Divisible by K Array, Hash Table
• Number of Good Ways to Split a String String, Hash Table
• Longest Subarray With Sum Zero Array, Hash Table
• Count Triplets That Can Form Two Arrays of Equal XOR Array, Hash Table, Math
• Count Number of Nice Subarrays Array, Hash Table, Math
• Binary Subarrays With Sum Array, Hash Table, Sliding Window
• Minimum Operations to Reduce X to Zero Array, Hash Table, Binary Search
• Continuous Subarray Sum Array, Hash Table, Math
• Contiguous Array Array, Hash Table
• Subarray Product Less Than K Array, Sliding Window, Binary Search
• Car Pooling Array, Intervals, Sorting
• Minimum Size Subarray Sum Array, Sliding Window
• Subarray Sum Equals K Array, Hash Table
• Product of Array Except Self Array

Hard (10)

• Number of Ways to Separate Numbers String, Dynamic Programming, Suffix Array
• Build Array Where You Can Find The Maximum Exactly K Comparisons Dynamic Programming
• Stone Game VIII Array, Math, Dynamic Programming
• Maximum Value of K Coins From Piles Array, Dynamic Programming
• Number of Submatrices That Sum to Target Array, Matrix, Hash Table
• Minimum White Tiles After Covering With Carpets String, Dynamic Programming
• Take K of Each Character From Left and Right String, Hash Table, Sliding Window
• Minimum Number of K Consecutive Bit Flips Array, Sliding Window, Greedy
• Shortest Subarray with Sum at Least K Array, Sliding Window, Monotonic Queue
• Count of Range Sum Fenwick Tree, Divide and Conquer

Companies that ask prefix sum problems

• Amazon 57 problems on prefix sum
• Google 44 problems on prefix sum
• Meta 11 problems on prefix sum
• Microsoft 9 problems on prefix sum
• Adobe 8 problems on prefix sum
• Uber 8 problems on prefix sum
• TCS 5 problems on prefix sum
• Zoho 3 problems on prefix sum
• Capgemini 2 problems on prefix sum
• Flipkart 2 problems on prefix sum
• Infosys 2 problems on prefix sum
• Paytm 2 problems on prefix sum

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Dynamic Programming 195 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems