Welcome to Subscribe On Youtube

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

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.

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

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

All Problems

All Solutions