Product of array except self

Question

Given an integer array nums, return an array out where out[i] is the product of all elements except nums[i]. Solve it in O(n) time without using the division operator. (Division would break on zeros anyway.)

Accepted Answer

Split each answer into a left-product and a right-product: out[i] = (∏{j<i} nums[j]) · (∏{ji} nums[j]). First sweep left to right, writing the running prefix product into out[i] (the product of everything strictly before i). Then sweep right to left carrying a running suffix product R, multiplying it in. No division, and the output array doubles as the prefix buffer so we use only O(1) extra space. Tracing nums = [1, 2, 3, 4]: after the forward pass out = [1, 1, 2, 6] (prefix products). The backward pass with right starting at 1 gives out[3] = 6·1 = 6, then right = 4; out[2] = 2·4 = 8, right …

Product of array except self

Your answer

More Coding questions