Product of Array Except Self

Category: Array

Deadline: 1st week (12/31 - 1/7)

Difficulty: Medium

Github: https://github.com/iamseokhyun/2022-algorithm-study/tree/master/array/ProductofArrayExceptSelf/

LeetCode link: https://leetcode.com/problems/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.

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

Solution

public class Solution
{
    public int[] ProductExceptSelf(int[] nums)
    {
        int l = nums.Length;
        int[] output = new int[l];
        output[0] = 1;

        for (int i = 1; i < l; i++)
        {
            output[i] = output[i - 1] * nums[i - 1];
        }

        int r = 1;
        output[l - 1] *= nums[l - 1];

        for (int i = l - 1; i > -1; i--)
        {
            output[i] *= r;
            r *= nums[i];
        }

        return output;
    }
}

Comment

• Divide 연산자( / )를 사용하지 못하므로 모든 수를 곱한 다음 ith index로 나누는 방법은 불가능, 길이는 nums와 같고 output이라는 배열을 만든 뒤 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 한번씩 곱하는 과정을 반복.
• output[i] = output[i-1] * nums[i-1]을 통해 output의 ith index에 i번째 이전까지의 수들의 모든 곱이 들어감.
• 왼쪽 -> 오른쪽으로 이동할때에는 0~i-1th index까지의 곱을 output[i-2]에 저장할 수 있었지만, 오른쪽 -> 왼쪽으로 이동할때는 output에 이미 값이 할당되어 있음. 새로운 l 크기의 배열에 넣어 배열끼리 곱하는 방법도 있지만, 계산의 효율성과 공간활용을 위해 r이라는 int 에 nums[i]를 연거푸 곱하고 이를 다시 output의 값에 곱해주는 방법으로 1을 우->좌로 반복.