238. Product of Array Except Self

Description

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 <= 10⁵
-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.)

Solutions

Solution 1: Two Passes

We define two variables $l e f t <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>l</mi><mi>e</mi><mi>f</mi><mi>t</mi></math>$ and $r i g h t <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>r</mi><mi>i</mi><mi>g</mi><mi>h</mi><mi>t</mi></math>$ , which represent the product of all elements to the left and right of the current element respectively. Initially, $l e f t = 1 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>l</mi><mi>e</mi><mi>f</mi><mi>t</mi><mo>=</mo><mn>1</mn></math>$ , $r i g h t = 1 <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>r</mi><mi>i</mi><mi>g</mi><mi>h</mi><mi>t</mi><mo>=</mo><mn>1</mn></math>$ . Define an answer array $a n s <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>n</mi><mi>s</mi></math>$ of length $n <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>$ .

We first traverse the array from left to right, for the $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ th element we update $a n s [i] <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>n</mi><mi>s</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo></math>$ with $l e f t <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>l</mi><mi>e</mi><mi>f</mi><mi>t</mi></math>$ , then $l e f t <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>l</mi><mi>e</mi><mi>f</mi><mi>t</mi></math>$ multiplied by $n u m s [i] <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi><mi>u</mi><mi>m</mi><mi>s</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo></math>$ .

Then, we traverse the array from right to left, for the $i <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>i</mi></math>$ th element, we update $a n s [i] <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>n</mi><mi>s</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo></math>$ to $a n s [i] \times r i g h t <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>a</mi><mi>n</mi><mi>s</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo><mo>\times</mo><mi>r</mi><mi>i</mi><mi>g</mi><mi>h</mi><mi>t</mi></math>$ , then $r i g h t <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>r</mi><mi>i</mi><mi>g</mi><mi>h</mi><mi>t</mi></math>$ multiplied by $n u m s [i] <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi><mi>u</mi><mi>m</mi><mi>s</mi><mo stretchy="false">[</mo><mi>i</mi><mo stretchy="false">]</mo></math>$ .

After the traversal, the array ans is the answer.

The time complexity is $O (n) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo></math>$ , where $n <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>n</mi></math>$ is the length of the array nums. Ignore the space consumption of the answer array, the space complexity is $O (1) <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo></math>$ .

Follow up

We can optimize the above method space complexity.

Since the final result is to be multiplied into the result res, it is not necessary to store the product in a separate array, but directly accumulate into the result res.

We traverse from the front first, and store the accumulation of the product in the result res
Then start traversing from the back, using a temporary variable right, initialized to 1
Then keep accumulating each time, and finally get the correct result

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

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        for (int i = 0, left = 1; i < n; ++i) {
            ans[i] = left;
            left *= nums[i];
        }
        for (int i = n - 1, right = 1; ~i; --i) {
            ans[i] *= right;
            right *= nums[i];
        }
        return ans;
    }
};

class Solution: # 2 extra arrays
    def productExceptSelf(self, nums):
        if nums is None or len(nums) == 0:
            return nums

        # Product from index=0 to index=i-1
        from_left = [1] * len(nums)
        for i in range(1, len(nums)):
            from_left[i] = nums[i - 1] * from_left[i - 1]

        # Product from index=n-1 to current position
        from_right = [1] * len(nums)
        for i in range(len(nums) - 2, -1, -1):
            from_right[i] = nums[i + 1] * from_right[i + 1]

        # Calculate result
        result = [0] * len(nums)
        for i in range(len(nums)):
            result[i] = from_left[i] * from_right[i]

        return result

############

class Solution: # follow up, no extra space
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [0] * n
        left = right = 1
        for i, v in enumerate(nums):
            ans[i] = left
            left *= v
        for i in range(n - 1, -1, -1):
            ans[i] *= right
            right *= nums[i]
        return ans


############


class Solution(object):
  def productExceptSelf(self, nums):
    """
    :type nums: List[int]
    :rtype: List[int]
    """
    dp = [1] * len(nums)
    for i in range(1, len(nums)):
      dp[i] = dp[i - 1] * nums[i - 1]
    prod = 1
    for i in reversed(range(0, len(nums))):
      dp[i] = dp[i] * prod
      prod *= nums[i]
    return dp

func productExceptSelf(nums []int) []int {
	n := len(nums)
	ans := make([]int, n)
	left, right := 1, 1
	for i, x := range nums {
		ans[i] = left
		left *= x
	}
	for i := n - 1; i >= 0; i-- {
		ans[i] *= right
		right *= nums[i]
	}
	return ans
}

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    const ans: number[] = new Array(n);
    for (let i = 0, left = 1; i < n; ++i) {
        ans[i] = left;
        left *= nums[i];
    }
    for (let i = n - 1, right = 1; i >= 0; --i) {
        ans[i] *= right;
        right *= nums[i];
    }
    return ans;
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
    const n = nums.length;
    const ans = new Array(n);
    for (let i = 0, left = 1; i < n; ++i) {
        ans[i] = left;
        left *= nums[i];
    }
    for (let i = n - 1, right = 1; i >= 0; --i) {
        ans[i] *= right;
        right *= nums[i];
    }
    return ans;
};

class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[]
     */
    function productExceptSelf($nums) {
        $n = count($nums);
        $ans = [];
        for ($i = 0, $left = 1; $i < $n; ++$i) {
            $ans[$i] = $left;
            $left *= $nums[$i];
        }
        for ($i = $n - 1, $right = 1; $i >= 0; --$i) {
            $ans[$i] *= $right;
            $right *= $nums[$i];
        }
        return $ans;
    }
}

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int n = nums.Length;
        int[] ans = new int[n];
        for (int i = 0, left = 1; i < n; ++i) {
            ans[i] = left;
            left *= nums[i];
        }
        for (int i = n - 1, right = 1; i >= 0; --i) {
            ans[i] *= right;
            right *= nums[i];
        }
        return ans;
    }
}

impl Solution {
    pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut ans = vec![1; n];
        for i in 1..n {
            ans[i] = ans[i - 1] * nums[i - 1];
        }
        let mut r = 1;
        for i in (0..n).rev() {
            ans[i] *= r;
            r *= nums[i];
        }
        ans
    }
}

238 - Product of Array Except Self

238. Product of Array Except Self

Description

Solutions

Follow up

All Problems

All Solutions

Welcome to Subscribe On Youtube

238. Product of Array Except Self

Description

Solutions

Follow up

All Problems

All Solutions