Suffix Sum | Engineering Interview Kit

Concept

If a Prefix Sum calculates the running total from Left to Right, a Suffix Sum (or Postfix Sum) calculates the running total from Right to Left.

By itself, a Suffix Sum isn’t particularly useful. However, when you combine a Prefix Sum array and a Suffix Sum array, you unlock the ability to know the exact mathematical state of the entire array to the left of an item, and the entire array to the right of an item, in instant $O(1)$ time.

Product of Array Except Self

The absolute best example of this pattern is LeetCode #238: “Given an integer array, return an array answer such that answer[i] is equal to the product of all the elements of the original array except nums[i]. You must write an algorithm that runs in $O(N)$ time and without using the division operation.”

Original Array: [1, 2, 3, 4]

The Math:
To find the answer for the 3 (index 2), we need to multiply everything to its left (1 * 2) by everything to its right (4).

Prefix Products (Left to Right): [1, 1*1, 1*2, 2*3] -> [1, 1, 2, 6]
(Note: We shift it by 1 so the index holds the product of everything STRICTLY BEFORE it).
Suffix Products (Right to Left): [2*3*4, 3*4, 4, 1] -> [24, 12, 4, 1]
(Note: The index holds the product of everything STRICTLY AFTER it).

Final Answer:
Multiply the two arrays together vertically!
[1*24, 1*12, 2*4, 6*1] -> [24, 12, 8, 6]

Implementation (Optimized to O(1) Space)

We could create two separate leftArr and rightArr taking $O(N)$ extra memory. But we can optimize this to $O(1)$ auxiliary space (excluding the output array) by updating the output array in two passes.

function productExceptSelf(nums: number[]): number[] {
    const result = new Array(nums.length).fill(1);
    
    // Pass 1: Prefix Products
    // Store the product of everything to the LEFT of 'i'
    let prefix = 1;
    for (let i = 0; i < nums.length; i++) {
        result[i] = prefix;
        prefix *= nums[i]; // Accumulate the actual number for the next loop
    }
    
    // Pass 2: Suffix Products
    // Multiply by the product of everything to the RIGHT of 'i'
    let suffix = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        result[i] *= suffix; // Multiply the prefix by the suffix
        suffix *= nums[i];   // Accumulate for the next loop
    }
    
    return result;
}

Interview Questions

Q: A problem asks you to find the “Equilibrium Index” of an array. This is an index where the sum of everything strictly to its left equals the sum of everything strictly to its right. How do you solve this using Prefix/Suffix sums?
A:

Approach 1 ( $O(N)$ Space): Create a prefixSum array and a suffixSum array. Loop through the indices and check if prefixSum[i] === suffixSum[i].
Approach 2 ( $O(1)$ Space): You don’t actually need two arrays! First, do one $O(N)$ loop to find the TotalSum of the entire array. Then, start a second loop, maintaining a runningLeftSum variable. At any given index i, you can instantly mathematically deduce the RightSum using: TotalSum - runningLeftSum - nums[i]. If runningLeftSum === RightSum, you have found the Equilibrium Index.

Q: In the “Product of Array Except Self” problem, why does the prompt explicitly forbid the use of the Division operator?
A: Because with division, the problem is trivial. You would just loop once to find the totalProduct of the entire array (e.g., 1*2*3*4 = 24). Then you loop again, and for each item, simply do 24 / nums[i].
The interviewer explicitly bans division to force you to demonstrate your knowledge of Prefix and Suffix manipulation logic. Furthermore, division fails completely if the array contains the number 0 (Division by Zero exception), whereas the Prefix/Suffix approach handles zeros flawlessly.