Prefix Sum
38 problems · 26 with full explanations
5 Easy20 Medium2 Hard
A prefix sum array pre-computes cumulative values so any range query is answered in O(1). The classic sum of range [l, r] = prefix[r+1] - prefix[l]. 2D prefix sums extend this to matrix sub-rectangle queries. Combine with a hash map for "subarray sum equals k" problems.
How to practice
To practice Prefix Sum problems effectively, start with the Easy problems listed below, trace through each solution on paper, then re-implement without looking. When you can recognise the prefix sum pattern within 30 seconds of reading a new problem, move on to Medium difficulty. Use the related topic pages and our study guide for a structured progression.
Start here (Easy + explained)
All Prefix Sum problems
- 303.Range Sum Query - ImmutableEasy
- 304.Range Sum Query 2D - ImmutableMedium
- 862.Shortest Subarray with Sum at Least KHard
- 1248.Count Number of Nice SubarraysMedium
- 1310.XOR Queries of a SubarrayMedium
- 1371.Find the Longest Substring Containing Vowels in Even CountsMedium
- 1524.Number of Sub-arrays With Odd SumMedium
- 1590.Make Sum Divisible by PMedium
- 1769.Minimum Number of Operations to Move All Balls to Each BoxMedium
- 1829.Maximum XOR for Each QueryUnknown
- 1894.Find the Student that Will Replace the ChalkUnknown
- 1930.Unique Length-3 Palindromic SubsequencesMedium
- 2106.Maximum Fruits Harvested After at Most K StepsUnknown
- 2145.Count the Hidden SequencesUnknown
- 2185.Counting Words With a Given PrefixEasy
- 2270.Number of Ways to Split ArrayMedium
- 2302.Count Subarrays With Score Less Than KHard
- 2348.Number of Zero-Filled SubarraysMedium
- 2389.Longest Subsequence With Limited SumEasy
- 2406.Divide Intervals Into Minimum Number of GroupsMedium
- 2438.Range Product Queries of PowersUnknown
- 2536.Increment Submatrices by OneMedium
- 2559.Count Vowel Strings in RangesMedium
- 2640.Find the Score of All Prefixes of an ArrayMedium
- 2657.Find the Prefix Common Array of Two ArraysMedium
- 2683.Neighboring Bitwise XORMedium
- 2845.Count of Interesting SubarraysMedium
- 2906.Construct Product MatrixEasy
- 3070.Count Submatrices with Top-Left Element and Sum Less Than kEasy
- 3152.Special Array IIMedium
- 3212.Count Submatrices With Equal Frequency of X and YUnknown
- 3346.Maximum Frequency of an Element After Performing Operations IMedium
- 3347.Maximum Frequency of an Element After Performing Operations IIUnknown
- 3355.Zero Array Transformation IUnknown
- 3356.Zero Array Transformation IIUnknown
- 3381.Maximum Subarray Sum With Length Divisible by KMedium
- 3546.Equal Sum Grid Partition IUnknown
- 3548.Equal Sum Grid Partition IIUnknown