arrays · Problem 3 of 3
Product of Array Except Self
medium
Amazon
Meta
Apple
Uber
Stripe
AmazonMetaAppleUberStripeGiven 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].
You must write an algorithm that runs in O(n) time and without using the division operation.
productExceptSelf([1, 2, 3, 4]) -> [24, 12, 8, 6]
productExceptSelf([-1, 1, 0, -3, 3]) -> [0, 0, 9, 0, 0]Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Running is free — Submit is what records it. Or press ⌘↩
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| productExceptSelf([1,2,3,4]) | positive integers | [24,12,8,6] | — |
| productExceptSelf([-1,1,0,-3,3]) | with single zero | [0,0,9,0,0] | — |
| productExceptSelf([2,5]) | two elements | [5,2] | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(n)
- target space
- O(1) auxiliary space (excluding the output array)
Two linear passes compute prefix products and suffix products in-place without division.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left