💬 Discord
Sign In
NeetCode #102LC-238MediumArrays & HashingBlind 75NC 150NC 250
← Back to All Problems

#102 · #238 · Product of Array Except Self(除自身以外数组的乘积)

📌 Problem Statement & Constraints

Given an integer array nums, return an array answer where answer[i] is the product of all elements of nums except nums[i]. Constraints: 2 <= nums.length <= 10^5, -30 <= nums[i] <= 30. The product of any prefix or suffix fits in a 32-bit integer. You must solve it in O(n) time and without using division.

💡 Core Algorithmic Approaches

  1. Division is banned precisely because it breaks on zeros: with one zero every other position is 0 and the zero position is the product of the rest; with two or more zeros everything is 0. Special-casing that is error-prone.
  2. Instead, split the product into a prefix part and a suffix part: answer[i] = (nums[0]*...*nums[i-1]) * (nums[i+1]*...*nums[n-1]).
  3. Pass 1 (left to right): write the running prefix product into answer[i].
  4. Pass 2 (right to left): keep a running suffix product and multiply it into answer[i]. This needs only one output array, so extra space is O(1).

💻 Benchmark Python3 Implementation

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n
        # Pass 1: answer[i] = product of everything strictly to the left of i
        prefix = 1
        for i in range(n):
            answer[i] = prefix
            prefix *= nums[i]
        # Pass 2: multiply in the product of everything strictly to the right
        suffix = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= suffix
            suffix *= nums[i]
        return answer

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): exactly two linear passes, with constant work per element.
💾 Space Complexity
O(1) extra space beyond the output array. A naive two-array solution (separate prefix and suffix arrays) would use O(n) extra.

⚠️ Interview Pitfalls & Follow-ups

  • Using division with a zero-count special case: it works, but the branches multiply and it is easy to get the two-zero case wrong. Interviewers usually prefer the prefix/suffix decomposition.
  • Forgetting that the output array does not count toward space complexity: LeetCode's follow-up explicitly allows O(1) extra space excluding the answer.
  • Initialising the prefix/suffix accumulators to 0: they must start at 1, the multiplicative identity.
  • Overwriting nums in place: it saves nothing here and destroys the input, which the follow-up question may forbid.