Prefix Sum

Precompute running totals so the sum of any range can be answered instantly instead of adding it up every time.

Prefix Sum Practice Problems

Easy

2 problems

109
Running Sum of 1d Array
Return a new array where each element is the sum of all elements up to that point.
easy
110
Find Pivot Index
Find the index where the sum of numbers to the left equals the sum of numbers to the right.
easy

Medium

6 problems

111
Subarray Sum Equals K
Count how many contiguous subarrays add up to a target value.
medium
112
Product of Array Except Self
Return an array where each element is the product of every other element, without using division.
medium
113
Contiguous Array
Find the longest contiguous subarray with an equal number of 0s and 1s.
medium
114
Range Sum Query 2D - Immutable
Answer repeated queries for the sum of values inside a rectangle of a fixed grid.
medium
266
Continuous Subarray Sum
Check whether a contiguous subarray of size at least two sums to a multiple of k.
medium
267
Maximum Size Subarray Sum Equals k
Find the longest contiguous subarray that sums to exactly k.
medium

Hard

1 problems

115
Count of Range Sum
Count how many contiguous subarray sums fall within a given range.
hard

Last updated 12 September 2026

Related concepts

Topic	Description
Kadane's Algorithm	Track the best running sum ending at each position to find the maximum sum of a contiguous subarray in one pass.
Hash Tables	Key-to-value lookup in average O(1) via hashing into buckets.
Sliding Window	Solve fixed-window problems: maximum sum of k elements, moving averages, and O(n) updates as the window slides.
Two Pointers	Scan a sorted array or string from both ends at once to find pairs, remove duplicates, or reverse data in O(n).
Binary Search	Cut a sorted range in half on every step to find a value or boundary in O(log n) instead of checking one by one.
Depth-First Search	Explore as far as possible down one path before backtracking, used to walk trees, graphs, and grids.