Compute product of array except self
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Given an integer array nums, return an array out where out[i] equals the product of all elements in nums except nums[i]. Do it in O(n) time using constant extra space beyond the output array and without using division. Discuss how to handle zero(s), negative values, and potential overflow, and provide unit tests.
Quick Answer: This question evaluates a candidate's ability to implement array transformations under strict time and space constraints, including handling edge cases such as zeros, negative values, overflow risks, and designing appropriate unit tests.
Given an integer array `nums`, return an array `out` where `out[i]` equals the product of all elements of `nums` except `nums[i]`.
Solve it in **O(n)** time using **constant extra space** beyond the output array, and **without using the division operator**.
The classic trick is two passes: a left-to-right pass that fills `out[i]` with the product of everything to the left of `i`, then a right-to-left pass that multiplies in the product of everything to the right of `i`. This naturally handles zeros (a single zero makes every other entry zero except its own slot; two or more zeros make the whole result zero) and negative values (sign just follows from the multiplications). Division is avoided entirely, which sidesteps the divide-by-zero problem that a `total_product / nums[i]` approach would hit.
**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
- Must run in O(n) time
- Must use only constant extra space beyond the output array
- The division operator may not be used
Examples
Input: ([1, 2, 3, 4],)
Expected Output: [24, 12, 8, 6]
Explanation: out[0]=2*3*4=24, out[1]=1*3*4=12, out[2]=1*2*4=8, out[3]=1*2*3=6.
Input: ([-1, 1, 0, -3, 3],)
Expected Output: [0, 0, 9, 0, 0]
Explanation: A single zero at index 2: every other slot includes that zero in its product and becomes 0, while index 2 itself is the product of the non-zero elements (-1*1*-3*3 = 9).
Hints
- Avoid division: even if you could compute the total product, a single zero in the array makes total / nums[i] undefined for the zero's slot.
- out[i] = (product of everything left of i) * (product of everything right of i). Compute these with two passes.
- First pass left-to-right: store the running prefix product in out[i] before multiplying nums[i] in. Then a second pass right-to-left multiplies each out[i] by the running suffix product. Keep the prefix/suffix in single scalar variables so you use O(1) extra space.