Product of Array Except Self

Problem in Plain English

For each position, multiply every number except the one at that position. Return those products in order, without division, in linear time.

Problem Statement

Given an integer array nums, build an array answer of the same length. For each index i, answer[i] must multiply all values in nums except nums[i]. Exclude a position, not every occurrence of its value.

The solution must take $O(n)$ time without division, where n is the array length. Products of all prefixes (sections starting at the first element) and suffixes (sections ending at the last element) fit in a signed 32-bit integer.

Follow-up: use $O(1)$ extra space. The returned answer array does not count as extra space; any other arrays do.

Constraints

2 <= nums.length <= 100000
-30 <= nums[i] <= 30
Every answer[i], prefix product, and suffix product fits in a signed 32-bit integer.

Examples

Example 1

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

Skip each position: 2 * 3 * 4 = 24, 1 * 3 * 4 = 12, 1 * 2 * 4 = 8, and 1 * 2 * 3 = 6.

Example 2

Input: nums = [2, 5]
Output: [5, 2]

At the smallest allowed length, each answer is simply the other number.

Example 3

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

Only index 2 skips the zero: (-1) * 1 * (-3) * 3 = 9; every other product contains zero.

Example 4

Input: nums = [0, 2, 0, 4]
Output: [0, 0, 0, 0]

Skipping one position still leaves at least one zero in every product.

Intuition

Split the array at the position you must skip: everything to its left and everything to its right. Their products combine into the answer. For index 2 in [1, 2, 3, 4], the left product is 1 * 2 = 2, the right product is 4, and the answer is 2 * 4 = 8. A side with no elements contributes 1, because multiplying by 1 leaves the other side unchanged. Two sweeps reuse these products instead of starting over for each position.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

For each position, scan the array and multiply every other value. This is a useful starting point, but it repeats nearly the same work for each answer and fails the required linear-time bound. Count zeros first so a product containing zero can be answered immediately, without a huge intermediate product.

Step-by-Step Logic

Count the zeros in nums and create answer filled with zeros. For [1, 2, 3, 4], the zero count is 0.
For each index i, check whether a zero remains after skipping i. If so, leave answer[i] = 0 and move on.
Otherwise, start product = 1 and scan every index j. Multiply by nums[j] only when j != i.
Store the product in answer[i]. At i = 0, this gives 2 * 3 * 4 = 24.
Repeat for all positions and return [24, 12, 8, 6]. The other three products are 12, 8, and 6.

Why It Works

If a zero remains outside i, the answer must be zero. Otherwise the inner loop visits each allowed position exactly once and skips only i, so it multiplies exactly the required values. Counting zeros first prevents JavaScript from overflowing to Infinity on a long interior segment before encountering a later zero.

Dry Run

Brute Force: variable states at each step
Index	Skipped value	Running product after each included value	Answer so far
`0`	`1`	`2 -> 6 -> 24`	`[24, 0, 0, 0]`
`1`	`2`	`1 -> 3 -> 12`	`[24, 12, 0, 0]`
`2`	`3`	`1 -> 2 -> 8`	`[24, 12, 8, 0]`
`3`	`4`	`1 -> 2 -> 6`	`[24, 12, 8, 6]`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(1)

Worst case: no zeros, so n answers each require a scan of n values. The preliminary zero count is linear and does not change the quadratic bound. Extra space is constant for counters and one product; the returned array occupies O(n) space and is excluded.

Code

Solution.java

1class Solution {2    public int[] productExceptSelf(int[] nums) {3        int n = nums.length;4        int[] answer = new int[n];5        int zeroCount = 0;6        for (int value : nums) {7            if (value == 0) zeroCount++;8        }9
10        for (int i = 0; i < n; i++) {11            // A remaining zero makes this answer zero without multiplication.12            int remainingZeros = zeroCount - (nums[i] == 0 ? 1 : 0);13            if (remainingZeros > 0) continue;14
15            int product = 1;16            for (int j = 0; j < n; j++) {17                if (j != i) product *= nums[j];18            }19            answer[i] = product;20        }21        return answer;22    }23}

Hints

Hint 1

At one chosen position, what remains on the left and on the right after you skip it?

Hint 2

A left-to-right pass can keep the product of everything already visited. Save that product before including the current value.

Hint 3

Use the output array for left products, then walk backward with a running right product. Combine the two sides before extending the right product.

Edge Cases

Smallest valid input: [2, 5] returns [5, 2]. Empty and single-element arrays are outside this problem's constraints.
Duplicates: [2, 2, 2] returns [4, 4, 4]. Skip one position, not every matching value.
All ones: [1, 1, 1] returns [1, 1, 1]; starting products at 1 also handles an empty side.
One zero: [-1, 1, 0, -3, 3] returns [0, 0, 9, 0, 0]. Only the zero's position can have a nonzero answer.
Two zeros: [0, 2, 0, 4] returns all zeros. Even a long run of large values between two zeros must return zeros, never NaN.
Negatives: [-1, 2, -3, 4] returns [-24, 12, -8, 6]; ordinary multiplication preserves the correct signs.
Numeric limits: Java int and JavaScript Number handle the guaranteed prefix, suffix, and answer bounds. Without those bounds, reassess overflow and integer precision.

Common Mistakes and Interview Tips

Using total-product division: division is forbidden, and zeros make that shortcut invalid.
Extending prefix or suffix before updating answer: this wrongly includes the current element. State the rule: the running product excludes the current index.
Starting a running product at zero, or using addition: the empty product is 1, and the operation is multiplication.
Interview tip: explain the quadratic baseline, then the two-pass rule. Say explicitly that O(1) is extra space excluding the output; separate prefix and suffix arrays would use O(n) extra space.

Key Takeaway

In the Arrays & Hashing pattern, two directional sweeps can combine information from both sides of an index. Save one side in the output and carry the other in a running value to avoid repeated work and extra arrays.