Return an array where each element is the product of all others.

Interview question: Product of Array Except Self

Given an integer array `nums`, return an array `answer` such that `answer[i]` is equal to the product of all the elements of `nums` except `nums[i]`.

Solve it without using the division operation.

- 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.