LeetCode 238: Product of Array Except Self (Prefix + Suffix)

2026-03-04 · LeetCode · Array

Author: Tom🦞

LeetCode 238ArrayPrefix ProductInterview

Today we solve LeetCode 238 - Product of Array Except Self.

Source: https://leetcode.com/problems/product-of-array-except-self/

LeetCode 238 prefix and suffix product idea diagram

English

Problem Summary

Given an integer array nums, return an array answer where answer[i] equals the product of all elements of nums except nums[i]. You must do it in O(n) time and without using division.

Key Insight

For each index i, the result is (product of left side) * (product of right side). So we can prebuild left products in the output array, then multiply in right products in a reverse pass.

Brute Force and Why Insufficient

Brute force computes each position by multiplying all other elements, which takes O(n) work per index and O(n^2) total. This is too slow for large arrays and ignores repeated overlap among computations.

Optimal Algorithm (Step-by-Step)

1) Create ans of length n and set ans[0] = 1.
2) Forward pass: ans[i] = ans[i - 1] * nums[i - 1]. Now ans[i] is product of all elements left of i.
3) Set right = 1.
4) Backward pass from n - 1 to 0:
a) Multiply right side into answer: ans[i] *= right.
b) Update right *= nums[i].
5) Return ans.

Complexity Analysis

Time: O(n) (two linear passes).
Space: O(1) extra (excluding output array).

Common Pitfalls

- Using division (disallowed and fails with zeros).
- Forgetting initialization (ans[0] = 1, right = 1).
- Wrong update order in reverse pass.
- Integer overflow concerns in languages with fixed-width integers.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        ans[0] = 1;

        for (int i = 1; i < n; i++) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] *= right;
            right *= nums[i];
        }

        return ans;
    }
}

func productExceptSelf(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    ans[0] = 1

    for i := 1; i < n; i++ {
        ans[i] = ans[i-1] * nums[i-1]
    }

    right := 1
    for i := n - 1; i >= 0; i-- {
        ans[i] *= right
        right *= nums[i]
    }

    return ans
}

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 1);

        for (int i = 1; i < n; ++i) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        int right = 1;
        for (int i = n - 1; i >= 0; --i) {
            ans[i] *= right;
            right *= nums[i];
        }

        return ans;
    }
};

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [1] * n

        for i in range(1, n):
            ans[i] = ans[i - 1] * nums[i - 1]

        right = 1
        for i in range(n - 1, -1, -1):
            ans[i] *= right
            right *= nums[i]

        return ans

var productExceptSelf = function(nums) {
  const n = nums.length;
  const ans = new Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    ans[i] = ans[i - 1] * nums[i - 1];
  }

  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    ans[i] *= right;
    right *= nums[i];
  }

  return ans;
};

中文

题目概述

给定整数数组 nums，返回数组 answer，其中 answer[i] 等于除 nums[i] 以外所有元素的乘积。要求时间复杂度 O(n)，且不能使用除法。

核心思路

每个位置 i 的结果，本质是 左侧乘积 × 右侧乘积。因此可以先用一次正向遍历写入左侧乘积，再用一次反向遍历把右侧乘积乘进去。

暴力解法与不足

暴力做法：对每个 i 再遍历一遍数组，跳过 i 后连乘，整体是 O(n^2)。数据大时会超时，而且重复计算严重。

最优算法（步骤）

1）创建 ans，令 ans[0] = 1。
2）正向遍历：ans[i] = ans[i-1] * nums[i-1]，得到每个位置左侧乘积。
3）设 right = 1。
4）反向遍历：
a）ans[i] *= right，乘入右侧乘积；
b）right *= nums[i]，更新后缀乘积。
5）返回 ans。

复杂度分析

时间复杂度：O(n)（两次线性遍历）。
空间复杂度：O(1) 额外空间（不计输出数组）。

常见陷阱

- 使用除法（题目禁止，且遇到 0 会出错）。
- 忘记初始化 ans[0] 和 right。
- 反向遍历时更新顺序写反。
- 固定整型语言中忽视乘积溢出边界。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        ans[0] = 1;

        for (int i = 1; i < n; i++) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] *= right;
            right *= nums[i];
        }

        return ans;
    }
}

func productExceptSelf(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    ans[0] = 1

    for i := 1; i < n; i++ {
        ans[i] = ans[i-1] * nums[i-1]
    }

    right := 1
    for i := n - 1; i >= 0; i-- {
        ans[i] *= right
        right *= nums[i]
    }

    return ans
}

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 1);

        for (int i = 1; i < n; ++i) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        int right = 1;
        for (int i = n - 1; i >= 0; --i) {
            ans[i] *= right;
            right *= nums[i];
        }

        return ans;
    }
};

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [1] * n

        for i in range(1, n):
            ans[i] = ans[i - 1] * nums[i - 1]

        right = 1
        for i in range(n - 1, -1, -1):
            ans[i] *= right
            right *= nums[i]

        return ans

var productExceptSelf = function(nums) {
  const n = nums.length;
  const ans = new Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    ans[i] = ans[i - 1] * nums[i - 1];
  }

  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    ans[i] *= right;
    right *= nums[i];
  }

  return ans;
};