Product of Array Except Self

Return an array where each element is the product of all elements except the element at that index.

Language Selection

Choose your preferred programming language

Showing: Python

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 operator.

Examples

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]
Explanation: 
- answer[0] = 2*3*4 = 24
- answer[1] = 1*3*4 = 12
- answer[2] = 1*2*4 = 8
- answer[3] = 1*2*3 = 6

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
Explanation: 
- answer[0] = 1*0*(-3)*3 = 0
- answer[1] = (-1)*0*(-3)*3 = 0
- answer[2] = (-1)*1*(-3)*3 = 9
- answer[3] = (-1)*1*0*3 = 0
- answer[4] = (-1)*1*0*(-3) = 0

Constraints

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Approach 1: Left and Right Product Arrays

Algorithm

Use two arrays to store the product of all elements to the left and right of each index.

Steps:

Create left array: left[i] = product of all elements to the left of i
Create right array: right[i] = product of all elements to the right of i
For each index i, answer[i] = left[i] * right[i]
Return the answer array

Implementation

Python:

def productExceptSelf(nums):
    """
    Find product except self using left and right arrays
    Time: O(n)
    Space: O(n)
    """
    n = len(nums)
    
    # Left array: product of all elements to the left
    left = [1] * n
    for i in range(1, n):
        left[i] = left[i-1] * nums[i-1]
    
    # Right array: product of all elements to the right
    right = [1] * n
    for i in range(n-2, -1, -1):
        right[i] = right[i+1] * nums[i+1]
    
    # Answer array: left[i] * right[i]
    answer = [0] * n
    for i in range(n):
        answer[i] = left[i] * right[i]
    
    return answer

Java:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        
        // Left array: product of all elements to the left
        int[] left = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i-1] * nums[i-1];
        }
        
        // Right array: product of all elements to the right
        int[] right = new int[n];
        right[n-1] = 1;
        for (int i = n-2; i >= 0; i--) {
            right[i] = right[i+1] * nums[i+1];
        }
        
        // Answer array: left[i] * right[i]
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = left[i] * right[i];
        }
        
        return answer;
    }
}

Go:

func productExceptSelf(nums []int) []int {
    n := len(nums)
    
    // Left array: product of all elements to the left
    left := make([]int, n)
    left[0] = 1
    for i := 1; i < n; i++ {
        left[i] = left[i-1] * nums[i-1]
    }
    
    // Right array: product of all elements to the right
    right := make([]int, n)
    right[n-1] = 1
    for i := n-2; i >= 0; i-- {
        right[i] = right[i+1] * nums[i+1]
    }
    
    // Answer array: left[i] * right[i]
    answer := make([]int, n)
    for i := 0; i < n; i++ {
        answer[i] = left[i] * right[i]
    }
    
    return answer
}

JavaScript:

function productExceptSelf(nums) {
    const n = nums.length;
    
    // Left array: product of all elements to the left
    const left = new Array(n);
    left[0] = 1;
    for (let i = 1; i < n; i++) {
        left[i] = left[i-1] * nums[i-1];
    }
    
    // Right array: product of all elements to the right
    const right = new Array(n);
    right[n-1] = 1;
    for (let i = n-2; i >= 0; i--) {
        right[i] = right[i+1] * nums[i+1];
    }
    
    // Answer array: left[i] * right[i]
    const answer = new Array(n);
    for (let i = 0; i < n; i++) {
        answer[i] = left[i] * right[i];
    }
    
    return answer;
}

C#:

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {
        int n = nums.Length;
        
        // Left array: product of all elements to the left
        int[] left = new int[n];
        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i-1] * nums[i-1];
        }
        
        // Right array: product of all elements to the right
        int[] right = new int[n];
        right[n-1] = 1;
        for (int i = n-2; i >= 0; i--) {
            right[i] = right[i+1] * nums[i+1];
        }
        
        // Answer array: left[i] * right[i]
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = left[i] * right[i];
        }
        
        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n) - Three passes through the array
Space Complexity: O(n) - For the left and right arrays

Approach 2: Space Optimized (Optimal)

Algorithm

Use the answer array itself to store the left products, then use a variable to track right products.

Steps:

First pass: Store left products in answer array
Second pass: Use a variable to track right products and multiply with left products
Return the answer array

Implementation

Python:

def productExceptSelfOptimized(nums):
    """
    Find product except self with space optimization
    Time: O(n)
    Space: O(1) excluding output array
    """
    n = len(nums)
    answer = [1] * n
    
    # First pass: store left products in answer array
    for i in range(1, n):
        answer[i] = answer[i-1] * nums[i-1]
    
    # Second pass: use variable to track right products
    right_product = 1
    for i in range(n-1, -1, -1):
        answer[i] = answer[i] * right_product
        right_product *= nums[i]
    
    return answer

