Product of Array Except Self
Given an integer array nums, return an array output such that output[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, 4, 6] Output: [48, 24, 12, 8]
Example 2:
Input: nums = [-1, 0, 1, 2, 3] Output: [0, -6, 0, 0, 0]
Recommended time and space complexity
You should aim for a solution with O(n) time complexity and O(1) space complexity (excluding the output array), where n is the size of the input array.
Hint 1
Instead of dividing the product of all numbers by each number, can you construct the answer by considering products from both sides?
Hint 2
Think about computing prefix products (products of all numbers to the left) and suffix products (products of all numbers to the right) for each position.
Hint 3
Can you use the output array to store one of the products (prefix or suffix) to achieve O(1) extra space?