Advanced · Module 14 · Lesson 3 of 4

Prefix sums

Store the running total at every position once, and the sum of any range becomes one subtraction. Combined with a hash map, prefix sums count subarrays with a given sum, even with negative numbers.

ProAbout 14 minutes

By the end you can

Build a prefix-sum array and answer range-sum queries in O(1)
Count subarrays with a target sum using prefix sums and a hash map
Extend the idea to two dimensions, to products, and to range updates with difference arrays

Builds on Sliding window.

01 · A question first

A dashboard asks for total sales between two dates, thousands of times a minute, over ten years of daily figures. Adding up the days for each request is O(n) every time. One extra array makes every request two lookups and a subtraction. What does that array store?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

Precompute once, answer instantly
Counting subarrays with a given sum
A worked example
Other prefix operations
Two dimensions
Range updates with difference arrays
When the data changes
Pseudocode & Multi-Language Implementations (C++, Java, Python)

See plans Already a member? Sign in

03 · Practice

Practice · easy · LeetCodeRange sum query: immutableAnswer many range-sum queries on a fixed array in O(1) each with a prefix-sum array.Practice · medium · LeetCodeSubarray sum equals KCount the subarrays whose sum is exactly k, even with negative numbers, using prefix sums and a hash map.Practice · medium · LeetCodeProduct of array except selfReturn, for each index, the product of all other elements, with prefix and suffix products and no division.

Asked in interviews

Count the subarrays that sum to k, when values can be negative

Something wrong with this lesson? Report a problem