Example 1
ready- Input
nums = [ 1, 2, 3, 4 ]- Expected
[ 24, 12, 8, 6 ]- Why
- each position receives the product of the other three values
Product of Array Except Self
35 min · productExceptSelf()mediumOpen in LeetCode #238 ↗
Imagine removing one item from a chain of multipliers. You need the result for every possible removal, but recomputing the whole chain each time gets expensive fast.
Given an integer array nums, return an array out of the same length where out[i]
is the product of every value in nums except nums[i].
A few ground rules:
- Don't use division.
- Keep the output in the same index order as the input.
- Zeros and negative values are valid input; the rule above handles them without a special output format.
Constraints
2 <= nums.length <= 100_000- A prefix product multiplies a run from the start of the array; a suffix product
does the same from the end. Every such running product and every answer value fits in
a signed 32-bit integer:
|value| < 2^31.
Hints
Split around the missing index
Everything except nums[i] has two parts: values to the left of i, and values to
the right. Can you compute those two products without division?
Store the left side first
Walk left to right with a running product. Before multiplying by nums[i], store
that running product in out[i]; it now represents everything strictly to the left.
Fold in the right side
Walk right to left with a second running product. Multiply it into out[i], then
update it with nums[i]. The output array can hold the prefix work, so you don't
need a second helper array.
Follow-up
Can you solve it with constant extra space when the returned array doesn't count toward the space budget?
Visible cases
Examples
Example 2
ready- Input
nums = [ 2, 0, 4 ]- Expected
[ 0, 8, 0 ]- Why
- the zero's position keeps the product 2 × 4; the others become zero
Example 3
ready- Input
nums = [ -1, 2, -3, 4 ]- Expected
[ -24, 12, -8, 6 ]- Why
- the signs change according to the excluded value
Interview signal
Asked at
AmazonMetaMicrosoftApple
Brute force — rebuild every product
For each output position i, scan the entire input and multiply every value whose
position isn't i. It follows the definition directly, which makes it a useful oracle.
def product_except_self(nums: list[int]) -> list[int]:
answer: list[int] = []
for skipped in range(len(nums)):
product = 1
for i, value in enumerate(nums):
if i != skipped:
product *= value
answer.append(product)
return answerTime O(n²) — each of n output positions scans n input values. Space O(1)
besides the returned array.
The repeated work is hiding in plain sight. Neighboring output positions reuse almost all the same factors; only the point where "left" becomes "right" moves.
Prefix + suffix products
A prefix product is the product of values before a position. On the first pass, store that left-side product directly in the answer array. Then walk backwards with a running suffix product — the product of values after the current position — and multiply it into the stored prefix.
def product_except_self(nums: list[int]) -> list[int]:
answer = [1] * len(nums)
prefix = 1
for i, value in enumerate(nums):
answer[i] = prefix
prefix *= value
suffix = 1
for i in range(len(nums) - 1, -1, -1):
answer[i] *= suffix
suffix *= nums[i]
return answerAt index i, answer[i] holds the product strictly to its left, while suffix holds
the product strictly to its right. Their product excludes exactly nums[i]. This logic
also handles zeros naturally: one zero leaves only its own position potentially nonzero,
and two zeros force every output to zero.
Time O(n) — one forward pass and one backward pass. Space O(1) beyond the output array; the two running products are the only extra storage.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[ 24, 12, 8, 6 ]
Run: visible + custom · Submit: full suite