[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⁵
・ -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.)

Idea

알고보면 간단한 문제인데, 생각하는 것이 어렵다.

주어진 array에서 해당 index의 값을 제외한 다른 모든 수를 곱한 값을 array로 만들어 리턴하는 문제다.

우선, 순방향으로 해당 index의 앞부분을 곱한 값을 array에 저장한다.

다음으로 역순으로 array를 탐색하면서 뒷부분을 곱한 값을 array에 저장된 값에 곱한 후 저장한다.

주어진 array를 두 번 돌면 해당 index를 제외한 원소를 곱한 값이 저장되는 것이다.

위와 같이 풀면 Time Complexity는 O(n)이 된다. Space Complexity도 O(n)인데, follow up에 나온대로 Space Complexity를 O(1)로 풀어보는 것도 많은 도움이 될 것 같다.

Solution

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];

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

        int acc = 1;
        for (int i=nums.length-2; i >= 0; i--) {
            acc *= nums[i+1];
            res[i] = res[i] * acc;
        }

        return res;
    }
}

Reference

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