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·
Explanation

prefix_sum[i] is built once in the constructor to hold the running total of nums[0..i]. Once that's in place, the sum of any range [left, right] is just prefix_sum[right] with everything before left subtracted back out - prefix_sum[left-1] - except when left is 0, where there's nothing before it to subtract, so prefix_sum[right] is already the whole answer.

Analysis
Time
O(n)
  • __init__ builds prefix_sum with a single O(n) pass over nums.
  • sumRange is O(1) - one or two array lookups and a subtraction, regardless of how wide [left, right] is.
Space
O(n)
  • prefix_sum holds one running total per element of nums.
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·
Explanation

Unlike [[2381. Shifting Letters II]], there's no explicit [start, end] range here - shifts[i] means "shift every character from 0 up to i", so index i's total shift is the sum of shifts[i:]. Walking i from the last index down to 0 and accumulating active += shifts[i] builds exactly that suffix sum as it goes, so by the time s[i] is processed, active already holds the full shift owed to it. Each character is looked up in alphabet_map, shifted by active positions, wrapped with %26, and pushed onto the front of ans since the walk runs backward.

Analysis
Time
O(2n + 26)
  • The backward scan over s and the final "".join(ans) are each a separate O(n) pass - 2n combined, where n = len(s).
  • alphabet_map is built once from the 26-character alphabet, O(26), independent of n.
Space
O(n + 26)
  • ans holds all n characters before the join.
  • alphabet_map holds exactly the 26 letters of the alphabet, O(26), independent of n.
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)