Product of Array Except Self

The problem

You are given an array nums of whole numbers (call its length n). Build a new array answer of the same length, where answer[i] is the product of every number in nums except nums[i].

You may not use division. Aim for O(n) time.

Example 1

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

Output: [12, 8, 24, 6]

answer[0] = 3 × 1 × 4 = 12. answer[1] = 2 × 1 × 4 = 8. answer[2] = 2 × 3 × 4 = 24. answer[3] = 2 × 3 × 1 = 6.

nums

20311243

answer

1208124263

Example 2

Input: nums = [5, 0, 2]

Output: [0, 10, 0]

Every product that includes the 0 is 0. Only answer[1] leaves the 0 out: 5 × 2 = 10.

Example 3

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

Output: [-18, 9, -6, 6]

Signs follow the usual rules. For example, answer[1] = (−1) × (−3) × 3 = 9.

Constraints

• 2 ≤ n ≤ 100,000
• −30 ≤ nums[i] ≤ 30
• Every product of a prefix or a suffix fits in a 32-bit integer.

Clarifying questions

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

Division is not allowed. It also breaks when nums[i] is 0.

Can there be zeros?

Yes, even several. The approaches below need no special case for them.

Can the products overflow?

No. The problem promises every prefix and suffix product fits in 32 bits.

Does the output array count as extra memory?

No. The follow-up asks for O(1) extra memory besides the answer itself.

Spot the pattern

“Everything except i” splits into two parts: everything left of i, and everything right of i. A running product from the left gives the first part for every i in one pass. A running product from the right gives the second. This is the prefix sum idea, with multiply instead of add.

Solutions

Brute forceO(n²)Prefix and suffixO(n)One arrayO(n), O(1) space

Show all

Brute force O(n²)

The idea

For each position i, walk the whole array again and multiply every number except the one at i. It matches the problem statement word for word, so it is clearly correct.

But each answer redoes almost the same work as the one before. answer[0] and answer[1] share every factor except two.

Walkthrough

nums

20311243

answer

10111213

1. answer = [1] * len(nums)
2. for i in range(len(nums)):
3. for j in range(len(nums)):
4. if j != i:
5. answer[i] *= nums[j]
6. return answer

