Product of Array Except Self: Prefix and Suffix, No Division

Given an array nums, return an array out where out[i] is the product of every element of nums except nums[i]. Do not use division, and aim for O(n) time.

Every product fits in a signed 32-bit integer.

Examples

Input	Output	Why
`nums = [1, 2, 3, 4]`	`[24, 12, 8, 6]`	out[1] = 1 × 3 × 4 = 12.
`nums = [5, 0, 2]`	`[0, 10, 0]`	Only the zero's own slot escapes the zero.
`nums = [0, 0, 5]`	`[0, 0, 0]`	Two zeros: every product contains at least one.

Constraints

2 ≤ n ≤ 10⁵
−30 ≤ nums[i] ≤ 30
Every product fits in 32 bits
No division

Hints

Hint 1

Total product divided by nums[i] is the obvious move. Try it on [5, 0, 2] and see what happens, and why the question bans it anyway.

Hint 2

The product of everything except position i splits cleanly into two pieces: everything to its left, and everything to its right.

Hint 3

One pass left to right fills in the left products. A second pass right to left multiplies in the right products, carried in a single running variable.

Dry run on `[1,2,3,4]`

Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.

Step 1 / 11

Step 1 / 11

nums
10213243
out
10111213
left1
Two passes. First, left to right: slot i gets the product of everything strictly to its left.
Step 2 / 11

nums
10i213243
out
10111213
left1
out[0] = 1, the product of everything left of index 0. Then multiply 1 into the running product.
Step 3 / 11

nums
1021i3243
out
10111213
left1
out[1] = 1, the product of everything left of index 1. Then multiply 2 into the running product.
Step 4 / 11

nums
102132i43
out
10112213
left2
out[2] = 2, the product of everything left of index 2. Then multiply 3 into the running product.
Step 5 / 11

nums
10213243i
out
10112263
left6
out[3] = 6, the product of everything left of index 3. Then multiply 4 into the running product.
Step 6 / 11

nums
10213243
out
10112263
right1
Now right to left, carrying the product of everything strictly to the right in one variable.
Step 7 / 11

nums
10213243i
out
10112263
right1
out[3] × 1 = 6: left product times right product. Then multiply 4 into the running right product.
Step 8 / 11

nums
102132i43
out
10118263
right4
out[2] × 4 = 8: left product times right product. Then multiply 3 into the running right product.
Step 9 / 11

nums
1021i3243
out
101218263
right12
out[1] × 12 = 12: left product times right product. Then multiply 2 into the running right product.
Step 10 / 11

nums
10i213243
out
2401218263
right24
out[0] × 24 = 24: left product times right product. Then multiply 1 into the running right product.
Step 11 / 11

out
2401218263
No division anywhere, so a zero needed no special case. Answer [24, 12, 8, 6].

How to think about it

The shortcut is to multiply everything once and divide by each element. It fails on a zero — you cannot divide by it, and with two zeros the total is zero while the bookkeeping gets worse — and the question bans division precisely so that you find the structure underneath.

That structure is simple. The product of everything except position i is

(product of nums[0 .. i−1]) × (product of nums[i+1 .. n−1])

— a prefix times a suffix. Build the prefixes in one pass left to right, writing each into the output before multiplying in the current element, so that slot i holds the product of everything strictly to its left. Then sweep right to left with a single running product of everything strictly to the right, and multiply it in.

Zeros need no special handling: a zero simply appears in the prefix or the suffix of every slot but its own. This is the same move as prefix sums in the subarray problem — store the running total, and let a range become the combination of two of them — with multiplication in place of addition.

Complexity. Time O(n) · Space O(1) beyond the output

The solution, in six languages

Each one is compiled and run against the test table before it is published. Java is reviewed by hand.

def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):              # out[i] = product of everything left of i
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):  # multiply in everything right of i
        out[i] *= right
        right *= nums[i]
    return out

#include <vector>
using namespace std;

vector<int> solve(vector<int> nums) {
    int n = nums.size();
    vector<int> out(n, 1);
    int left = 1;
    for (int i = 0; i < n; i++) {        // out[i] = product of everything left of i
        out[i] = left;
        left *= nums[i];
    }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {   // multiply in everything right of i
        out[i] *= right;
        right *= nums[i];
    }
    return out;
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] out = new int[n];
        int left = 1;
        for (int i = 0; i < n; i++) {        // out[i] = product of everything left of i
            out[i] = left;
            left *= nums[i];
        }
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {   // multiply in everything right of i
            out[i] *= right;
            right *= nums[i];
        }
        return out;
    }
}

function productExceptSelf(nums) {
  const n = nums.length, out = new Array(n).fill(1);
  let left = 1;
  for (let i = 0; i < n; i++) {        // out[i] = product of everything left of i
    out[i] = left;
    left *= nums[i];
  }
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {   // multiply in everything right of i
    out[i] *= right;
    right *= nums[i];
  }
  return out;
}

fn solve(nums: &[i32]) -> Vec<i32> {
    let n = nums.len();
    let mut out = vec![1; n];
    let mut left = 1;
    for i in 0..n {                 // out[i] = product of everything left of i
        out[i] = left;
        left *= nums[i];
    }
    let mut right = 1;
    for i in (0..n).rev() {         // multiply in everything right of i
        out[i] *= right;
        right *= nums[i];
    }
    out
}

-- scanl gives the products to the left of each slot, scanr those to the right.
solve :: [Int] -> [Int]
solve xs = zipWith (*) (init (scanl (*) 1 xs)) (tail (scanr (*) 1 xs))

Where people lose marks

Dividing the total product by nums[i]. Banned, and wrong in the presence of a zero.
Including nums[i] in its own prefix — write the running product into out[i] before multiplying the current element in.
Allocating separate prefix and suffix arrays. Correct, but O(n) extra space the running variable makes unnecessary; interviewers often ask for exactly this improvement.
Overflow when the constraints are looser than here. Say which type you would widen to, and when.

Variants to try

Division is allowed. (Count zeros: none, divide; one, only that slot is non-zero; two or more, all zero.)
Same question, but sums instead of products. (Total minus nums[i] — addition has an inverse that never fails.)
Answer queries "product of nums[l..r]" many times. (Prefix products, with care around zeros — store the zero count as a prefix too.)

Next problems

Easy10 min

Product of every element except itself

Examples

Constraints

Hints

Dry run on `[1,2,3,4]`

How to think about it

The solution, in six languages

Where people lose marks

Variants to try

Next problems

Pair with a given sum in an unsorted array

Longest run of consecutive integers

The k most frequent values

Keep going

Pair with a given sum in an unsorted array

Longest run of consecutive integers

The k most frequent values

The pattern behind it

Product of every element except itself

Examples

Constraints

Hints

Dry run on [1,2,3,4]

How to think about it

The solution, in six languages

Where people lose marks

Variants to try

Next problems

Pair with a given sum in an unsorted array

Longest run of consecutive integers

The k most frequent values

Keep going

Pair with a given sum in an unsorted array

Longest run of consecutive integers

The k most frequent values

The pattern behind it

Dry run on `[1,2,3,4]`