Prefix Sum Coding Problems: 137 Questions with Solutions
137 prefix sum coding problems — 19 easy · 85 medium · 33 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 8-day plan.
- Problems: 137
- By difficulty: 19 easy · 85 medium · 33 hard
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
- Cost: Free on every plan; sign in to run and submit
A prefix-sum array stores the running total, so the sum of any range is one subtraction. Range-sum queries, subarrays with a target sum (with a hash map of prefixes seen), balanced pivots and two-dimensional grid sums all rest on it; the problems here practise building the prefix once and reading it many times.
New to prefix sum? Read the Prefix Sum tutorial first.
How prefix sum works, step by step
nums = [2, 4, 1, 3, 5, 2]; query: sum of nums[1..4]- 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.
- 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.
- prefix[2] = prefix[1] + nums[1] = 2 + 4 = 6, the same as 2 + 4 without adding those again.
- prefix[3] = prefix[2] + nums[2] = 6 + 1 = 7, the same as 2 + 4 + 1 without adding those again.
- prefix[4] = prefix[3] + nums[3] = 7 + 3 = 10, the same as 2 + 4 + 1 + 3 without adding those again.
- prefix[5] = prefix[4] + nums[4] = 10 + 5 = 15, the same as 2 + 4 + 1 + 3 + 5 without adding those again.
- 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.
- 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.
- 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 137 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 123 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.
Day 2
Medium problems: the same pattern with one twist each. Name the twist before you code.
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.
Day 8
Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.
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]andpre[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 (19)
- Range Sum Query - Immutable Array, Design
- Minimum Positive Sum Subarray Array, Sliding Window
- Check if All the Integers in a Range Are Covered Array, Hash Table
- Distance Between Bus Stops Array
- 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 (85)
- Product of the Last K Numbers Array, Math, Design
- My Calendar II Array, Binary Search, Ordered Set
- Range Sum Query 2D - Immutable Array, Matrix, Design
- Path Sum III Tree, Depth-First Search, Hash Table
- All Divisions With the Highest Score of a Binary Array Array
- Count the Hidden Sequences Array
- Intervals Between Identical Elements Array, Hash Table
- Find Good Days to Rob the Bank Array, Dynamic Programming
- Maximum Number of Non-Overlapping Subarrays With Sum Equals Target Array, Hash Table, Greedy
- Count Beautiful Substrings I Hash Table, Math, String
- Shifting Letters Array, String
- Count Partitions With Max-Min Difference at Most K Array, Dynamic Programming, Queue
- Maximum Frequency After Subarray Operation Array, Hash Table, Dynamic Programming
- Largest Magic Square Array, Matrix
- Get Biggest Three Rhombus Sums in a Grid Array, Matrix, Sorting
- Maximum Sum of an Hourglass Array, Matrix
- Find All Possible Stable Binary Arrays I Dynamic Programming, Combinatorics
- Describe the Painting Array, Hash Table, Sorting
- Maximum Subarray Min-Product Array, Stack, Monotonic Stack
- Minimum Operations to Make All Array Elements Equal Array, Binary Search, Sorting
- Minimum Absolute Difference Queries Array, Hash Table, Binary Search
- Maximum Side Length of a Square with Sum Less than or Equal to Threshold Array, Binary Search, Matrix
- Maximum White Tiles Covered by a Carpet Array, Sliding Window, Sorting
- Count of Interesting Subarrays Array, Hash Table
- Maximum Sum Obtained of Any Permutation Array, Greedy, Sorting
- Minimum Moves to Make Array Complementary Array, Hash Table
- Ways to Split Array Into Three Subarrays Array, Two Pointers, Binary Search
- Minimum Penalty for a Shop String
- Minimum Amount of Time to Collect Garbage Array, String
- Shifting Letters II Array, String
- Maximize Number of Subsequences in a String String, Greedy
- Plates Between Candles Array, String, Binary Search
- Change Minimum Characters to Satisfy One of Three Conditions Hash Table, String, Counting
- Sum of Distances Array, Hash Table
- Count the Number of Beautiful Subarrays Array, Hash Table, Bit Manipulation
- Rearrange Array to Maximize Prefix Score Array, Greedy, Sorting
- Minimize Maximum of Array Array, Binary Search, Greedy
- Find All Good Indices Array, Dynamic Programming
- Number of Ways to Split Array Array
- Minimum Average Difference Array
- Grid Game Array, Matrix
- Maximum Absolute Sum of Any Subarray Array, Dynamic Programming
- Sum of Absolute Differences in a Sorted Array Array, Math
- Ways to Make a Fair Array Array
- Make Sum Divisible by P Array, Hash Table
- Number of Sub-arrays With Odd Sum Array, Math, Dynamic Programming
- Maximum Sum of Two Non-Overlapping Subarrays Array, Dynamic Programming, Sliding Window
- 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 (33)
- Stamping the Grid Array, Greedy, Matrix
- Maximum Number of Ways to Partition an Array Array, Hash Table, Counting
- Smallest Rotation with Highest Score Array
- Find the Original Typed String II String, Dynamic Programming
- Find the Count of Monotonic Pairs I Array, Math, Dynamic Programming
- Count Increasing Quadruplets Array, Dynamic Programming, Binary Indexed Tree
- Delivering Boxes from Storage to Ports Array, Dynamic Programming, Segment Tree
- K Inverse Pairs Array Dynamic Programming
- Number of Beautiful Partitions String, Dynamic Programming
- Minimum Time to Remove All Cars Containing Illegal Goods String, Dynamic Programming
- Number of Ways of Cutting a Pizza Array, Dynamic Programming, Matrix
- Minimum Cost to Merge Stones Array, Dynamic Programming
- Maximum Sum of 3 Non-Overlapping Subarrays Array, Dynamic Programming, Sliding Window
- My Calendar III Binary Search, Segment Tree, Ordered Set
- Sum of Total Strength of Wizards Array, Stack, Monotonic Stack
- Maximize the Minimum Powered City Array, Binary Search, Greedy
- Number of Flowers in Full Bloom Array, Binary Search, Sorting
- Apply Operations to Maximize Frequency Score Array, Sliding Window, Sorting
- Maximum Fruits Harvested After at Most K Steps Array, Binary Search, Sliding Window
- Count Subarrays With Score Less Than K Array, Binary Search, Sliding Window
- Count Subarrays With Median K Array, Hash Table
- Sum of Floored Pairs Array, Math, Binary Search
- Find Longest Awesome Substring String, Hash Table, Bit Manipulation
- 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 129 problems on prefix sum
- Google 109 problems on prefix sum
- Meta 17 problems on prefix sum
- Microsoft 15 problems on prefix sum
- Uber 10 problems on prefix sum
- Adobe 8 problems on prefix sum
- TCS 6 problems on prefix sum
- Sprinklr 4 problems on prefix sum
- Zoho 3 problems on prefix sum
- Arcesium 2 problems on prefix sum
- Capgemini 2 problems on prefix sum
- Directi 2 problems on prefix sum
Next topic: Sorting