Java:

class Solution {
    public int[] productExceptSelfOptimized(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        
        // First pass: store left products in answer array
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i-1] * nums[i-1];
        }
        
        // Second pass: use variable to track right products
        int rightProduct = 1;
        for (int i = n-1; i >= 0; i--) {
            answer[i] = answer[i] * rightProduct;
            rightProduct *= nums[i];
        }
        
        return answer;
    }
}

Go:

func productExceptSelfOptimized(nums []int) []int {
    n := len(nums)
    answer := make([]int, n)
    
    // First pass: store left products in answer array
    answer[0] = 1
    for i := 1; i < n; i++ {
        answer[i] = answer[i-1] * nums[i-1]
    }
    
    // Second pass: use variable to track right products
    rightProduct := 1
    for i := n-1; i >= 0; i-- {
        answer[i] = answer[i] * rightProduct
        rightProduct *= nums[i]
    }
    
    return answer
}

JavaScript:

function productExceptSelfOptimized(nums) {
    const n = nums.length;
    const answer = new Array(n);
    
    // First pass: store left products in answer array
    answer[0] = 1;
    for (let i = 1; i < n; i++) {
        answer[i] = answer[i-1] * nums[i-1];
    }
    
    // Second pass: use variable to track right products
    let rightProduct = 1;
    for (let i = n-1; i >= 0; i--) {
        answer[i] = answer[i] * rightProduct;
        rightProduct *= nums[i];
    }
    
    return answer;
}

C#:

public class Solution {
    public int[] ProductExceptSelfOptimized(int[] nums) {
        int n = nums.Length;
        int[] answer = new int[n];
        
        // First pass: store left products in answer array
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i-1] * nums[i-1];
        }
        
        // Second pass: use variable to track right products
        int rightProduct = 1;
        for (int i = n-1; i >= 0; i--) {
            answer[i] = answer[i] * rightProduct;
            rightProduct *= nums[i];
        }
        
        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n) - Two passes through the array
Space Complexity: O(1) excluding the output array

Key Insights

Left and Right Products: Each element is the product of left and right subarrays
Space Optimization: Use the answer array itself to store intermediate results
No Division: Avoid division operator as it can cause issues with zeros
Two Passes: First pass for left products, second pass for right products
Variable Tracking: Use a variable to track right products instead of an array

Edge Cases

Zeros: [1,0,3,4] → [0,12,0,0]
Multiple Zeros: [0,0,3,4] → [0,0,0,0]
Negative Numbers: [-1,1,0,-3,3] → [0,0,9,0,0]
Two Elements: [1,2] → [2,1]
All Same: [2,2,2] → [4,4,4]

Test Cases

def test_product_except_self():
    # Basic case
    assert productExceptSelf([1,2,3,4]) == [24,12,8,6]
    
    # With zeros
    assert productExceptSelf([-1,1,0,-3,3]) == [0,0,9,0,0]
    
    # Two elements
    assert productExceptSelf([1,2]) == [2,1]
    
    # All same
    assert productExceptSelf([2,2,2]) == [4,4,4]
    
    # Negative numbers
    assert productExceptSelf([-1,-2,-3]) == [6,3,2]
    
    print("All tests passed!")

test_product_except_self()

Follow-up Questions

Product with Division: What if you could use the division operator?
Multiple Arrays: How would you handle multiple arrays?
Streaming Data: How would you handle streaming data?
Range Queries: What if you need to answer range product queries?
Modular Arithmetic: What if you need to compute products modulo a number?

Common Mistakes

Using Division: Trying to use division operator which can cause issues with zeros
Not Handling Zeros: Not properly handling arrays with zero elements
Space Complexity: Not optimizing space usage
Index Errors: Off-by-one errors in array indexing

Interview Tips

Clarify Requirements: Ask about division operator and space constraints
Discuss Approaches: Mention both left-right arrays and space-optimized approaches
Handle Edge Cases: Discuss arrays with zeros and negative numbers
Optimize Space: Focus on the O(1) space solution
Explain Algorithm: Walk through the two-pass approach

Variations

Product with Division: Allow division operator for simpler solution
Multiple Arrays: Handle multiple input arrays
Streaming Data: Handle data arriving one element at a time
Range Queries: Answer range product queries efficiently
Modular Arithmetic: Compute products modulo a number