Compute the Product of an Array Except Self
Company: Microsoft
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
The interview report preserved the input-output example but not every original restriction. The following is a self-contained version of the reported array-product task.
Implement:
```python
def product_except_self(nums: list[int]) -> list[int]:
...
```
Given an integer array `nums`, return an array `answer` of the same length such that `answer[i]` is the product of every element of `nums` except `nums[i]`.
Do not use division. Your algorithm must run in `O(n)` time and use `O(1)` auxiliary space apart from the returned array.
Constraints:
- `2 <= len(nums) <= 100_000`
- `-30 <= nums[i] <= 30`
- Every prefix product, suffix product, and requested output fits in a signed 64-bit integer.
- The input may contain zero, multiple zeros, and negative values.
- Do not mutate `nums`.
Examples:
```text
Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
```
```text
Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
```
Quick Answer: Tackle the product-of-array-except-self problem under linear-time and constant-auxiliary-space constraints. It assesses array reasoning, careful handling of zeros and negative values, input immutability, complexity analysis, and edge-case discipline.