PrefixAlgorithmaka reverse prefix sum, right-to-left cumulative sum, suffix array of sums

Suffix Sum

Precompute S[i] = a[i] + … + a[n-1] by scanning right to left, so questions about "everything after index i" are answered in O(1) — usually paired with a prefix sum.

▶ VisualizePattern: Prefix SumPractice (2)
Progress

Overview

A suffix sum is the mirror image of a Prefix Sum: S[n] = 0 and S[i] = a[i] + S[i+1]. It answers "what is the total from index i to the end" in O(1). Mathematically S[i] = total − P[i], so a suffix array is never strictly necessary when a prefix array exists — but computing it directly is often clearer, and for non-invertible aggregates (suffix max, suffix min, suffix product with zeros) there is no total − P[i] shortcut and the explicit right-to-left scan is the only option.

The typical use is a split-point problem: for each index i, combine a fact about a[0..i) (from a prefix pass) with a fact about a[i..n) (from a suffix pass). Product of Array Except Self, Trapping Rain Water (prefix max and suffix max), and "best time to buy and sell with one transaction" all have this shape.

contiguousright-to-leftcumulativeO(1) querypivot

Intuition

A mental model before the formal terms.

Reading a book from the back: instead of asking "how many pages have I read so far", ask "how many pages are left". Each step backward adds one page to the remaining count. Now, at any bookmark, you know both what came before (prefix) and what comes after (suffix) without flipping through the rest.

How it works

  1. Allocate S of length n + 1 with S[n] = 0.
  2. For i from n − 1 down to 0: S[i] = a[i] + S[i+1].
  3. Sum of a[i..n-1] is S[i]; sum of a[l..r] is S[l] − S[r+1].
  4. Split-point pattern: compute prefix aggregate L[i] over a[0..i) and suffix aggregate R[i] over a(i..n), then evaluate combine(L[i], R[i]) for each i and take the best. For products this yields the answer to Product of Array Except Self without division.
  5. Space optimization: build only the suffix array, then sweep left to right maintaining the prefix aggregate in a single variable.

Why it works

Telescoping in reverse: S[l] − S[r+1] = (a[l] + … + a[n-1]) − (a[r+1] + … + a[n-1]) = a[l] + … + a[r]. The sentinel S[n] = 0 handles r = n − 1 without a special case.

Split-point correctness: the quantity "everything except index i" decomposes exactly into "everything before i" and "everything after i", and both parts are independent of each other. Computing each part with its own cumulative scan means every element contributes to each side in O(1) amortized, so all n split points are evaluated in O(n) instead of O(n²).

For non-invertible aggregates like max, a suffix scan works because max(a[i..n)) = max(a[i], max(a[i+1..n))) — the recurrence only needs the next suffix value, never the removal of an element.

Recognition

How to tell a problem wants this.

  • "For each index, compute something about the elements to its right" / "after i" / "remaining".
  • "Except self", "excluding the current element", "split the array into two non-empty parts and maximize/minimize" — combine a prefix and a suffix pass.
  • "Product of array except self without using division" — division would undo a prefix product, but zeros break it; prefix × suffix products avoid it entirely.
  • Trapping Rain Water and similar: water at i depends on the maximum to the left and the maximum to the right.
  • "Minimum of the right side", "does a larger element exist to the right" — suffix max/min.
“sum of subarray” → Prefix Sum

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Prefix Sum visualization.

a
3
0
1
1
4
2
1
3
5
4
9
5
2
6
6
7
P (prefix sums)
0
0
1/13Build P where P[i] is the sum of the first i elements. P[0] = 0 (empty prefix) so every query has a clean left endpoint.
Being addedQueried rangePrefix entries usedAnswer
PseudocodeLearn Prefix Sum →
1P[0] = 0
2for i in 0 .. n-1: P[i+1] = P[i] + a[i]
3query(l, r) = P[r+1] - P[l]
Variables
n8
Complexity
best O(n)
avg O(n)
worst O(n)
space O(n)
Speed

Pseudocode

1S = array of n + 1 zeros
2for i in n-1 down to 0: S[i] = a[i] + S[i+1]
3# split point: best combine(prefix(a[0..i)), suffix(a[i..n)))
4best = -inf, left = identity
5for i in 0..n-1:
6  best = max(best, combine(left, S[i]))
7  left = left + a[i]
8return best

Implementations

