Product of All Elements Except Self

Medium20–25 min

Topics

ArrayPrefix Sum

Companies

AmazonMicrosoftGoogleApple

Given an array nums, return an array result where result[i] is the product of every element in nums except nums[i] — without using division, and ideally in O(n) time. Multiplying everything except one index, one index at a time, repeats almost the same work over and over. The prefix product trick reuses that work: sweep once left-to-right building the product of everything to the left of each index, then once right-to-left building the product of everything to the right, multiplying the two halves together as you go.

Test Case 1:

Input:nums = [1, 2, 3, 4]

Output:[24, 12, 8, 6]

Explanation:result[0] = 2×3×4 = 24, result[1] = 1×3×4 = 12, and so on.

Test Case 2:

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

Output:[0, 0, 9, 0, 0]

Explanation:The single 0 at index 2 makes every OTHER position's product 0. Index 2 itself excludes that 0, so its product is -1 × 1 × -3 × 3 = 9.

Test Case 3:

Input:nums = [2, 3]

Output:[3, 2]

Explanation:With only two elements, each position's product is simply the other element.

Constraints

◆2 ≤ nums.length ≤ 10⁵
◆-30 ≤ nums[i] ≤ 30
◆The product of any prefix or suffix fits in a 32-bit integer
◆Division is not allowed as a solving technique

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

nums (comma-separated) — 3-8 integers, -6 to 6

1	class Solution {
2	public int[] productExceptSelf(int[] nums) {
3	int n = nums.length;
4	int[] result = new int[n];
5	result[0] = 1;
6	for (int i = 1; i < n; i++) {
7	result[i] = result[i - 1] * nums[i - 1];
8	}
9	int suffix = 1;
10	for (int i = n - 1; i >= 0; i--) {
11	result[i] *= suffix;
12	suffix *= nums[i];
13	}
14	return result;
15	}
16	}
17

Array

Variables

result[0]1

INITIALIZE

result[0] = 1 — there's nothing to the left of index 0, so its prefix product is empty (1).

Step 1 / 14

Approach & Solutions

Brute Force

Brute

For every index i, loop over the whole array again and multiply together every element except nums[i]. Correct, but it repeats almost the same multiplication work for every single index instead of reusing anything from the index before it.

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int product = 1;
            for (int j = 0; j < nums.length; j++) {
                if (j != i) product *= nums[j];
            }
            result[i] = product;
        }
        return result;
    }
}

Optimal — Prefix × Suffix Product

Optimal

This is the same prefix-sum idea, but with multiplication and swept from both directions. First pass, left to right: fill result[i] with the product of everything strictly to the left of i (result[0] = 1, since nothing is to its left). Second pass, right to left: multiply each result[i] by a running suffix product of everything strictly to the right of i, updating that running product as you go. Left-of-i times right-of-i covers every element except i itself — no division needed.

TimeO(n)

SpaceO(1)