Coding problem · Medium · Arrays & Hashing

Product of Array Except Self

Medium Algorithms & data structures Seen at Amazon, Meta, Apple, Asana

Given an integer array nums, return an array answer where answer[i] is the product of all elements except nums[i]. Solve it in O(n) without using division.

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
Products fit in a 32-bit integer

Hints

Hint 1

answer[i] = (product of everything left of i) × (product of everything right of i).

Hint 2

Fill prefix products in one pass, then multiply by a running suffix product in a second pass from the right.

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

Time O(n) · Space O(1) extra (output excluded)

Two passes: left-to-right stores the prefix product before each index, then right-to-left multiplies by a running suffix product. The output array doubles as prefix storage, so extra space is O(1).

Reference solution

function productExceptSelf(nums) {
  const n = nums.length;
  const out = new Array(n).fill(1);
  for (let i = 1; i < n; i++) out[i] = out[i - 1] * nums[i - 1];
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    out[i] *= suffix;
    suffix *= nums[i];
  }
  return out.map((x) => x + 0); // normalise -0
}

function productExceptSelf(nums: number[]): number[] {
  const n = nums.length;
  const out = new Array<number>(n).fill(1);
  for (let i = 1; i < n; i++) out[i] = out[i - 1] * nums[i - 1];
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    out[i] *= suffix;
    suffix *= nums[i];
  }
  return out.map((x) => x + 0);
}

def product_except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    out = [1] * n
    for i in range(1, n):
        out[i] = out[i - 1] * nums[i - 1]
    suffix = 1
    for i in range(n - 1, -1, -1):
        out[i] *= suffix
        suffix *= nums[i]
    return out

<?php

function productExceptSelf(array $nums): array
{
    $n = count($nums);
    $out = array_fill(0, $n, 1);
    for ($i = 1; $i < $n; $i++) {
        $out[$i] = $out[$i - 1] * $nums[$i - 1];
    }
    $suffix = 1;
    for ($i = $n - 1; $i >= 0; $i--) {
        $out[$i] *= $suffix;
        $suffix *= $nums[$i];
    }
    return $out;
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] out = new int[n];
        out[0] = 1;
        for (int i = 1; i < n; i++) out[i] = out[i - 1] * nums[i - 1];
        int suffix = 1;
        for (int i = n - 1; i >= 0; i--) {
            out[i] *= suffix;
            suffix *= nums[i];
        }
        return out;
    }
}

Common mistakes

Using division breaks with zeros — and the problem forbids it.