Skip to content

Practice Product of Array Except Self

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#238
LeetCode Problem

Product of Array Except Self

Problem Statement

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. Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Source: Product of Array Except Self on LeetCode. Use the original task for its coding environment and submissions.

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]

Constraints

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
The input is generated such that answer[i] is guaranteed to fit in a 32-bit integer.

How to solve Product of Array Except Self

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

The product of everything except index i equals the product of the elements before i times the product of the elements after i, and both come from running products in two passes, which avoids division and handles zeros naturally.

Why brute force is not enough

Multiplying all other elements for each index is O(n^2), about 10^10 operations for n up to 10^5. Dividing the total product by each element is linear but uses the forbidden division and breaks when a zero is present.

Approach

  1. Fill the output left to right so position 0 holds 1 and every other position holds the product of all elements strictly before it; the invariant is that position i holds the prefix product of indices 0 through i-1.
  2. Sweep right to left carrying a running suffix product that starts at 1.
  3. At each index, multiply the stored prefix by the suffix and write it back, then multiply the suffix by the current element so it covers everything strictly after the next index to visit.
  4. When the sweep finishes, every position holds prefix times suffix, the product of all other elements.
  5. The output holds the prefixes and the suffix is one variable, so extra space beyond the output is constant, satisfying the follow-up.

Walkthrough of Example 1

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

  1. Left pass: position 0 gets 1, position 1 gets 1, position 2 gets 1 * 2 = 2, position 3 gets 1 * 2 * 3 = 6, so the array is [1,1,2,6].
  2. Right pass with suffix 1: at index 3 the result is 6 * 1 = 6, and the suffix becomes 4.
  3. At index 2 the result is 2 * 4 = 8, and the suffix becomes 12.
  4. At index 1 the result is 1 * 12 = 12, and the suffix becomes 24.
  5. At index 0 the result is 1 * 24 = 24, giving [24,12,8,6].

Time and space

Time O(n) · Space O(1) extra. n is nums.length; two linear passes do constant work per element, and apart from the required output only one running suffix variable is kept.

Interview pitfalls

  • Reaching for division, which is disallowed and fails with zeros; example 2 has one zero and expects 9 at that position with 0 everywhere else.
  • Including the current element in its own prefix or suffix, an off-by-one that yields the total product at every index.
  • Updating the suffix before using it in the right pass, which shifts every result by one position.
  • Two or more zeros must yield all zeros; the two-pass method does this automatically, but patched division logic often does not.

Follow-up questions interviewers ask

  • If the array changes between queries, how would you answer repeated product-except-one queries?
  • How would you handle exactly one zero versus several if division were allowed?
  • Does the same two-pass idea work for sums or XOR, and when is it unnecessary?

Further reading on the technique: Prefix sum

Related LeetCode Problems

Practice more problems similar to Product of Array Except Self.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.