[LeetCode] 238. Product of Array Except Self

Problem

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^5
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

---

Solution

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

Explanation

• 문제를 O(n)의 시간 복잡도 내에 해결하려면 반복문을 중첩해서는 안된다. 고로 배열 nums의 앞에서 뒤로 혹은 뒤에서 앞으로 참조하는 과정을 반복하여 문제를 해결하도록 한다.
• 반환을 위한 배열 ans를 선언한다.

  int[] ans = new int[nums.length];
  

• 배열 nums를 앞에서 뒤로 참조하여 얻을 수 있는 값은 다음과 같다. ```java
• nums[0]
• nums[0] * nums[1]
• nums[0] * nums[1] * nums[2]
• … ```
• 위에 해당하는 값들을 반환을 위한 배열 ans에 할당해준다.
• 배열 ans와 nums의 같은 자리 원소는 서로 관련이 없기 때문에 배열 ans에 값을 할당하는 과정에서 배열 nums의 원소 중 같은 자리 원소가 사용되지 않도록 한다.

  ans[0] = 1;
  for (int i = 1; i < nums.length; i++)
    ans[i] = ans[i - 1] * nums[i - 1];
  

• 배열 nums를 뒤에서 앞으로 참조하여 얻을 수 있는 값은 다음과 같다. ```java
• nums[nums.length - 1]
• nums[nums.length - 1] * nums[nums.length - 2]
• nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3]
• … ```
• 위에 해당하는 값들을 배열 ans에 할당해준다.
• 마찬가지로 ans에 값을 할당하는 과정에서 배열 nums의 원소 중 같은 자리 원소가 사용되지 않도록 한다.
• 배열 ans를 반환한다.

  for (int i = nums.length - 2; -1 < i; i--) {
    ans[i] *= nums[i + 1];
    nums[i] *= nums[i + 1];
  }
  return ans;