Skip to main content

238. Product of Array Except Self

medium

Return an array where each element is the product of all other elements in the input. The catch: no division allowed and O(n) time. Tests prefix/suffix-product thinking.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given 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]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.

Constraints

  • 2 <= nums.length <= 10^5
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Examples

Example 1

Input
nums = [1,2,3,4]
Output
[24,12,8,6]

Example 2

Input
nums = [-1,1,0,-3,3]
Output
[0,0,9,0,0]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Division would be easy (total / nums[i]) but it's banned — and breaks on zeros anyway.

Hint 2

Think of answer[i] as (product of everything left of i) * (product of everything right of i).

Hint 3

Two passes: first pass fills answer[i] with the prefix product. Second pass walks right-to-left, multiplying by a running suffix product.

Solution approach

Reveal approach

Two passes, no extra arrays beyond the output. First left-to-right: answer[i] = product of nums[0..i-1] (so answer[0] = 1). Then right-to-left with a running variable suffix initialized to 1: answer[i] *= suffix, then suffix *= nums[i]. After both passes, answer[i] holds prefix * suffix = product of everything except nums[i]. O(n) time, O(1) extra space (output array doesn't count by convention).

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • prefix-sum

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • Apple
  • LinkedIn

More Arrays practice problems

See all Arrays problems →