Skip to main content

🟨 Product of Array Except Self (#238)

🔗 Problem Link​

📋 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].

You must write an algorithm that runs in O(n) time and without using the division operation.

💡 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]

🔑 Key Insights & Approach​

Core Observation: For each position, the result is the product of all elements to its left multiplied by the product of all elements to its right.

Why Prefix/Suffix Products?

  • O(n) time complexity without division
  • Can compute left and right products in two passes
  • Space optimized by using output array for prefix

Approaches:

  1. Prefix and Suffix arrays: O(n) time, O(n) space
  2. Optimized: Use output array to store prefix, then multiply by suffix: O(n) time, O(1) extra space

Pattern: "Prefix/Suffix Product" pattern - breaking down problem into left and right perspectives.

🐍 Solution: Python​

Approach: Prefix and Suffix (Space Optimized)​

Time Complexity: O(n) | Space Complexity: O(1) - output array doesn't count

from typing import List

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

        # Calculate prefix products (left to right)
        prefix = 1
        for i in range(n):
            result[i] = prefix
            prefix *= nums[i]

        # Calculate suffix products and multiply (right to left)
        suffix = 1
        for i in range(n - 1, -1, -1):
            result[i] *= suffix
            suffix *= nums[i]

        return result

Approach 2: Using Separate Arrays (Easier to Understand)​

Time Complexity: O(n) | Space Complexity: O(n)

from typing import List

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

        # Prefix products
        prefix = [1] * n
        for i in range(1, n):
            prefix[i] = prefix[i-1] * nums[i-1]

        # Suffix products
        suffix = [1] * n
        for i in range(n-2, -1, -1):
            suffix[i] = suffix[i+1] * nums[i+1]

        # Combine
        result = [prefix[i] * suffix[i] for i in range(n)]
        return result

🔵 Solution: Golang​

Approach: Prefix and Suffix (Space Optimized)​

Time Complexity: O(n) | Space Complexity: O(1)

func productExceptSelf(nums []int) []int {
    n := len(nums)
    result := make([]int, n)

    // Calculate prefix products
    prefix := 1
    for i := 0; i < n; i++ {
        result[i] = prefix
        prefix *= nums[i]
    }

    // Calculate suffix products and multiply
    suffix := 1
    for i := n - 1; i >= 0; i-- {
        result[i] *= suffix
        suffix *= nums[i]
    }

    return result
}

📚 References​