For each position i, multiply every number except nums[i]. Every answer starts at 1.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Brute force: for each position, multiply all the other numbers.
    // n positions times n numbers, so O(n^2) time and O(1) extra memory.
    public int[] productExceptSelf(int[] nums) {
        int numsLength = nums.length;
        int[] answer = new int[numsLength];
        Arrays.fill(answer, 1);
        for (int i = 0; i < numsLength; i++) {
            for (int j = 0; j < numsLength; j++) {
                // Leave out the number at i itself.
                if (j != i) answer[i] *= nums[j];
            }
        }
        return answer;
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines check j != i and multiply. They sit inside two loops that each walk all n positions. One check and one multiply do not grow with n, so each run is 1 step.

   1. answer = [1] * len(nums)
   2. for i in range(len(nums)):
   3. for j in range(len(nums)):
   4. if j != i:
   5. answer[i] *= nums[j]
   6. return answer

2. 2 Count the runs on Example 1

   Example 1 has 4 numbers. For each of the 4 values of i, the inner loop walks all 4 values of j. It skips one of them, but it still visits it.

   4 × 4 = 16 runs.

   i	0	1	2	3
   multiplies	3	3	3	3
   skips	1	1	1	1

   inner runs

   4 × 4 = 16

3. 3 Write the count for any n

   With n numbers, the outer loop runs n times and the inner loop runs n times for each:

   n × n = n²

   Check it with Example 1: 4 × 4 = 16.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is already n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   Besides the answer, the code creates only i and j. The space is O(1).

   ij

Prefix and suffix O(n)

The idea

Split each answer in two: answer[i] = (product left of i) × (product right of i).

Build an array prefix, where prefix[i] is the product of everything left of i. Nothing is left of position 0, so prefix[0] = 1. Each next value is the one before times one more number, so the whole array costs one pass.

Build suffix the same way from the right. Then multiply the two arrays position by position.

Walkthrough

nums

20311243

prefix

10·1·2·3

suffix

·0·1·2·3

1. prefix = [1] * len(nums)
2. for i in range(1, len(nums)):
3. prefix[i] = prefix[i - 1] * nums[i - 1]
4. suffix = [1] * len(nums)
5. for i in range(len(nums) - 2, -1, -1):
6. suffix[i] = suffix[i + 1] * nums[i + 1]
7. return [prefix[i] * suffix[i] for i in range(len(nums))]

prefix[i] will be the product of everything left of i. Nothing is left of 0, so prefix[0] = 1.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Prefix and suffix products: everything except nums[i] is
    // (product left of i) * (product right of i). Three passes, O(n) time and memory.
    public int[] productExceptSelf(int[] nums) {
        int numsLength = nums.length;
        // prefix[i] = product of nums[0..i-1]. Nothing is left of 0, so it is 1.
        int[] prefix = new int[numsLength];
        prefix[0] = 1;
        for (int i = 1; i < numsLength; i++) {
            // Reuse the product before, so each value costs one multiply.
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }
        // suffix[i] = product of nums[i+1..end]. Nothing is right of the last position.
        int[] suffix = new int[numsLength];
        suffix[numsLength - 1] = 1;
        for (int i = numsLength - 2; i >= 0; i--) suffix[i] = suffix[i + 1] * nums[i + 1];
        int[] answer = new int[numsLength];
        for (int i = 0; i < numsLength; i++) answer[i] = prefix[i] * suffix[i];
        return answer;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There are three loops, one after the other: fill prefix, fill suffix, combine them. Each run does one multiply, so each run is 1 step. No loop sits inside another.

   1. prefix = [1] * len(nums)
   2. for i in range(1, len(nums)):
   3. prefix[i] = prefix[i - 1] * nums[i - 1]
   4. suffix = [1] * len(nums)
   5. for i in range(len(nums) - 2, -1, -1):
   6. suffix[i] = suffix[i + 1] * nums[i + 1]
   7. return [prefix[i] * suffix[i] for i in range(len(nums))]

2. 2 Count the runs on Example 1

   Example 1 has 4 numbers. The prefix loop runs 3 times (from 1 to 3). The suffix loop runs 3 times (from 2 down to 0). The combine step runs 4 times.

   3 + 3 + 4 = 10 runs.

   loop	prefix	suffix	combine
   runs on Example 1	3	3	4

3. 3 Write the count for any n

   (n − 1) + (n − 1) + n = 3n − 2

   Check it with Example 1: 3 × 4 − 2 = 10.

4. 4 Keep only the part that grows fastest

   • Drop the − 2. A fixed amount does not change how the work grows.
   • Drop the 3. Three passes instead of one: when n doubles, 3n still only doubles.

   What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   prefix and suffix hold n numbers each. That is 2n extra numbers, so the space is O(n). The next approach removes both arrays.

   prefix (n numbers)suffix (n numbers)i

One array O(n), O(1) space

The idea

The answer array is allowed for free. So use it to hold the prefix products in a first pass, left to right.

Then walk back from the right with one number, right, instead of a whole suffix array. At each position, multiply answer[i] (the product on the left) by right (the product on the right). Only then fold nums[i] into right, so it is ready for the next position to the left.

Why it is correct: when the second pass reaches i, answer[i] still holds the product left of i, and right holds exactly the product right of i. Their product leaves out nums[i] and nothing else.

Walkthrough

nums

20311243

answer

10·1·2·3

1. answer = [1] * len(nums)
2. for i in range(1, len(nums)):
3. answer[i] = answer[i - 1] * nums[i - 1]
4. right = 1
5. for i in range(len(nums) - 1, -1, -1):
6. answer[i] *= right
7. right *= nums[i]
8. return answer

Use the answer array itself to hold the prefix products. answer[0] = 1, since nothing is left of 0.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Prefix products in the answer, then one running suffix product.
    // Two passes, O(n) time. No array besides the answer, so O(1) extra memory.
    public int[] productExceptSelf(int[] nums) {
        int numsLength = nums.length;
        // First pass: answer[i] = product of everything left of i.
        int[] answer = new int[numsLength];
        answer[0] = 1;
        for (int i = 1; i < numsLength; i++) answer[i] = answer[i - 1] * nums[i - 1];
        // Second pass: right = product of everything right of i.
        int right = 1;
        for (int i = numsLength - 1; i >= 0; i--) {
            answer[i] *= right;
            // Fold nums[i] in after using right, so it never multiplies itself.
            right *= nums[i];
        }
        return answer;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There are two loops, one after the other. Each run of the first does one multiply. Each run of the second does two. Either way it is a fixed amount of work, so each run is 1 step.

   1. answer = [1] * len(nums)
   2. for i in range(1, len(nums)):
   3. answer[i] = answer[i - 1] * nums[i - 1]
   4. right = 1
   5. for i in range(len(nums) - 1, -1, -1):
   6. answer[i] *= right
   7. right *= nums[i]
   8. return answer

2. 2 Count the runs on Example 1

   Example 1 has 4 numbers. The first loop runs 3 times (from 1 to 3). The second loop runs 4 times (from 3 down to 0).

   3 + 4 = 7 runs.

   loop	left to right	right to left
   runs on Example 1	3	4

3. 3 Write the count for any n

   (n − 1) + n = 2n − 1

   Check it with Example 1: 2 × 4 − 1 = 7.

4. 4 Keep only the part that grows fastest

   • Drop the − 1 and drop the 2, for the same reasons as before. Neither changes how the work grows with n.

   What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   Besides the answer array, the code keeps only right and i. That is 2 numbers for any n, so the extra space is O(1).

   righti

Common mistake

Updating right too early

In the second pass, multiply answer[i] by right first, and only then multiply right by nums[i]. If you swap the two lines, nums[i] ends up in its own answer.

Tested at the limits

2,000 random arrays of 2 to 8 numbers from −3 to 3, so zeros (one, two or more) and sign changes are common. The brute force, the prefix and suffix and the one array gave the same answer every time.

Largest inputs	Result
100,000 numbers (the most allowed). One array.	0.01 s, and about 0.9 MB of extra memory: that is the answer list itself. Nothing else grows, which is the O(1) space.
100,000 numbers. Prefix and suffix.	0.01 s, and about 2.5 MB of extra memory: two more arrays the same size as the answer.
2,000 numbers. Brute force, about 4 million products.	0.15 s. At 100,000 numbers it would do 10 billion products, which is why the one array matters.