Skip to main content

Prefix Sum

Precompute a running total once, and every range sum after that is a subtraction instead of a rescan. prefix[i] holds the sum of everything up to and including index i, so the sum of any range [left, right] is just prefix[right] - prefix[left-1] - one lookup, no matter how wide the range. The same idea runs in either direction: a forward pass answers "what's the total up to here", a backward pass answers "what's the total from here to the end".

Precomputed Prefix Array​

Build the running total once in the constructor, then answer every query in O(1) by subtracting two prefix sums instead of rescanning the range each time.

303. Range Sum Query - Immutable​

Easy·
FIG. 303 RANGE SUM QUERY IMMUTABLE● INTERACTIVE
visualization loads as you reach it
class NumArray:
 
def __init__(self, nums: List[int]):
self.prefix_sum = []
active = 0
for i in nums:
active += i
self.prefix_sum.append(active)
 
def sumRange(self, left: int, right: int) -> int:
if left == 0:
return self.prefix_sum[right]
return self.prefix_sum[right] - self.prefix_sum[left - 1]
 
 
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)

Suffix Sum​

The mirror image: nothing is precomputed for reuse, but each position's update implicitly covers everything from it to the end (or start) of the array, so a single accumulating pass in that direction reconstructs the total directly, without ever building a difference array.

848. Shifting Letters​

Medium·
FIG. 848 SHIFTING LETTERS● INTERACTIVE
visualization loads as you reach it
class Solution:
def shiftingLetters(self, s: str, shifts: List[int]) -> str:
ans = collections.deque()
alphabets = "abcdefghijklmnopqrstuvwxyz"
alphabet_map = {j: i for i, j in enumerate(alphabets)}
active = 0
for i in range(len(s) - 1, -1, -1):
active += shifts[i]
char = alphabets[(alphabet_map[s[i]] + active) % 26]
ans.appendleft(char)
return "".join(ans)

Prefix Meets Suffix​

When a position's answer depends on both sides of it, neither direction alone is enough - build the forward pass and the backward pass, then read one value from each. The pair of arrays turns a per-index rescan of the whole array into two lookups.

238. Product of Array Except Self​

Medium·
2 Approaches
FIG. 238 PRODUCT OF ARRAY EXCEPT SELF PREFIX SUFFIX● INTERACTIVE
visualization loads as you reach it
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
prefix = [0] * n
prefix[0] = nums[0]
for i in range(1, n):
prefix[i] = prefix[i - 1] * nums[i]
suffix = [0] * n
suffix[-1] = nums[-1]
for i in range(n - 2, -1, -1):
suffix[i] = suffix[i + 1] * nums[i]
ans = [0] * n
ans[0] = suffix[1]
ans[-1] = prefix[-2]
for i in range(1, n - 1):
ans[i] = prefix[i - 1] * suffix[i + 1]
return ans