Product of Array Except Self
Given an integer array nums, return an array where each element i represents the product of all values in nums excluding nums[i].
Note: You may assume the product of all numbers within nums can safely fit within an integer range.
Example(s)
Example 1:
Input: nums = [1, 2, 3]
Output: [6, 3, 2]
Explanation:
- result[0] = 2 * 3 = 6 (exclude nums[0] = 1)
- result[1] = 1 * 3 = 3 (exclude nums[1] = 2)
- result[2] = 1 * 2 = 2 (exclude nums[2] = 3)
Example 2:
Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Explanation:
- result[0] = 1 * 0 * (-3) * 3 = 0
- result[1] = (-1) * 0 * (-3) * 3 = 0
- result[2] = (-1) * 1 * (-3) * 3 = 9
- result[3] = (-1) * 1 * 0 * 3 = 0
- result[4] = (-1) * 1 * 0 * (-3) = 0
Example 3:
Input: nums = [2, 3, 4, 5]
Output: [60, 40, 30, 24]
Explanation:
- result[0] = 3 * 4 * 5 = 60
- result[1] = 2 * 4 * 5 = 40
- result[2] = 2 * 3 * 5 = 30
- result[3] = 2 * 3 * 4 = 24
Solution
The solution uses two passes without division:
- Left pass: Calculate product of all elements to the left of each index
- Right pass: Calculate product of all elements to the right and multiply with left product
- No division: Avoids division by zero and handles zeros correctly
- JavaScript Solution
- Python Solution
JavaScript Solution - Two Passes
/**
* Product of array except self
* @param {number[]} nums - Input array
* @return {number[]} - Array where result[i] = product of all except nums[i]
*/
function productExceptSelf(nums) {
const n = nums.length;
const result = new Array(n);
// First pass: Calculate left products
// result[i] = product of all elements to the left of i
result[0] = 1; // No elements to the left of index 0
for (let i = 1; i < n; i++) {
result[i] = result[i - 1] * nums[i - 1];
}
// Second pass: Calculate right products and multiply with left products
// rightProduct = product of all elements to the right of i
let rightProduct = 1;
for (let i = n - 1; i >= 0; i--) {
result[i] = result[i] * rightProduct;
rightProduct = rightProduct * nums[i];
}
return result;
}
// Test cases
console.log('Example 1:', productExceptSelf([1, 2, 3]));
// [6, 3, 2]
console.log('Example 2:', productExceptSelf([-1, 1, 0, -3, 3]));
// [0, 0, 9, 0, 0]
console.log('Example 3:', productExceptSelf([2, 3, 4, 5]));
// [60, 40, 30, 24]
console.log('Test 4:', productExceptSelf([1, 0]));
// [0, 1]Output:
Click "Run Code" to execute the code and see the results.
Python Solution - Two Passes
from typing import List
def product_except_self(nums: List[int]) -> List[int]:
"""
Product of array except self
Args:
nums: Input array
Returns:
List[int]: Array where result[i] = product of all except nums[i]
"""
n = len(nums)
result = [1] * n
# First pass: Calculate left products
# result[i] = product of all elements to the left of i
for i in range(1, n):
result[i] = result[i - 1] * nums[i - 1]
# Second pass: Calculate right products and multiply with left products
# right_product = product of all elements to the right of i
right_product = 1
for i in range(n - 1, -1, -1):
result[i] = result[i] * right_product
right_product = right_product * nums[i]
return result
# Test cases
print('Example 1:', product_except_self([1, 2, 3]))
# [6, 3, 2]
print('Example 2:', product_except_self([-1, 1, 0, -3, 3]))
# [0, 0, 9, 0, 0]
print('Example 3:', product_except_self([2, 3, 4, 5]))
# [60, 40, 30, 24]
print('Test 4:', product_except_self([1, 0]))
# [0, 1]Loading Python runtime...
Output:
Click "Run Code" to execute the code and see the results.
Alternative Solution (With Division)
Here's a simpler approach using division (but has issues with zeros):
- JavaScript Division
- Python Division
/**
* Using division (doesn't work well with zeros)
*/
function productExceptSelfDivision(nums) {
const n = nums.length;
let totalProduct = 1;
let zeroCount = 0;
let zeroIndex = -1;
// Calculate total product and count zeros
for (let i = 0; i < n; i++) {
if (nums[i] === 0) {
zeroCount++;
zeroIndex = i;
} else {
totalProduct *= nums[i];
}
}
const result = new Array(n).fill(0);
if (zeroCount === 0) {
// No zeros: divide total product by each element
for (let i = 0; i < n; i++) {
result[i] = totalProduct / nums[i];
}
} else if (zeroCount === 1) {
// One zero: only that index has non-zero product
result[zeroIndex] = totalProduct;
}
// If zeroCount > 1, all results are 0 (already filled)
return result;
}
def product_except_self_division(nums: List[int]) -> List[int]:
"""
Using division (doesn't work well with zeros)
"""
n = len(nums)
total_product = 1
zero_count = 0
zero_index = -1
# Calculate total product and count zeros
for i in range(n):
if nums[i] == 0:
zero_count += 1
zero_index = i
else:
total_product *= nums[i]
result = [0] * n
if zero_count == 0:
# No zeros: divide total product by each element
for i in range(n):
result[i] = total_product // nums[i]
elif zero_count == 1:
# One zero: only that index has non-zero product
result[zero_index] = total_product
# If zero_count > 1, all results are 0 (already filled)
return result
Complexity
- Time Complexity: O(n) - Two passes through the array
- Space Complexity: O(1) extra space - The output array doesn't count as extra space. If we don't count output array, it's O(1).
Approach
The solution uses two passes without division:
-
First pass (left to right):
- Calculate product of all elements to the left of each index
- Store in result array
result[i] = product of nums[0] to nums[i-1]
-
Second pass (right to left):
- Calculate product of all elements to the right of each index
- Multiply with the left product already stored
result[i] = leftProduct[i] * rightProduct[i]
-
Why it works:
- For index i, we need product of all elements except nums[i]
- This equals: (product of left elements) × (product of right elements)
- Left pass calculates left products
- Right pass calculates right products and multiplies
Key Insights
- Two passes: Left products + right products = answer
- No division: Avoids division by zero issues
- O(1) extra space: Uses result array to store left products
- Handles zeros: Works correctly with any number of zeros
- Prefix/suffix products: Similar to prefix sum concept
Step-by-Step Example
Let's trace through Example 1: nums = [1, 2, 3]
Initial: nums = [1, 2, 3]
result = [1, 1, 1] (initialize)
First pass (left to right):
i = 0: result[0] = 1 (no elements to the left)
i = 1: result[1] = result[0] * nums[0] = 1 * 1 = 1
i = 2: result[2] = result[1] * nums[1] = 1 * 2 = 2
After first pass: result = [1, 1, 2]
Second pass (right to left):
rightProduct = 1
i = 2:
result[2] = result[2] * rightProduct = 2 * 1 = 2
rightProduct = rightProduct * nums[2] = 1 * 3 = 3
i = 1:
result[1] = result[1] * rightProduct = 1 * 3 = 3
rightProduct = rightProduct * nums[1] = 3 * 2 = 6
i = 0:
result[0] = result[0] * rightProduct = 1 * 6 = 6
rightProduct = rightProduct * nums[0] = 6 * 1 = 6
Final: result = [6, 3, 2]
Visual Representation
Example 1: nums = [1, 2, 3]
For index 0 (exclude 1):
Left: [] (empty, product = 1)
Right: [2, 3] (product = 6)
Result: 1 * 6 = 6
For index 1 (exclude 2):
Left: [1] (product = 1)
Right: [3] (product = 3)
Result: 1 * 3 = 3
For index 2 (exclude 3):
Left: [1, 2] (product = 2)
Right: [] (empty, product = 1)
Result: 2 * 1 = 2
Result: [6, 3, 2]
Edge Cases
- Array with zeros: Handled correctly (product becomes 0)
- Multiple zeros: All results are 0 except possibly one
- Single element: Result is [1] (product of empty set = 1)
- Negative numbers: Works correctly
- All same numbers: Works correctly
Important Notes
- No division: The two-pass approach avoids division entirely
- O(1) extra space: Uses output array for intermediate storage
- Handles zeros: Works correctly with any number of zeros
- Two passes: Left pass then right pass
- In-place: Can modify result array during second pass
Why Two Passes Work
For each index i, we need:
- Product of all elements to the left:
nums[0] * nums[1] * ... * nums[i-1] - Product of all elements to the right:
nums[i+1] * nums[i+2] * ... * nums[n-1]
First pass: Calculate left products and store in result Second pass: Calculate right products on the fly and multiply with stored left products
Comparison: Two Passes vs Division
| Approach | Time | Space | Handles Zeros | Complexity |
|---|---|---|---|---|
| Two Passes | O(n) | O(1) | Yes | Simple |
| Division | O(n) | O(1) | Needs special handling | More complex |
Related Problems
- Prefix Sum: Similar concept of accumulating values
- Trapping Rain Water: Different but uses similar two-pass technique
- Candy: Another two-pass problem
- Maximum Product Subarray: Different problem
Takeaways
- Two passes efficiently solve without division
- Left + Right products = product except self
- O(1) extra space by using output array
- Handles zeros naturally without special cases
- O(n) time is optimal (must visit each element)