Question

Formatted question description: https://leetcode.ca/all/238.html

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.)

Algorithm

For a certain number, if we know the product of all the numbers before it, and also know the product of all the numbers after it, then the multiplication of the before and after is the result we want.

So we only need to create these two arrays separately and traverse from the two directions back and forth of the array, to create the multiplication and accumulation product arrays.

Algorithm - 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

Code

import java.util.Arrays;

public class Product_of_Array_Except_Self {

    public static void main(String[] args) {

        Product_of_Array_Except_Self out = new Product_of_Array_Except_Self();

        Solution s = out.new Solution();
        System.out.println(Arrays.toString(s.productExceptSelf(new int[]{1,2,3,4}))); // output: [24,12,8,6]

    }

    // combine below solution, 2 for loops into 1 loop
    class Solution {

        // @note: int[] is definitely possible to be overflowed, the problem set is troublesome itself
        public int[] productExceptSelf(int[] nums) {
            if (nums == null || nums.length == 0) {
                return nums;
            }

            // product from index=0 to index=i-1 position.
            // @note: excluding current index, fromLeft[i] = nums[0] * nums[1] * ... * nums[i-1]
            int[] result = new int[nums.length];
            result[0] = 1;

            for (int i = 1; i < nums.length; i++) {
                result[i] = nums[i - 1] * result[i - 1]; // here excluding current nums[] value
            }

            // product from index=n-1 to current position
            int fromRight = 1;

            for (int i = nums.length - 1; i >= 0; i--) {

                // `fromRight` is excluding current-index, at below line
                result[i] *= fromRight; // here result[] is same as below fromLeft[]

                fromRight *= nums[i]; // here fromRight value is fromRight[i], for next loop index=i+1, fromRight index=i
            }

            return result;
        }
    }

    class Solution_space {
        public int[] productExceptSelf(int[] nums) {

            if (nums == null || nums.length == 0) {
                return nums;
            }

            // product from index=0 to index=i-1 position.
            // @note: excluding current index, fromLeft[i] = nums[0] * nums[1] * ... * nums[i-1]
            int[] fromLeft = new int[nums.length];
            fromLeft[0] = 1;

            for (int i = 1; i < nums.length; i++) {
                fromLeft[i] = nums[i - 1] * fromLeft[i - 1]; // here excluding current nums[] value
            }

            // product from index=n-1 to current position
            int[] fromRight = new int[nums.length];
            fromRight[nums.length - 1] = 1;

            for (int i = nums.length - 2; i >= 0; i--) {
                fromRight[i] = nums[i + 1] * fromRight[i + 1];
            }

            int[] result = new int[nums.length];
            for (int i = 0; i < nums.length; i++) {
                result[i] = fromLeft[i] * fromRight[i];
            }

            return 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;
    }
}

// OJ: https://leetcode.com/problems/product-of-array-except-self/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& A) {
        vector<int> ans = A;
        int N = A.size(), prod = 1;
        for (int i = N - 2; i >= 0; --i) ans[i] = ans[i + 1] * A[i];
        for (int i = 0; i < N; ++i) {
            ans[i] = prod * (i + 1 < N ? ans[i + 1] : 1);
            prod *= A[i];
        }
        return ans;
    }
};

class Solution(object):
  # better way
  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

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

class Solution:
    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

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

function productExceptSelf(nums: number[]): number[] {
    const n = nums.length;
    let 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;
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
    const n = nums.length;
    let 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;
};

impl Solution {
    pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
        let mut dp_left = vec![1_i32; nums.len()];
        let mut dp_right = vec![1_i32; nums.len()];
        for i in 1..nums.len() {
            dp_left[i] = dp_left[i - 1] * nums[i - 1];
        }
        for i in (0..(nums.len() - 1)).rev() {
            dp_right[i] = dp_right[i + 1] * nums[i + 1];
        }
        dp_left
            .into_iter()
            .enumerate()
            .map(|(i, x)| x * dp_right[i])
            .collect()
    }
}

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;
    }
}

238 - Product of Array Except Self

Question

Algorithm

Algorithm - Follow up

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Algorithm - Follow up

Code

All Problems

All Solutions