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 is between `-(2^53 - 1)` and `2^53 - 1`, inclusive.
- 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]
```
Overview: 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.
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]`.
Implement:
```python
def product_except_self(nums):
...
```
Do not use division. Your algorithm must run in `O(n)` time and use `O(1)` auxiliary space apart from the returned array. Do not mutate `nums`.
**Output semantics**
- Return a list of exactly `len(nums)` values in index order: position `i` holds the product of all elements of `nums` other than the one at position `i`.
- The answer is unique. There is no ordering, selection, or tie-breaking choice to make, so two correct solutions always agree element for element.
**Examples**
Example 1
```text
Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
```
`24 = 2*3*4`, `12 = 1*3*4`, `8 = 1*2*4`, `6 = 1*2*3`.
Example 2
```text
Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]
```
Every index except index 2 has the `0` inside its product, so its answer is `0`. Index 2 holds the `0`, and the product of the remaining elements is `(-1)*1*(-3)*3 = 9`.
**Magnitude**
Answers routinely exceed `2^31 - 1` (for example, ten copies of `30` produce `30^9 = 19683000000000` at every index), and running products reach `2^53 - 1`. Java must accumulate and return `long`, and C++ must use `long long`; a 32-bit `int` silently overflows. Python integers and JavaScript doubles represent every value in the stated range exactly.
Constraints
- 2 <= len(nums) <= 100000
- -30 <= nums[i] <= 30
- Every prefix product, every suffix product, and every value of the returned array lies in [-(2^53 - 1), 2^53 - 1]
- nums may contain zero, multiple zeros, and negative values
- Answers exceed 2^31 - 1, so Java must use long and C++ must use long long; a 32-bit int overflows
- Do not use division
- The algorithm must run in O(n) time and use O(1) auxiliary space apart from the returned array
- Do not mutate nums
Examples
Input: ([1, 2, 3, 4],)
Expected Output: [24, 12, 8, 6]
Input: ([-1, 1, 0, -3, 3],)
Expected Output: [0, 0, 9, 0, 0]
Hints
- Split answer[i] into two halves: everything strictly to the left of i, times everything strictly to the right of i.
- One of those halves can be accumulated in a single forward pass while writing directly into the output array; the other folds in on a second pass running the opposite direction.
- The returned array does not count toward auxiliary space, so it can carry a partial result between the two passes. If you never divide, zeros need no special case at all.
Community answers
Answer by MeanMedianMode
def product_except_self(nums: list[int]) -> list[int]:
n=len(nums)
answers=[1]*n
prefix=1
for i in range(n):
answers[i]=prefix
prefix *=nums[i]
suffix=1
for i in range(n-1,-1,-1):
answers[i] *=suffix
suffix *=nums[i]
return answers
Answer by Paramartha Sengupta
def product_except_self(nums):
answer=[1 for x in nums]
for i in range(0,len(nums)):
answer[i] = np.product([answer[i]*nums[j] for j in range(0,len(nums)) if j!=i])
return answer