Prefix, Suffix, and One-Pass State

Stop recomputing the past

Many array problems ask a question at every position: what happened before here, after here, or between two boundaries? Re-scanning the same region for every answer creates quadratic work. A running summary lets later positions reuse earlier work.

Prefix sums and the leading zero

For nums = [3,1,4,2], define prefix[i] as the sum of the first i elements:

i          0  1  2  3   4
prefix     0  3  4  8  10

The leading zero is the additive identity: the sum of no elements. It keeps one formula valid even when a range starts at index zero.

function buildPrefix(nums: number[]): number[] {
  const prefix = [0]
  for (const value of nums) {
    prefix.push(prefix[prefix.length - 1] + value)
  }
  return prefix
}

function rangeSum(prefix: number[], left: number, right: number): number {
  return prefix[right + 1] - prefix[left]
}

Building the prefix costs O(n) time and O(n) space. Each range query then costs O(1). For q queries, the total changes from O(n · q) rescanning to O(n + q).

Left summary plus right summary

Product of Array Except Self (LeetCode #238) asks for an output where position i contains the product of every input value except nums[i]. It requires O(n) time and forbids division, which would also be awkward around zeroes.

The answer at each position splits naturally:

answer[i] = product left of i × product right of i

First write left products into the answer. Then walk backward while carrying one running right product:

function productExceptSelf(nums: number[]): number[] {
  const answer = Array<number>(nums.length).fill(1)

  let leftProduct = 1
  for (let i = 0; i < nums.length; i += 1) {
    answer[i] = leftProduct
    leftProduct *= nums[i]
  }

  let rightProduct = 1
  for (let i = nums.length - 1; i >= 0; i -= 1) {
    answer[i] *= rightProduct
    rightProduct *= nums[i]
  }
  return answer
}

Why multiply after using the running value? At index i, the summary must exclude nums[i]. Updating first would accidentally include the current element.

The answer array is required output. Beyond it, the optimized version uses only two running numbers, so auxiliary space is O(1) under the usual output-excluded convention.

Sometimes one summary is enough

Best Time to Buy and Sell Stock (LeetCode #121) gives daily prices and asks for the largest profit from buying once and selling on a later day. For each possible selling day, only one fact about the entire prefix matters: the cheapest earlier price.

function maxProfit(prices: number[]): number {
  let cheapest = Infinity
  let best = 0

  for (const price of prices) {
    cheapest = Math.min(cheapest, price)
    best = Math.max(best, price - cheapest)
  }
  return best
}

This is prefix thinking without a prefix array. When future positions need only one aggregate—minimum, maximum, count, sum, or best result—carry that value instead of storing every historical summary.

How this grows in Week 2

Prefix summaries become more powerful when stored in a Map. If a problem asks how many earlier prefixes have a particular value, the Map preserves those repeated states. That is the foundation of Subarray Sum Equals K (LeetCode #560), covered in Week 2.

Common mistakes

• Defining prefix[i] inconsistently and introducing left - 1 special cases.
• Forgetting the identity value: 0 for sums, 1 for products.
• Updating a running summary before using it when the current value must be excluded.
• Using division in Product Except Self and mishandling zeroes.
• Storing an entire prefix array when one running aggregate answers the question.