Prefix Sum

A prefix-sum array precomputes running totals so the sum of any range is answered in O(1) by subtracting two endpoints. Use it when you face many range-sum queries, or to count subarrays whose sum hits a target.

7 LeetCode problems solved with the Prefix Sum pattern. Practice them with spaced repetition so the pattern sticks.

• Car PoolingMEDIUM · O(n + M)
• Find Pivot IndexEASY · O(n)
• Find the Highest AltitudeEASY · O(n)
• Kids With the Greatest Number of CandiesEASY · O(n)
• Product of Array Except SelfMEDIUM · O(n)
• Range Sum Query 2D - ImmutableMEDIUM · O(m*n) to build, O(1) per query
• Subarray Sum Equals KMEDIUM · O(n)