Product of Array Except Self
Problem Description
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:
Example 2:
Constraints:
- 2 <= nums.length <= 105
- -30 <= nums[i] <= 30
- The input is generated such that
answer[i]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.)
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The brute force approach is to calculate the product of all elements in the array except the one at the current index. We can achieve this by iterating over each element and using an inner loop to calculate the product of all elements except the current one.
Steps:
- Initialize an output array of length
nwith all elements set to 1. - For each element in the input array, iterate over the input array again to calculate the product of all elements except the current one.
- Assign this product to the corresponding index in the output array.
Code:
- Time Complexity: O(n^2) because for each element, we loop through the array again.
- Space Complexity: O(1) except for the output array, which does not count as extra space by convention.
2. Prefix and Suffix Products
Intuition:
To improve efficiency, we can use two auxiliary arrays to store the product of all elements to the left and to the right of each index. This way, we can construct the result array by multiplying the prefix and suffix products.
Steps:
- Create two arrays
prefixandsuffix, both of sizen. - Fill the
prefixarray such thatprefix[i]holds the product of all elements to the left ofi. - Fill the
suffixarray such thatsuffix[i]holds the product of all elements to the right ofi. - For the result array, multiply the corresponding values of
prefixandsuffix.
Code:
- Time Complexity: O(n) because we are traversing the input array three times.
- Space Complexity: O(n) for the prefix and suffix arrays.
3. Single Pass
Intuition:
To optimize our space usage, we can eliminate the suffix array and calculate the right product on the fly while filling up the result array. Compute left products into the output first, then sweep from right to left while maintaining a single variable right that accumulates the product of elements to the right of the current index.
- The answer at index
iis(product of elements left of i) × (product of elements right of i). - We can precompute the left part in one forward pass.
- We don’t need a whole suffix array: a single running multiplier
rightcan supply the right part during a backward pass.
Steps:
- Initialize the result array by computing the prefix (left) products as in approach 2.
- Use a single variable
rightto iterate from the end of the array, updating the result by multiplying withright. - Update
rightin each iteration as you progress from right to left.
Code:
- Time Complexity: O(n) because it involves two passes over the array.
- Space Complexity: O(1) extra space apart from the output array.
Example Walkthrough:
Pass 1: Build left products (stored in output)
output[i] = output[i - 1] * nums[i - 1]
Pass 2: Sweep from right, multiply by running right product
output[i] *= right, right *= nums[i]