Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Product of Array Except Self

Arrays & Two-Pointersmedium

Implement `productExceptSelf(nums)` that returns an array `out` where `out[i]` is the product of every element of `nums` except `nums[i]`. Solve it in O(n) time **without using division**.

Examples

Input: [1, 2, 3, 4]
Output: [24, 12, 8, 6]
out[0] = 2*3*4 = 24, out[1] = 1*3*4 = 12, and so on.
Input: [2, 3, 4]
Output: [12, 8, 6]

Sample tests

Input: productExceptSelf([1,2,3,4])
Output: [24,12,8,6]
Input: productExceptSelf([2,3,4])
Output: [12,8,6]

+ 2 hidden tests run on Submit.

Hints

Common pitfalls
  • Reaching for division breaks when any element is 0.
  • Allocating an O(n) prefix and an O(n) suffix array works but the two-pass approach needs only the output array.

Learning resources

  • Wikipedia: Array data structure
Approach & explanation (try first)

The product of all-but-i equals (product of everything left of i) times (product of everything right of i). One forward pass fills the left products into the result, and one backward pass multiplies in the right products using a running accumulator. O(n) time, O(1) extra space.

Loading...
⌘/Ctrl + Enter

Run your code to see results.