LeetCode238. Product of Array Except Self

雨点打透心脏的1/2处 2022-06-06 00:39 170阅读 0赞

# Solution1 Two-pass O(n) time O(n) space #

Considering that we are trying to get something like cumulative sum except self, it is possible that we can utilize some method similar to cumulative sum to get this product. So for this product of array except self, we actually want the product of the left side of the array multiplies the product of the right side of the array. Yes! we can use the 2 side cumulative product, i.e. one multiplies from left to right one by one and the other multiplies from right to left one by one. And thus for a specific product except self, we simply get the product of left side and right side.

Time complexity: `O(2n) = O(n)` because of the 2 passes.  
Space complexity: `O(2n) = O(n)` because of the 2 arrays.

class Solution {
        /**
         * O(n) time, O(n) space 2 pass solution
         * Calculate the left cumulative product and right cumulative product respectively.
         * And then get the product expect self in O(1).
         */
        public int[] productExceptSelf(int[] nums) {
            int product = 1;
            int[] leftProduct = new int[nums.length];
            int[] rightProduct = new int[nums.length];
            // left cumulative product
            for (int i = 1; i <= nums.length - 1; i++) {
                leftProduct[i] = product * nums[i - 1];
                product = leftProduct[i];
            }
            leftProduct[0] = 1;
    
            product = 1;
            // right cumulative product
            for (int i = nums.length - 2; i >= 0; i--) {
                rightProduct[i] = product * nums[i + 1];
                product = rightProduct[i];
            }
            rightProduct[nums.length - 1] = 1;
    
            int[] ret = new int[nums.length];
            for (int i = 0; i < nums.length; i++) {
                ret[i] = leftProduct[i] * rightProduct[i];
            }
    
            return ret;
        }
    }

# Solution2 Two-pass O(n) time O(1) space without considering the return array #

Although we stored the left and right cumulative product in the previous solution, actually since we are only using one right product each time, we can calculate it on the fly, rather than store it. And for the left product, we could override it step by step from right to left to make it stores the return results.

Time complexity: `O(2n) = O(n)`.  
Space complexity: `O(1)` without considering the return array.

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

# Solution3 One-pass O(n) time O(1) space #

Scan the array from left to right in the same for loop.

class Solution {
        public int[] productExceptSelf(int[] nums) {
            int left = 1;
            int right = 1;
            int len = nums.length;
            int[] ret = new int[len];
            Arrays.fill(ret, 1);
            for (int i = 0, j = len - 1; i < len - 1; i++, j--) {
                left *= nums[i];
                right *= nums[j];
                ret[i + 1] *= left;
                ret[j - 1] *= right;
            }
    
            return ret;
        }
    }