1# Suffix sums + the split-point pattern (Product of Array Except Self)
2 
31 · Build suffix sums right to left with sentinel S[n] = 0
4def suffix_sums(a: list[int]) -> list[int]:
5    s = [0] * (len(a) + 1)
6    for i in range(len(a) - 1, -1, -1):
7        s[i] = a[i] + s[i + 1]
8    return s  # sum of a[i..n-1] is s[i]; sum of a[l..r] is s[l] - s[r+1]
9 
10 
11# Product of Array Except Self: out[i] = product of all a[j], j != i (no division)
12def product_except_self(a: list[int]) -> list[int]:
13    n = len(a)
142 · Prefix products of a[0..i) go straight into the output
15    out = [1] * n
16    for i in range(1, n):
17        out[i] = out[i - 1] * a[i - 1]
183 · Right-to-left sweep folds in the suffix product of a(i..n)
19    suffix = 1
20    for i in range(n - 1, -1, -1):
21        out[i] *= suffix
22        suffix *= a[i]
234 · Each slot now holds prefix(a[0..i)) * suffix(a(i..n))
24    return out
Walkthrough
  1. range(len(a) - 1, -1, -1) iterates indices right to left in O(1) memory — no reversed copy of the array is made.
  2. The sentinel s[n] = 0 is part of the [0] * (len(a) + 1) allocation, so the recurrence needs no boundary check.
  3. Python ints are arbitrary precision: neither the suffix sums nor the products can overflow, only slow down for huge values.
  4. In product_except_self, out is both the prefix-product array and the final answer; suffix is a single running variable.
  5. Tuple-free, slice-free loops keep the extra memory at O(1) beyond the output.
Complexity (this implementation)
time O(n) · space O(n)

O(1) extra beyond the output. a[::-1] or list(reversed(a)) would copy O(n) — the index range avoids that.

Language notes
  • a[::-1] builds a full reversed *copy* (O(n) time and memory); reversed(a) is a lazy iterator; range(n - 1, -1, -1) iterates indices — prefer the latter two for scans.
  • itertools.accumulate(reversed(a), initial=0) computes suffix sums lazily; reversing its output back costs one O(n) list copy.
  • math.prod(a) computes a whole-array product, but division by a[i] breaks on zeros — the prefix/suffix form avoids division entirely.
Common mistakes in this language
  • Writing for x in a[::-1] in a memory-constrained problem and paying an O(n) copy per call.
  • Using range(len(a) - 1, 0, -1) and skipping index 0.
  • Dividing the total product by a[i] — raises ZeroDivisionError on zeros and is usually banned by the problem.
Language differences that matter here
  • Overflow of suffix sums (n * max|a|): C++ must accumulate in long long (int overflow is UB); JS/TS doubles are exact only to 2^53; Python ints never overflow.
  • C++ trap: std::partial_sum accumulates in the input's value_type, so summing a vector<int> into a vector<long long> still overflows in int — use std::inclusive_scan with a 0LL init or a manual loop.
  • Reverse iteration cost: Python a[::-1] copies O(n) while range(n-1, -1, -1) / reversed(a) do not; JS a.reverse() mutates in place (toReversed() copies); C++ rbegin()/rend() are free views.
  • Reverse loop counters: a C++ size_t loop variable wraps below zero and never terminates — use a signed index; JS/TS/Python have no unsigned trap.
  • Uninitialised slots: JS new Array(n) has holes that arithmetic turns into NaN (always .fill()); C++ vector(n, 0) and Python [0] * n are zeroed by construction.

Complexity

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(n)

O(1) extra space when the output array doubles as the prefix array and the suffix is a running variable.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Per-index questions about the elements after i.
  • Split-point optimizations that need both a left and a right aggregate.
  • Non-invertible aggregates (max, min, gcd, product with zeros) where total − prefix is unavailable.
  • Avoiding division in product problems.
Avoid it when
  • A Prefix Sum already exists and the aggregate is invertible — S[i] = total − P[i], no second array needed.
  • The array changes between queries — use a Fenwick Tree or Segment Tree.
  • Only one suffix query is asked — a direct loop is simpler.

Alternatives

Prefix SumSegment TreeMonotonic Stack

Common mistakes

  • Off-by-one on the sentinel: S needs length n + 1 with S[n] = 0, otherwise S[n-1] is uninitialized or the loop reads S[n] out of bounds.
  • Using division for Product Except Self and crashing (or producing wrong results) on zeros.
  • Building both prefix and suffix arrays when a single running variable would meet an O(1) extra-space requirement.
  • Confusing "suffix sum" with the string-algorithm Suffix Array — unrelated structures with similar names.

Interview patterns

  • Product of Array Except Self — prefix product in the output array, suffix product in a variable.
  • Trapping Rain Water with leftMax[i] and rightMax[i] arrays (then optimized to Two Pointers (Opposite Ends)).
  • Best Time to Buy and Sell Stock: suffix max of prices minus each price (or prefix min).
  • Minimum split such that left sum ≥ right sum / "number of ways to split array" with prefix vs suffix comparison.
  • Find Pivot Index: P[i] == S[i+1].
Interview questions on this
Mock interviews

Example problems

Trapping Rain WaterhardProduct of Array Except Selfmedium