14. Product of Array Except Self

MediumArray Prefix Sum

Given an integer array nums, return an array answer where answer[i] is the product of every element of nums except nums[i].

Your algorithm must run in O(n) time and must not use division. Every prefix and suffix product fits in a 32-bit signed integer.

Example 1

Input: nums = [2,3,4,5]
Output: [60,40,30,24]

Explanation: For example, answer[1] = 2 · 4 · 5 = 40.

Example 2

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

Explanation: Only the position holding the 0 gets a non-zero product: -2 · 1 · 3 = -6.

Example 3

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

Explanation: With two zeros, every product includes at least one of them.

Constraints

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
Every prefix and suffix product of nums fits in a 32-bit signed integer.

Follow-up: Can you do it with O(1) extra space, not counting the output array?

💡 Hint 1

answer[i] is (product of everything to the left of i) × (product of everything to the right of i).

💡 Hint 2

Compute all the left products in one pass and all the right products in a second pass.

💡 Hint 3

To use O(1) extra space besides the output, store the left products in answer first, then sweep from the right with a single running product.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

The product of all elements except nums[i] equals the prefix product before i times the suffix product after i. First sweep left to right, writing into answer[i] the product of nums[0..i-1]. Then sweep right to left with a running suffix product: multiply answer[i] by suffix, then multiply suffix by nums[i]. Zeros need no special casing, and no division is used.

Time O(n)Space O(1) extra (the output array does not count)

function productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n);
  let prefix = 1;
  for (let i = 0; i < n; i++) {
    answer[i] = prefix;
    prefix *= nums[i];
  }
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= suffix;
    suffix *= nums[i];
  }
  return answer;
}

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

/**
 * @param {number[]} nums
 * @return {number[]}
 */
function productExceptSelf(nums) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit