Product of Array Except Self

Medium#238from both sides

You get an array of integers. Return an array where position i holds the product of all the numbers except nums[i]. Division is not allowed, and the time has to be O(n). Our example: [2, 3, 0, 4] — the answer is [0, 0, 24, 0]: only the 0 gets 2 × 3 × 4 = 24, every other product includes the 0.

238 Product of Array Except SelfWalkthrough · 1×

Example: [2, 3, 0, 4]. Under the numbers is answer; below it, the running products left and right.

numsanswerleft–right–02132034
not reached yetcurrent indexproduct from the leftin the product from the rightfinal answer

4 numbers, one of them 0

01/29
restart · back · play · step
Speed
1function productExceptSelf(nums):
2 n = len(nums)
3 answer = array of n ones
4 left = 1
5 for i from 0 to n - 1:
6 answer[i] = left
7 left = left * nums[i]
8 right = 1
9 for i from n - 1 down to 0:
10 answer[i] = answer[i] * right
11 right = right * nums[i]
12 return answer
state
n
4
answer
–
left
–
right
–
i
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The product of all numbers except nums[i] is the product of everything left of i times the product of everything right of i. The first pass leaves the left part in answer[i], the second multiplies in the right part.
  2. answer[i] is written before nums[i] joins left or right, so a number never gets into its own product. That is how the 0 gets 24.
  3. Division would not work here anyway: the product of everything is 0, and 0 / 0 says nothing. The two passes never divide, so a 0 is just another number.

Complexity

Time O(n): two passes. Memory O(1) besides the answer itself: left and right are single numbers.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.