Skip to content

238. Product of Array Except Self

Solve in Leetcode

Description

Static Badge

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1

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

Example 2

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

Constraints

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Solution: Brute Force Approach

  • Time Complexity: O(n^2), where n is the length of nums. Have to iterate over nums array twice.
Warning
  • It which will cause Time Limit Exceeded error.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function productExceptSelf(nums: number[]): number[] {
    let output: number[] = [];

    for(var i = 0; i < nums.length; i++) {
        let clone = nums.filter((_,index) => index !== i);
        output[i] = clone.reduce((acc, el) => acc * el, 1);
    }

    return output;
};

Solution: Dynamic Programming Approach (Space Optimization)

  • Time Complexity: O(n), where n is the length of nums
  • Space Complexity: O(1) exclude nums array
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function productExceptSelf(nums: number[]): number[] {
    // 1 can make first output same as first nums[0]
    let output: number[] = [1];

    // product from left to right
    for(var i = 1; i < nums.length; i++) {
        output[i] = output[i-1] * nums[i-1];
    }

    let right = 1;

    // `i` is last index
    // product from right to left with `output`
    for(var i = nums.length - 1; i >= 0; i--) {
        output[i] *= right;
        right *= nums[i];
    }

    return output;
};