Product of Array Except Self

Trapping Rain Water

Climbing Stairs

Build prefix and suffix products without division.

Return an array where output index `i` equals the product of every value in `nums` except `nums[i]`. Do not use division.

**Input / output**
- Input: `nums: integer[]`
- Output: `integer[]` of equal length

**Examples**
1. `[1,2,3,4]` returns `[24,12,8,6]`.
2. `[-1,1,0,-3,3]` returns `[0,0,9,0,0]`.

**Constraints**
- `2 <= nums.length <= 100,000`
- Every prefix and suffix product fits a 32-bit signed integer

**Follow-up**
Can you store suffix accumulation in one variable so output space is the only allocated array?

- For each index `i`, the answer should be the product of every number except `nums[i]`.
- Division is not allowed, so we cannot compute one total product and divide by the current value.
- The output order must match the input order exactly.

Understand Each Output Position

- For each index, multiply all values at every other index.
- This is correct and handles zeroes, but it repeats almost the same multiplication for every position.
- The nested loops make the time complexity O(n²).

Consider the Brute Force Idea

- The product except self is the product of everything to the left times everything to the right.
- A prefix pass can store products before each index.
- A suffix pass can multiply in products after each index.

Split the Product into Left and Right Parts

- Start with an answer array filled with `1`.
- Move left to right while carrying a running prefix product.
- Before multiplying by `nums[i]`, store the product of all values to the left in `answer[i]`.

Fill Prefix Products First

- The second pass moves right to left with a running suffix product.
- Multiplying `answer[i]` by the suffix gives left product times right product, excluding `nums[i]` itself.
- Time complexity is O(n), and extra space is O(1) besides the required output array.