values. Build an array of the same length whose element at position i is the product of every element of values except values[i].
Division is off limits, and the solution must run in O(n).
The product of any prefix and any suffix of values is guaranteed to fit in a signed 32-bit integer.
Bonus: can you manage with O(1) extra memory, not counting the output?values=[2, 5, 3, 1] → [15, 6, 10, 30]
For index 0: 5 · 3 · 1 = 15; for index 1: 2 · 3 · 1 = 6, and so on.
values=[4, 0, -2, 3] → [0, -24, 0, 0]
The zero sits at index 1, so only that position gets a non-zero answer: 4 · (-2) · 3 = -24.
values=[-1, 7] → [7, -1]
Each element simply gets its only neighbour.
values=[2, 5, 3, 1]
[15, 6, 10, 30]
Run checks the first 3 tests in your browser. Submit checks all 63 tests on the server, hidden ones included.