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.
Examples
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
Hints
Hint 1
The tempting first idea — compute the total product, then divide by nums[i] for each position — is explicitly disallowed here, and it also breaks the moment any element is 0. Why?
Hint 2
The brute force without division: for each index, multiply every OTHER element directly — O(n^2), but it establishes the correct baseline before optimizing.
Hint 3
answer[i] is exactly (product of everything to i's LEFT) times (product of everything to i's RIGHT) — compute those two halves separately, in two linear passes.
Solutions
public int[] productExceptSelfBruteForce(int[] nums) {
int n = nums.length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
int product = 1;
for (int j = 0; j < n; j++) {
if (j != i) product *= nums[j];
}
result[i] = product;
}
return result;
}Time: O(n^2) · Space: O(1) extra (excluding output)