Prefix Sum LeetCode Problems: All 157, With Python Solutions
Every problem in this library that LeetCode tags Prefix Sum — 157 in total, 139 of them with a complete Python solution, a worked example and the time and space complexity of the approach.
- 157 problems
- 14 Easy
- 102 Medium
- 41 Hard
How Prefix Sum problems are solved
A tag names the subject, not the method. These pattern hubs cover the techniques that actually solve Prefix Sum problems — each one explains the approach, gives a Python template and states its complexity.
- Prefix Sum — Precompute running totals once so any range query becomes a single subtraction.
Prefix Sum problems by difficulty
Problems with a complete Python solution are listed first, then by ascending problem number.
Easy (14)
| # | Problem | Difficulty | Topics |
|---|---|---|---|
| 303 | Range Sum Query - Immutable | Easy | Design, Array, Prefix Sum |
| 724 | Find Pivot Index | Easy | Array, Prefix Sum |
| 1413 | Minimum Value to Get Positive Step by Step Sum | Easy | Array, Prefix Sum |
| 1422 | Maximum Score After Splitting a String | Easy | String, Prefix Sum |
| 1480 | Running Sum of 1d Array | Easy | Array, Prefix Sum |
| 1588 | Sum of All Odd Length Subarrays | Easy | Array, Math, Prefix Sum |
| 1732 | Find the Highest Altitude | Easy | Array, Prefix Sum |
| 1854 | Maximum Population Year | Easy | Array, Counting, Prefix Sum |
| 1893 | Check if All the Integers in a Range Are Covered | Easy | Array, Hash Table, Prefix Sum |
| 1991 | Find the Middle Index in Array | Easy | Array, Prefix Sum |
| 2389 | Longest Subsequence With Limited Sum | Easy | Greedy, Array, Binary Search +2 |
| 2485 | Find the Pivot Integer | Easy | Math, Prefix Sum |
| 2574 | Left and Right Sum Differences | Easy | Array, Prefix Sum |
| 2848 | Points That Intersect With Cars | Easy | Array, Hash Table, Prefix Sum |
Medium (102)
| # | Problem | Difficulty | Topics |
|---|---|---|---|
| 209 | Minimum Size Subarray Sum | Medium | Array, Binary Search, Prefix Sum +1 |
| 238 | Product of Array Except Self | Medium | Array, Prefix Sum |
| 304 | Range Sum Query 2D - Immutable | Medium | Design, Array, Matrix +1 |
| 497 | Random Point in Non-overlapping Rectangles | Medium | Reservoir Sampling, Array, Math +4 |
| 523 | Continuous Subarray Sum | Medium | Array, Hash Table, Math +1 |
| 525 | Contiguous Array | Medium | Array, Hash Table, Prefix Sum |
| 528 | Random Pick with Weight | Medium | Array, Math, Binary Search +2 |
| 560 | Subarray Sum Equals K | Medium | Array, Hash Table, Prefix Sum |
| 713 | Subarray Product Less Than K | Medium | Array, Binary Search, Prefix Sum +1 |
| 731 | My Calendar II | Medium | Design, Segment Tree, Array +3 |
| 813 | Largest Sum of Averages | Medium | Array, Dynamic Programming, Prefix Sum |
| 848 | Shifting Letters | Medium | Array, String, Prefix Sum |
| 930 | Binary Subarrays With Sum | Medium | Array, Hash Table, Prefix Sum +1 |
| 974 | Subarray Sums Divisible by K | Medium | Array, Hash Table, Prefix Sum |
| 1004 | Max Consecutive Ones III | Medium | Array, Binary Search, Prefix Sum +1 |
| 1094 | Car Pooling | Medium | Array, Prefix Sum, Sorting +2 |
| 1109 | Corporate Flight Bookings | Medium | Array, Prefix Sum |
| 1124 | Longest Well-Performing Interval | Medium | Stack, Array, Hash Table +2 |
| 1140 | Stone Game II | Medium | Array, Math, Dynamic Programming +2 |
| 1177 | Can Make Palindrome from Substring | Medium | Bit Manipulation, Array, Hash Table +2 |
| 1208 | Get Equal Substrings Within Budget | Medium | String, Binary Search, Prefix Sum +1 |
| 1248 | Count Number of Nice Subarrays | Medium | Array, Hash Table, Math +2 |
| 1292 | Maximum Side Length of a Square with Sum Less than or Equal to Threshold | Medium | Array, Binary Search, Matrix +1 |
| 1310 | XOR Queries of a Subarray | Medium | Bit Manipulation, Array, Prefix Sum |
| 1314 | Matrix Block Sum | Medium | Array, Matrix, Prefix Sum |
| 1352 | Product of the Last K Numbers | Medium | Design, Array, Math +2 |
| 1371 | Find the Longest Substring Containing Vowels in Even Counts | Medium | Bit Manipulation, Hash Table, String +1 |
| 1423 | Maximum Points You Can Obtain from Cards | Medium | Array, Prefix Sum, Sliding Window |
| 1442 | Count Triplets That Can Form Two Arrays of Equal XOR | Medium | Bit Manipulation, Array, Hash Table +2 |
| 1508 | Range Sum of Sorted Subarray Sums | Medium | Array, Two Pointers, Binary Search +2 |
| 1524 | Number of Sub-arrays With Odd Sum | Medium | Array, Math, Dynamic Programming +1 |
| 1546 | Maximum Number of Non-Overlapping Subarrays With Sum Equals Target | Medium | Greedy, Array, Hash Table +1 |
| 1589 | Maximum Sum Obtained of Any Permutation | Medium | Greedy, Array, Prefix Sum +1 |
| 1590 | Make Sum Divisible by P | Medium | Array, Hash Table, Prefix Sum |
| 1658 | Minimum Operations to Reduce X to Zero | Medium | Array, Hash Table, Binary Search +2 |
| 1664 | Ways to Make a Fair Array | Medium | Array, Prefix Sum |
| 1674 | Minimum Moves to Make Array Complementary | Medium | Array, Hash Table, Prefix Sum |
| 1685 | Sum of Absolute Differences in a Sorted Array | Medium | Array, Math, Prefix Sum |
| 1712 | Ways to Split Array Into Three Subarrays | Medium | Array, Two Pointers, Binary Search +1 |
| 1737 | Change Minimum Characters to Satisfy One of Three Conditions | Medium | Hash Table, String, Counting +1 |
| 1738 | Find Kth Largest XOR Coordinate Value | Medium | Bit Manipulation, Array, Divide and Conquer +5 |
| 1744 | Can You Eat Your Favorite Candy on Your Favorite Day? | Medium | Array, Prefix Sum |
| 1769 | Minimum Number of Operations to Move All Balls to Each Box | Medium | Array, String, Prefix Sum |
| 1829 | Maximum XOR for Each Query | Medium | Bit Manipulation, Array, Prefix Sum |
| 1838 | Frequency of the Most Frequent Element | Medium | Greedy, Array, Binary Search +3 |
| 1856 | Maximum Subarray Min-Product | Medium | Stack, Array, Prefix Sum +1 |
| 1871 | Jump Game VII | Medium | String, Dynamic Programming, Prefix Sum +1 |
| 1878 | Get Biggest Three Rhombus Sums in a Grid | Medium | Array, Math, Matrix +3 |
| 1894 | Find the Student that Will Replace the Chalk | Medium | Array, Binary Search, Prefix Sum +1 |
| 1895 | Largest Magic Square | Medium | Array, Matrix, Prefix Sum |
| 1915 | Number of Wonderful Substrings | Medium | Bit Manipulation, Hash Table, String +1 |
| 1930 | Unique Length-3 Palindromic Subsequences | Medium | Bit Manipulation, Hash Table, String +1 |
| 1943 | Describe the Painting | Medium | Array, Hash Table, Prefix Sum +1 |
| 2017 | Grid Game | Medium | Array, Matrix, Prefix Sum |
| 2024 | Maximize the Confusion of an Exam | Medium | String, Binary Search, Prefix Sum +1 |
| 2055 | Plates Between Candles | Medium | Array, String, Binary Search +1 |
| 2100 | Find Good Days to Rob the Bank | Medium | Array, Dynamic Programming, Prefix Sum |
| 2121 | Intervals Between Identical Elements | Medium | Array, Hash Table, Prefix Sum |
| 2145 | Count the Hidden Sequences | Medium | Array, Prefix Sum |
| 2171 | Removing Minimum Number of Magic Beans | Medium | Greedy, Array, Enumeration +2 |
| 2207 | Maximize Number of Subsequences in a String | Medium | Greedy, String, Prefix Sum |
| 2222 | Number of Ways to Select Buildings | Medium | String, Dynamic Programming, Prefix Sum |
| 2245 | Maximum Trailing Zeros in a Cornered Path | Medium | Array, Matrix, Prefix Sum |
| 2256 | Minimum Average Difference | Medium | Array, Prefix Sum |
| 2270 | Number of Ways to Split Array | Medium | Array, Prefix Sum |
| 2271 | Maximum White Tiles Covered by a Carpet | Medium | Greedy, Array, Binary Search +3 |
| 2381 | Shifting Letters II | Medium | Array, String, Prefix Sum |
| 2391 | Minimum Amount of Time to Collect Garbage | Medium | Array, String, Prefix Sum |
| 2406 | Divide Intervals Into Minimum Number of Groups | Medium | Greedy, Array, Two Pointers +3 |
| 2420 | Find All Good Indices | Medium | Array, Dynamic Programming, Prefix Sum |
| 2428 | Maximum Sum of an Hourglass | Medium | Array, Matrix, Prefix Sum |
| 2438 | Range Product Queries of Powers | Medium | Bit Manipulation, Array, Prefix Sum |
| 2439 | Minimize Maximum of Array | Medium | Greedy, Array, Binary Search +2 |
| 2483 | Minimum Penalty for a Shop | Medium | String, Prefix Sum |
| 2536 | Increment Submatrices by One | Medium | Array, Matrix, Prefix Sum |
| 2559 | Count Vowel Strings in Ranges | Medium | Array, String, Prefix Sum |
| 2587 | Rearrange Array to Maximize Prefix Score | Medium | Greedy, Array, Prefix Sum +1 |
| 2588 | Count the Number of Beautiful Subarrays | Medium | Bit Manipulation, Array, Hash Table +1 |
| 2602 | Minimum Operations to Make All Array Elements Equal | Medium | Array, Binary Search, Prefix Sum +1 |
| 2615 | Sum of Distances | Medium | Array, Hash Table, Prefix Sum |
| 2640 | Find the Score of All Prefixes of an Array | Medium | Array, Prefix Sum |
| 2680 | Maximum OR | Medium | Greedy, Bit Manipulation, Array +1 |
| 2731 | Movement of Robots | Medium | Brainteaser, Array, Prefix Sum +1 |
| 2772 | Apply Operations to Make All Array Elements Equal to Zero | Medium | Array, Prefix Sum |
| 2845 | Count of Interesting Subarrays | Medium | Array, Hash Table, Prefix Sum |
| 2875 | Minimum Size Subarray in Infinite Array | Medium | Array, Hash Table, Prefix Sum +1 |
| 2906 | Construct Product Matrix | Medium | Array, Matrix, Prefix Sum |
| 2947 | Count Beautiful Substrings I | Medium | Hash Table, Math, String +3 |
| 2971 | Find Polygon With the Largest Perimeter | Medium | Greedy, Array, Prefix Sum +1 |
| 253 | Meeting Rooms IIPremium | Medium | Greedy, Array, Two Pointers +3 |
| 325 | Maximum Size Subarray Sum Equals kPremium | Medium | Array, Hash Table, Prefix Sum |
| 370 | Range AdditionPremium | Medium | Array, Prefix Sum |
| 1983 | Widest Pair of Indices With Equal Range SumPremium | Medium | Array, Hash Table, Prefix Sum |
| 2021 | Brightest Position on StreetPremium | Medium | Array, Ordered Set, Prefix Sum +1 |
| 2083 | Substrings That Begin and End With the Same LetterPremium | Medium | Hash Table, Math, String +2 |
| 2219 | Maximum Sum Score of ArrayPremium | Medium | Array, Prefix Sum |
| 2237 | Count Positions on Street With Required BrightnessPremium | Medium | Array, Prefix Sum |
| 2489 | Number of Substrings With Fixed RatioPremium | Medium | Hash Table, Math, String +1 |
| 2505 | Bitwise OR of All Subsequence SumsPremium | Medium | Bit Manipulation, Brainteaser, Array +2 |
| 2838 | Maximum Coins Heroes Can CollectPremium | Medium | Array, Two Pointers, Binary Search +2 |
| 2950 | Number of Divisible SubstringsPremium | Medium | Hash Table, String, Counting +1 |
| 2955 | Number of Same-End SubstringsPremium | Medium | Array, Hash Table, String +2 |
Hard (41)
| # | Problem | Difficulty | Topics |
|---|---|---|---|
| 363 | Max Sum of Rectangle No Larger Than K | Hard | Array, Binary Search, Matrix +2 |
| 410 | Split Array Largest Sum | Hard | Greedy, Array, Binary Search +2 |
| 689 | Maximum Sum of 3 Non-Overlapping Subarrays | Hard | Array, Dynamic Programming, Prefix Sum +1 |
| 732 | My Calendar III | Hard | Design, Segment Tree, Binary Search +2 |
| 798 | Smallest Rotation with Highest Score | Hard | Array, Prefix Sum |
| 862 | Shortest Subarray with Sum at Least K | Hard | Queue, Array, Binary Search +4 |
| 903 | Valid Permutations for DI Sequence | Hard | String, Dynamic Programming, Prefix Sum |
| 995 | Minimum Number of K Consecutive Bit Flips | Hard | Bit Manipulation, Queue, Array +2 |
| 1000 | Minimum Cost to Merge Stones | Hard | Array, Dynamic Programming, Prefix Sum |
| 1074 | Number of Submatrices That Sum to Target | Hard | Array, Hash Table, Matrix +1 |
| 1420 | Build Array Where You Can Find The Maximum Exactly K Comparisons | Hard | Dynamic Programming, Prefix Sum |
| 1444 | Number of Ways of Cutting a Pizza | Hard | Memoization, Array, Dynamic Programming +2 |
| 1687 | Delivering Boxes from Storage to Ports | Hard | Segment Tree, Queue, Array +4 |
| 1703 | Minimum Adjacent Swaps for K Consecutive Ones | Hard | Greedy, Array, Prefix Sum +1 |
| 1862 | Sum of Floored Pairs | Hard | Array, Math, Binary Search +1 |
| 1872 | Stone Game VIII | Hard | Array, Math, Dynamic Programming +2 |
| 1889 | Minimum Space Wasted From Packaging | Hard | Array, Binary Search, Prefix Sum +1 |
| 2025 | Maximum Number of Ways to Partition an Array | Hard | Array, Hash Table, Counting +2 |
| 2106 | Maximum Fruits Harvested After at Most K Steps | Hard | Array, Binary Search, Prefix Sum +1 |
| 2132 | Stamping the Grid | Hard | Greedy, Array, Matrix +1 |
| 2209 | Minimum White Tiles After Covering With Carpets | Hard | String, Dynamic Programming, Prefix Sum |
| 2218 | Maximum Value of K Coins From Piles | Hard | Array, Dynamic Programming, Prefix Sum |
| 2234 | Maximum Total Beauty of the Gardens | Hard | Greedy, Array, Two Pointers +4 |
| 2251 | Number of Flowers in Full Bloom | Hard | Array, Hash Table, Binary Search +3 |
| 2281 | Sum of Total Strength of Wizards | Hard | Stack, Array, Prefix Sum +1 |
| 2302 | Count Subarrays With Score Less Than K | Hard | Array, Binary Search, Prefix Sum +1 |
| 2382 | Maximum Segment Sum After Removals | Hard | Union Find, Array, Ordered Set +1 |
| 2398 | Maximum Number of Robots Within Budget | Hard | Queue, Array, Binary Search +4 |
| 2448 | Minimum Cost to Make Array Equal | Hard | Greedy, Array, Binary Search +2 |
| 2478 | Number of Beautiful Partitions | Hard | String, Dynamic Programming, Prefix Sum |
| 2488 | Count Subarrays With Median K | Hard | Array, Hash Table, Prefix Sum |
| 2528 | Maximize the Minimum Powered City | Hard | Greedy, Queue, Array +3 |
| 2552 | Count Increasing Quadruplets | Hard | Binary Indexed Tree, Array, Dynamic Programming +2 |
| 2681 | Power of Heroes | Hard | Array, Math, Dynamic Programming +2 |
| 2968 | Apply Operations to Maximize Frequency Score | Hard | Array, Binary Search, Prefix Sum +2 |
| 2983 | Palindrome Rearrangement Queries | Hard | Hash Table, String, Prefix Sum |
| 548 | Split Array with Equal SumPremium | Hard | Array, Hash Table, Prefix Sum |
| 644 | Maximum Average Subarray IIPremium | Hard | Array, Binary Search, Prefix Sum |
| 1788 | Maximize the Beauty of the GardenPremium | Hard | Greedy, Array, Hash Table +1 |
| 2819 | Minimum Relative Loss After Buying ChocolatesPremium | Hard | Array, Binary Search, Prefix Sum +1 |
| 2949 | Count Beautiful Substrings II | Hard | Hash Table, Math, String +2 |
Keep exploring
All LeetCode topicsEvery tag with a page of its own, with the number of problems behind each.LeetCode patternsThe techniques themselves, with a Python template and complexity for each.Curated study listsBlind 75, NeetCode 150 and three more, grouped by pattern.Easy problemsStart here when the data structure is new rather than the problem.
Other topics
- Array1,569
- String672
- Hash Table588
- Math485
- Dynamic Programming481
- Sorting392
- Greedy346
- Depth-First Search289
- Binary Search253
- Database249
- Tree225
- Breadth-First Search223
- Matrix216
- Two Pointers201
- Bit Manipulation194
- Binary Tree174
- Heap (Priority Queue)163
- Stack157
- Simulation144
- Graph138
- Counting126
- Design122
- Sliding Window116
- Backtracking105
When the Prefix Sum problem arrives live
Stealth Interview is a desktop app for macOS and Windows. It reads the coding problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer is saying — while staying invisible to screen sharing.