Question

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

238	Product of Array Except Self

Given an array of n integers where n > 1, nums,
return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity?
(Note: The output array does not count as extra space for the purpose of space complexity analysis.)

@tag-array

Algorithm

Related: 1740-Find-Distance-in-a-Binary-Tree

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.

Code

Java

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

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.

  1. We traverse from the front first, and store the accumulation of the product in the result res
  2. Then start traversing from the back, using a temporary variable right, initialized to 1
  3. Then keep accumulating each time, and finally get the correct result
  • public class Solution {
        public int[] productExceptSelf(int[] nums) {
            int n = nums.length;
            int[] res = new int[n];
            res[0] = 1;
            for (int i = 1; i < n; ++i) {
                res[i] = res[i - 1] * nums[i - 1];
            }
    
            int right = 1;
            for (int i = n - 1; i >= 0; --i) {
                res[i] *= right;
                right *= nums[i];
            }
            return res;
        }
    }
    
  • // 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
    
    

All Problems

All Solutions