Given an integer array nums, build an array answer of the same length where answer[i] is the product of every element of nums except nums[i]. Division is off the table — an element can be zero — and the whole thing must run in O(n).
Examples
Example 1:
Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Example 2:
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Explanation: only the position holding the 0 sees the product of everything else.
Example 3:
Input: nums = [2,2]
Output: [2,2]
Example 4:
Input: nums = [5,0,0]
Output: [0,0,0]
Explanation: with two zeros, every position's "everything else" contains a zero.
Constraints
2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
Every prefix and suffix product fits in a 32-bit integer.
Prerequisites
Hash sets and hash maps — expected O(1) membership and lookup, and what "expected" costs when hashes collide. Array traversal, and the habit of asking what a second pass buys over a nested loop.
How to think about it
1. Prefix and Suffix Products Optimal
Intuition
Everything except me is everything before me times everything after me. Two sweeps compute those halves, and no division is needed — which matters, because a single zero would make division meaningless and two zeros would make it wrong.
Algorithm
1. Sweep left to right filling answer[i] with the product of everything before i. 2. Sweep right to left multiplying answer[i] by a running product of everything after i. 3. Each position now holds before x after, which is the answer.
Time & Space
Time O(n) — two passes. Space O(1) beyond the output array, since the running products are single variables.