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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Product of Array Except Self and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →