Prefix Sum
38 problems
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.
- 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