Prefix Sums and Running Totals
Build prefix-sum arrays to answer range-sum queries in O(1) and apply the technique to subarray problems like maximum-sum subarray.
Prefix Sums and Running Totals is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
The Range-Sum Problem
Given an array nums, you need to answer many queries of the form: what is the sum of elements from index i to index j? Computing each query naively takes O(n) time, so k queries cost O(n×k). With a prefix sum array, you precompute a running total in O(n) and then answer each query in O(1). This is one of the most widely used pre-computation techniques in interviews.
# Naive: O(n) per query
def range_sum_naive(nums, i, j):
return sum(nums[i:j+1])
nums = [1, 3, 5, 7, 9]
print(range_sum_naive(nums, 1, 3)) # 3+5+7 = 15
print(range_sum_naive(nums, 0, 4)) # 1+3+5+7+9 = 25
# For 1000 queries, this takes 5000 operationsBuilding the Prefix Sum Array
Define prefix[i] as the sum of nums[0] through nums[i-1] (one extra slot, zero-indexed offset of 1 makes boundary cases cleaner). Build it in O(n) with one pass: prefix[i] = prefix[i-1] + nums[i-1]. Then a range query sum(i, j) becomes prefix[j+1] - prefix[i]: a single subtraction costing O(1).
def build_prefix(nums):
n = len(nums)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i+1] = prefix[i] + nums[i]
return prefix
def range_sum(prefix, i, j):
return prefix[j+1] - prefix[i] # O(1)
nums = [1, 3, 5, 7, 9]
pre = build_prefix(nums)
print(pre) # [0, 1, 4, 9, 16, 25]
print(range_sum(pre, 1, 3)) # 9 - 1 = 8? Wait: 3+5+7=15
# Hmm: prefix[4]-prefix[1] = 16-1 = 15 correct
print(range_sum(pre, 1, 3)) # 15Subarray Sum Equals K
Finding the number of subarrays with sum equal to k is a classic hash map + prefix sum problem. The key insight: subarray sum from i to j equals prefix[j] - prefix[i-1]. If we want this equal to k, then prefix[i-1] = prefix[j] - k. As we scan left-to-right maintaining a running prefix sum, we look up how many times current_sum - k has appeared before, counting all valid subarrays in O(n) total.
from collections import defaultdict
def subarray_sum_k(nums, k):
count = 0
current = 0
freq = defaultdict(int)
freq[0] = 1 # empty prefix
for n in nums:
current += n
count += freq[current - k] # how many prior sums give diff=k
freq[current] += 1
return count
print(subarray_sum_k([1, 1, 1], 2)) # 2
print(subarray_sum_k([1, 2, 3], 3)) # 2 ([1,2] and [3])Maximum Subarray Sum with Prefix
The maximum subarray sum can be framed as a prefix sum problem: for each index j, we want to maximise prefix[j] - prefix[i] over all i < j. The optimal i at each j is the minimum prefix sum seen so far. Scanning left to right while tracking min_prefix gives O(n) time. This is equivalent to Kadane's algorithm viewed through the prefix-sum lens.
def max_subarray_prefix(nums):
max_sum = float('-inf')
min_pre = 0 # prefix[0] = 0
current = 0
for n in nums:
current += n
max_sum = max(max_sum, current - min_pre)
min_pre = min(min_pre, current)
return max_sum
print(max_subarray_prefix([-2,1,-3,4,-1,2,1,-5,4]))
# 6 (same as Kadane's)
print(max_subarray_prefix([-1,-2,-3]))
# -12D Prefix Sums for Grid Queries
Prefix sums extend to 2D grids. Define P[i][j] as the sum of all elements in the rectangle from (0,0) to (i-1,j-1). Build it with the inclusion-exclusion formula: P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1]. Then any rectangle sum query (r1,c1) to (r2,c2) is answered in O(1) using four lookups.
def build_2d_prefix(grid):
R, C = len(grid), len(grid[0])
P = [[0]*(C+1) for _ in range(R+1)]
for r in range(1, R+1):
for c in range(1, C+1):
P[r][c] = (P[r-1][c] + P[r][c-1]
- P[r-1][c-1] + grid[r-1][c-1])
return P
def rect_sum(P, r1, c1, r2, c2):
return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]
grid = [[3,0,1,4],[5,6,3,2],[1,2,0,1]]
P = build_2d_prefix(grid)
print(rect_sum(P, 0, 0, 1, 1)) # 3+0+5+6 = 14Running Total for Equilibrium Index
The equilibrium index is the position where the sum of elements to the left equals the sum to the right. Precompute total sum, then scan left maintaining a running left sum. The right sum is total - left_sum - nums[i]. Check equality in O(1) per index, giving O(n) overall. This demonstrates how a running total replaces two separate prefix-sum arrays.
def find_pivot_index(nums):
total = sum(nums)
left_sum = 0
for i, n in enumerate(nums):
# right_sum = total - left_sum - nums[i]
if left_sum == total - left_sum - n:
return i
left_sum += n
return -1
print(find_pivot_index([1, 7, 3, 6, 5, 6])) # 3
print(find_pivot_index([1, 2, 3])) # -1Product Array Except Self
Given an array, return an array where each element is the product of all others. Division is not allowed. Use a prefix product and suffix product: result[i] = (product of all elements before i) × (product of all elements after i). Build the prefix products in a left-to-right pass, then multiply in suffix products in a right-to-left pass using a running variable — no extra array needed for the suffix.
def product_except_self(nums):
n = len(nums)
result = [1] * n
# Left pass: result[i] = product of nums[:i]
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# Right pass: multiply in product of nums[i+1:]
suffix = 1
for i in range(n-1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
print(product_except_self([1, 2, 3, 4]))
# [24, 12, 8, 6] O(n) time, O(1) extra spacePrefix Sum with Modulo
Some problems ask for the number of subarrays whose sum is divisible by k. Using prefix sums modulo k: if prefix[j] % k == prefix[i] % k, then sum(i+1..j) is divisible by k. A hash map counting each remainder value as we scan gives O(n) time. The key initialisation is freq[0] = 1 to handle subarrays starting at index 0.
from collections import defaultdict
def subarray_div_by_k(nums, k):
freq = defaultdict(int)
freq[0] = 1
current = 0
count = 0
for n in nums:
current = (current + n) % k
count += freq[current]
freq[current] += 1
return count
print(subarray_div_by_k([4, 5, 0, -2, -3, 1], 5))
# 7 (seven subarrays divisible by 5)Difference Array for Range Updates
A difference array is the inverse of a prefix sum. Given an array, precompute diff[i] = nums[i] - nums[i-1]. Adding x to a range [l, r] requires only two O(1) operations on the diff array: diff[l] += x and diff[r+1] -= x. After all updates, reconstruct the result array with a single prefix-sum pass. This turns k range-updates from O(n×k) to O(n + k).
def apply_range_updates(n, updates):
# updates: list of (l, r, val)
diff = [0] * (n + 1)
for l, r, val in updates:
diff[l] += val
diff[r+1] -= val
# Reconstruct with prefix sum
result = []
running = 0
for i in range(n):
running += diff[i]
result.append(running)
return result
# Add 3 to [1,3], add 1 to [0,2]
print(apply_range_updates(5, [(1,3,3),(0,2,1)]))
# [1, 4, 4, 3, 0]Prefix Sum in Interview Problems
Prefix sums appear across many problem categories:
- Range queries — subarray sum, rectangle sum
- Subarray counting — sum equals k, divisible by k
- Product problems — product except self
- Equilibrium — find pivot index
- Range updates — difference array
# Template: prefix sum + hash map for subarray problems
from collections import defaultdict
def subarray_count_template(nums, target):
"""
Count subarrays with property involving prefix sums.
Adapt 'target' and lookup condition for each problem.
"""
freq = defaultdict(int)
freq[0] = 1 # empty prefix at sum=0
current = 0
count = 0
for n in nums:
current += n
count += freq[current - target] # adjust per problem
freq[current] += 1
return count
print(subarray_count_template([1,2,3,2,1], 3)) # 3Running Sum and Running Maximum
Beyond prefix sums, many problems use a running maximum or running minimum maintained with a single variable. Best-time-to-buy-stock uses a running minimum price; trapping rain water from the left uses a running maximum left height. These patterns require only one scan and O(1) extra space, making them the gold standard for both time and space efficiency.
def max_profit(prices):
# Running minimum buy price
min_price = float('inf')
max_prof = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_prof:
max_prof = price - min_price
return max_prof
def left_max_array(heights):
# Running max from left for trapping rain water
n = len(heights)
left_max = [0] * n
left_max[0] = heights[0]
for i in range(1, n):
left_max[i] = max(left_max[i-1], heights[i])
return left_max
print(max_profit([7,1,5,3,6,4])) # 5Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: prefix sums transform O(n) range queries into O(1) lookups by precomputing cumulative sums in a single O(n) pass, combining prefix sums with a hash map enables O(n) solutions for counting subarrays with a given sum or divisibility property, and difference arrays are the inverse: they allow O(1) range updates with a single prefix-sum reconstruction pass at the end. Next up we tackle the two-pointer technique starting with opposite-ends pointers.
Frequently asked questions
Is the “Prefix Sums and Running Totals” lesson free?
Yes — the full text of “Prefix Sums and Running Totals” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Prefix Sums and Running Totals”?
Build prefix-sum arrays to answer range-sum queries in O(1) and apply the technique to subarray problems like maximum-sum subarray. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Prefix Sums and Running Totals” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Array Basics and In-Place Operations
- Prefix Sums and Running Totals
- Two Pointers: Opposite Ends
- Two Pointers: Slow and Fast