Product of All Others
MediumArrays & Hashing
Problem
Given an integer array nums, return an array out where out[i] is the product of every element of nums except nums[i].
You may not use division (the array may contain zeros), and the solution should run in linear time. Every product is guaranteed to fit in a 32-bit signed integer.
Example 1
- Input:
- nums = [2, 3, 4, 5]
- Output:
- [60, 40, 30, 24]
out[0] = 3·4·5 = 60, out[1] = 2·4·5 = 40, and so on.
Example 2
- Input:
- nums = [-1, 2, 0, 3]
- Output:
- [0, 0, -6, 0]
Only the position holding the zero avoids multiplying by zero: (-1)·2·3 = -6.
Constraints
- 2 ≤ nums.length ≤ 10^5
- -30 ≤ nums[i] ≤ 30
- Every prefix and suffix product fits in a 32-bit signed integer.
Hint
Show the first hint
out[i] splits naturally into two parts: everything to the left of i and everything to the right of i.
Walkthrough
How to approach it
01Clarify before coding
- Why no division? Zeros make total / nums[i] undefined; the interviewer wants the prefix/suffix idea.
- Can the products overflow? No, they are guaranteed to fit in 32 bits.
- Does the output array count as extra space? Usually not; aim for O(1) beyond it.
02Brute force
For each i, multiply all other elements in a nested loop.
Cost: O(n²) time: 10^10 multiplications for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.