238. Product of Array Except Self

Source link: https://leetcode.com/problems/product-of-array-except-self/

Design

[1,2,3,4] → [24,12,8,6]

Method I (Brute Force)

The brute force way is just simply apply the double for loop to check if the current index equals to the target index we need to assign. It does not meet the constraint of this problem, as the time complexity is $O(n^2)$

Method II

  1. Initialize three arrays. One for storing the final result, both of others safe temperate results.
  2. Calculating the product of nums[n - 1] and left_to_right[n - 1] from left to right, and store the result into the array left_to_right. Please notice that if there is no element on the left of current element assign its value with 1.
  3. Same calculation as the second step from the right to left of the array.
  4. Traverse through the array for storing the final result, assign the element by the product of left_to_right[i] and right_to_left[i].

Method III (Constant Space)

This method does not require the extra space for storing the product result. We can get the solution by observing the image above.

  1. Initialize an array for storing the final result.
  2. Traverse through the array from the left to right, and update elements by the product of res[i - 1] and nums[i - 1] as the method above.
  3. Initialize an for storing the value of the product of elements from right to left.
  4. Traverse through the array from the right to left, and update elements by the product of res[i] * right.
  5. Update the variable value with right * nums[i].

Implementation

Method I (Brute Force)

class Solution {
  public int[] productExceptSelf(int[] nums) {
    int len = nums.length;
    int[] res = new int[len];
    int product = 1;
    for (int i = 0; i < len; i++) {
      for (int j = 0; j < len; j++) {
        if (i != j) {
          product *= nums[j];
        }
      }
      res[i] = product;
      product = 1;
    }
    return res;
  }
}

Method II

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

Method III (Constant Space)

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

Complexity Analysis

Method I (Brute Force)

Time: $O(n^2)$

Space: $O(n)$

Method II

Time: $O(n)$

Space: $O(n)$

Method III (Constant Space)

Time: $O(n)$

Space: $O(1)$