Product of Array Except Self Without Division
Company: Newrelic
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
# Product of Array Except Self Without Division
Given an integer array, return an array in which output[i] is the product of every input element except nums[i].
~~~python
def product_except_self(nums: list[int]) -> list[int]:
...
~~~
## Requirements
- Do not use division.
- Run in O(n) time.
- Use O(1) auxiliary space beyond the returned list; loop variables do not count.
- Do not mutate nums.
- Zeros and negative values are valid.
- Every intermediate and final product fits in a signed 64-bit integer.
## Constraints and Error Rules
- 2 <= len(nums) <= 100000
- -30 <= nums[i] <= 30
- Every element must be an integer but not a boolean.
- Invalid inputs must raise ValueError.
- Inputs and outputs are JSON-marshalable and outputs are compared exactly.
## Examples
~~~text
Input: [1, 2, 3, 4]
Output: [24, 12, 8, 6]
Input: [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
Input: [0, 0, 5]
Output: [0, 0, 0]
~~~
## Hints
- For each position, separate contributions from the elements on its two sides.
- The returned array can hold intermediate information before it holds final answers.
Quick Answer: Compute the product of every array element except the current one without division. Achieve linear time and constant auxiliary space beyond the output while correctly handling zeros, negative values, validation, and 64-bit product bounds.
Return at each index the product of every other input value in linear time without division and without mutating the input.
Constraints
- 2 <= len(nums) <= 100000
- Zeros and negative integers are allowed
- Use O(1) auxiliary space beyond output
Examples
Input: [1, 2, 3, 4]
Expected Output: [24, 12, 8, 6]
Explanation: The standard positive example.
Input: [-1, 1, 0, -3, 3]
Expected Output: [0, 0, 9, 0, 0]
Explanation: With one zero, only its position has a nonzero product.
Hints
- First store the product strictly left of each position.
- A reverse scan can multiply in the product strictly to the right.