Product of All Other Elements for Each Index Without Division
Company: Walmart Labs
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Given an integer array `nums`, return an array `answer` of the same length in which `answer[i]` is the product of every element of `nums` except `nums[i]`. Do not use division, and run in time linear in the length of `nums`.
### Function Signature
```python
def products_except_self(nums: list[int]) -> list[int]:
```
### Rules
- `answer[i]` multiplies the elements at every index other than `i`, including any zeros among them.
- Equal values are separate elements: leaving out `nums[i]` removes only the element at index `i`, not other elements with the same value.
- Do not use the division operator anywhere in the computation.
- Return the products in index order, one per element of `nums`.
### Constraints
- `2 <= len(nums) <= 10^5`
- `-30 <= nums[i] <= 30`
- the product of every prefix of `nums`, the product of every suffix of `nums`, and every value of `answer` lie between `-2^31` and `2^31 - 1`
### Examples
**Example 1**
```text
Input: nums = [2, 3, 4, 5]
Output: [60, 40, 30, 24]
```
For example, `answer[1] = 2 × 4 × 5 = 40`.
**Example 2**
```text
Input: nums = [-2, 0, 3, 1]
Output: [0, -6, 0, 0]
```
Only `answer[1]` leaves out the zero: `(-2) × 3 × 1 = -6`. Every other product includes it.
**Example 3**
```text
Input: nums = [0, 4, 0]
Output: [0, 0, 0]
```
With two zeros, every product still includes at least one of them.
Overview: For each position of an integer array, compute the product of all the other elements in linear time and without using division. It tests careful handling of zeros, negative values and repeated values, and planning a single efficient pass when the obvious division shortcut is not allowed.
Given an integer array `nums`, return an array `answer` of the same length in which `answer[i]` is the product of every element of `nums` except `nums[i]`. Do not use division, and run in time linear in the length of `nums`.
### Rules
- `answer[i]` multiplies the elements at every index other than `i`, including any zeros among them.
- Equal values are separate elements: leaving out `nums[i]` removes only the element at index `i`, not other elements with the same value.
- Do not use the division operator anywhere in the computation.
- Return the products in index order, one per element of `nums`.
### Constraints
- `2 <= len(nums) <= 10^5`
- `-30 <= nums[i] <= 30`
- The product of every prefix of `nums`, the product of every suffix of `nums`, and every value of `answer` lie between `-2^31` and `2^31 - 1` (inclusive).
Because of the last constraint, every element, every prefix or suffix product and every answer value fits in a signed 32-bit integer: no value exceeds `2^31 - 1`, so Java `int` and C++ `int` are sufficient for the input and the output.
### Example 1
```text
Input: nums = [2, 3, 4, 5]
Output: [60, 40, 30, 24]
```
For example, `answer[1] = 2 × 4 × 5 = 40`.
### Example 2
```text
Input: nums = [-2, 0, 3, 1]
Output: [0, -6, 0, 0]
```
Only `answer[1]` leaves out the zero: `(-2) × 3 × 1 = -6`. Every other product includes it.
Constraints
- 2 <= len(nums) <= 10^5
- -30 <= nums[i] <= 30
- The product of every prefix of nums, the product of every suffix of nums, and every value of answer lie between -2^31 and 2^31 - 1 (inclusive)
- Do not use the division operator; run in time linear in len(nums)
Examples
Input: ([2, 3, 4, 5],)
Expected Output: [60, 40, 30, 24]
Explanation: Source Example 1: no zeros; each entry is the product of the other three values.
Input: ([-2, 0, 3, 1],)
Expected Output: [0, -6, 0, 0]
Explanation: Source Example 2: only index 1 leaves out the single zero, (-2) x 3 x 1 = -6.
Hints
- Work through Example 2 by hand: notice which outputs a single zero affects, then ask how a second zero would change them.
- Equal values at different indices are separate elements; leaving out nums[i] never removes its duplicates.
- The constraints guarantee that every prefix product, suffix product and answer fits in a signed 32-bit integer, so no big-number handling is needed.