Product of Array Except Self

Problem

Given an integer array nums, build an array answer where answer[i] is the product of every element of nums except nums[i]. Division is not allowed.

• The array has at least 2 and at most 150,000 elements.
• Values are small (between -20 and 20), and every prefix or suffix product fits in a signed 32-bit integer, so overflow is not a concern for the intended solution.

Examples

• nums = [3, 5, 2, 4] → [40, 24, 60, 30]. For index 0: 5 * 2 * 4 = 40.
• nums = [6, -2, 0, 5] → [0, 0, -60, 0]. Only index 2 excludes the zero, so only it is nonzero: 6 * -2 * 5 = -60.
• nums = [7, 9] → [9, 7]. With two elements each answer is simply the other element.

Hints

1. "Everything except nums[i]" is "everything to the left of i" times "everything to the right of i."
2. Both of those can be computed for every i in one sweep each.
3. Fill the output with left products first, then walk from the right multiplying in a running suffix product; that avoids a second array.