Problem 5.3 · Prefix SumMedium

Product of Array Except Self

What it teaches: Prefix and suffix products: the answer at i is (product of everything left) × (product of everything right), without division.

Practise it on judges as “Product of Array Except Self”.

The problem

Given nums, return an array answer where answer[i] is the product of all elements except nums[i]. Don't use division, and run in O(n).

Example 1

Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]

Example 2

Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]

Constraints

2 ≤ nums.length ≤ 10⁵
−30 ≤ nums[i] ≤ 30
Products fit in a 32-bit int
No division

Pattern clues in the wording

→ Everything except index i = left part and right part
→ No division allowed (zeros would break it anyway)

These clues point to Prefix Sum: Store running totals so the sum of any range is one subtraction: prefix[r + 1] - prefix[l].

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] out = new int[nums.length];
        return out;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [1,2,3,4]	[24,12,8,6]
2	nums = [-1,1,0,-3,3]	[0,0,9,0,0]

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Prefix and suffix arrays · O(n)2. Optimal: prefix in the output, suffix in a variable · O(n)

Prefix and suffix arrays

Time O(n) Space O(n)

left[i] = product of nums[0..i−1], right[i] = product of nums[i+1..n−1]. answer[i] = left[i] × right[i].

Approach 1

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] left = new int[n], right = new int[n], out = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) left[i] = left[i - 1] * nums[i - 1];
        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) right[i] = right[i + 1] * nums[i + 1];
        for (int i = 0; i < n; i++) out[i] = left[i] * right[i];
        return out;
    }
}

Verdict: Clear, with two extra arrays.

Optimal: prefix in the output, suffix in a variable

Time O(n) Space O(1) extra (the output doesn't count)

First pass writes left products into the answer. Second pass goes right to left with a running suffix product, multiplying it in.

▶ Dry run: Left pass, then right passnums = [1, 2, 3, 4]

Step 1/5Left pass: answer[i] = product of everything before i: [1, 1, 1·2, 1·2·3].

Approach 2

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] out = new int[n];
        out[0] = 1;
        for (int i = 1; i < n; i++) out[i] = out[i - 1] * nums[i - 1];
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            out[i] *= suffix;
            suffix *= nums[i];
        }
        return out;
    }
}

Verdict: Same idea, no extra arrays.

Before you submit

Edge cases and common mistakes

Test these inputs

One zero (only that index is non-zero)
Two or more zeros (all zeros)
Negative numbers
Length 2

Mistakes people make

Using total product / nums[i]: banned, and divides by zero.
Multiplying the suffix in before using it.

Interview

Follow-up questions

Why not just divide the total product by nums[i]?

Command Palette