☕ DSA Java Articles

Topics › Arrays › Medium

Product of Array Except Self

Easy TUF ID 2404 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given an integer array nums of length n, return an array answer where answer[i] is the product of every element of nums except nums[i]. You may not use division, and the target is O(n) time. The follow-up asks for O(1) extra space, where the output array does not count as extra.

Constraints (LeetCode 238): 2 ≤ n ≤ 10^5, -30 ≤ nums[i] ≤ 30, and every prefix or suffix product is guaranteed to fit in a 32-bit integer. The methods here also accept n = 0 and n = 1 (the product of no numbers is 1).

Example 1

nums   = [1, 2, 3, 4]
answer = [24, 12, 8, 6]       // e.g. answer[1] = 1 × 3 × 4 = 12

Example 2

nums   = [-1, 1, 0, -3, 3]
answer = [0, 0, 9, 0, 0]      // only answer[2] skips the zero: -1 × 1 × -3 × 3 = 9

Why not just divide?

The obvious trick is to multiply everything once and output total / nums[i]. Apart from being forbidden, it breaks on zeros. With one zero, total is 0 and you would divide 0 by 0 at the zero’s position, whose correct answer is the (non-zero) product of the others. With two or more zeros every answer is 0. Handling this needs a separate count of zeros and a product of the non-zero values: workable, but fiddly. The no-division approaches below are simpler and handle zeros without any special case.

Approach 1: Brute force

Intuition. Do exactly what the definition says: for each index i, multiply all the other elements.

Algorithm.

  1. For each i, start with p = 1.
  2. For each j ≠ i, multiply p by nums[j].
  3. Store p in ans[i].
static int[] bruteForce(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) {
        int p = 1;
        for (int j = 0; j < n; j++) {
            if (j != i) p *= nums[j];
        }
        ans[i] = p;
    }
    return ans;
}

Complexity. Time O(n^2): n outputs, each a product of n - 1 numbers. Space O(1) besides the output.

For n = 10^5 that is 10^10 multiplications. Notice how much is repeated: answer[1] and answer[2] share every factor except two.

Approach 2: Better, prefix and suffix products

Intuition. Split “everything except nums[i]” into two parts: everything to the left of i and everything to the right of i.

answer[i] = (nums[0] × ... × nums[i-1])  ×  (nums[i+1] × ... × nums[n-1])
          =        prefix[i]             ×            suffix[i]

Both parts can be built incrementally: prefix[i] = prefix[i - 1] × nums[i - 1] going left to right, and suffix[i] = suffix[i + 1] × nums[i + 1] going right to left, with prefix[0] = suffix[n - 1] = 1 (empty products). Each element now contributes to the running products once, instead of n - 1 times.

Algorithm.

  1. Fill prefix left to right.
  2. Fill suffix right to left.
  3. ans[i] = prefix[i] × suffix[i].
static int[] better(int[] nums) {
    int n = nums.length;
    int[] prefix = new int[n], suffix = new int[n];      // prefix[i] = nums[0..i-1], suffix[i] = nums[i+1..n-1]
    for (int i = 0; i < n; i++) prefix[i] = i == 0 ? 1 : prefix[i - 1] * nums[i - 1];
    for (int i = n - 1; i >= 0; i--) suffix[i] = i == n - 1 ? 1 : suffix[i + 1] * nums[i + 1];
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) ans[i] = prefix[i] * suffix[i];
    return ans;
}

Complexity. Time O(n): three linear passes. Space O(n) extra for the two helper arrays.

Why zeros are fine. A zero at position z makes prefix[i] zero for every i > z and suffix[i] zero for every i < z, but prefix[z] and suffix[z] do not include nums[z], so answer[z] is correct. No division, no special case.

Approach 3: Optimal, O(1) extra space

Intuition. We do not need two helper arrays. Store the prefix products directly in the output array. Then walk from the right with a single variable right holding the product of everything to the right of the current index, and multiply it in. After the second pass, ans[i] = prefix[i] × suffix[i], exactly as before.

The order inside each loop matters: in the first pass we write ans[i] = left before multiplying nums[i] into left, so ans[i] excludes nums[i]. The same holds for right in the second pass.

Algorithm.

  1. left = 1. For i = 0..n-1: ans[i] = left, then left *= nums[i].
  2. right = 1. For i = n-1..0: ans[i] *= right, then right *= nums[i].
  3. Return ans.
static int[] optimal(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    int left = 1;
    for (int i = 0; i < n; i++) {                        // ans[i] = product of everything left of i
        ans[i] = left;
        left *= nums[i];
    }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {                   // multiply in the product of everything right of i
        ans[i] *= right;
        right *= nums[i];
    }
    return ans;
}

Dry run on nums = [1, 2, 3, 4]:

i after pass 1: ans[i] (left product) right during pass 2 final ans[i]
3 1 × 2 × 3 = 6 1 6
2 1 × 2 = 2 4 8
1 1 4 × 3 = 12 12
0 1 (empty) 12 × 2 = 24 24

Complexity. Time O(n): two passes. Space O(1) extra: two int variables, since the output array is not counted.

The general lesson. Whenever an answer for position i is “combine everything except i” and the combining operation has no inverse you can trust (division with zeros, maximum, gcd), split it into a left part and a right part and precompute both sides. The output array can often double as one of the two helper arrays, which is where the O(1) space comes from.

Edge cases and pitfalls