Product Of Array Except Self

Array Algorithm Medium

Python Java C++

def productExceptSelf(nums):
    # Initialize result array with 1s
    res = [1] * len(nums)
    
    # Track running products from both ends
    left = right = 1
    j = len(nums) - 1
    
    # Calculate products in single pass
    for i in range(len(nums)):
        res[i] *= left
        left *= nums[i]
        
        res[j - i] *= right
        right *= nums[j - i]
        
    return res

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] res = new int[nums.length];
        Arrays.fill(res, 1);

        int left = 1, right = 1, j = nums.length - 1;

        for (int i = 0; i < nums.length; i++) {
            res[i] *= left;
            left *= nums[i];

            res[j - i] *= right;
            right *= nums[j - i];
        }

        return res;
    }
}

class Solution {
public:
    vector productExceptSelf(vector& nums) {
        vector res(nums.size(), 1);
        
        int left = 1, right = 1;
        int j = nums.size() - 1;
        
        for (int i = 0; i < nums.size(); i++) {
            res[i] *= left;
            left *= nums[i];
            
            res[j - i] *= right;
            right *= nums[j - i];
        }
        
        return res;
    }
};

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 solve it in O(n) time and without using division.

Detailed Explanation

Approach

This solution uses a clever approach to calculate products from both ends simultaneously. Instead of using separate left and right product arrays, we compute both in a single pass using two running products.

Key Concepts

1. Running Products: Maintain left and right running products as we traverse the array
2. Two-Way Traversal: Update products from both ends in the same loop
3. Space Optimization: Use output array as storage instead of separate left/right arrays

Algorithm Steps

1. Initialize result array with 1s
2. Initialize left and right running products as 1
3. For each index i:
   • Multiply res[i] by left product
   • Update left product with nums[i]
   • Multiply res[j-i] by right product
   • Update right product with nums[j-i]

Visual Example

Input: nums = [1,2,3,4] Step by step: i=0: left=1, right=1 res = [1,1,1,1] After left: [1,1,1,1] After right: [1,1,1,4] left=1, right=4 i=1: res = [1,1,1,4] After left: [1,1,1,4] After right: [1,1,12,4] left=2, right=12 i=2: res = [1,1,12,4] After left: [1,2,12,4] After right: [1,8,12,4] left=6, right=24 i=3: res = [1,8,12,4] After left: [1,8,12,24] After right: [24,8,12,6] Final output: [24,12,8,6]

Time and Space Complexity

• Time Complexity: O(n) - Single pass through the array
• Space Complexity: O(1) - Only using the output array

Why This Works

For each index i, we need the product of all numbers before i (prefix) multiplied by the product of all numbers after i (suffix). By maintaining running products from both ends, we build these prefix and suffix products simultaneously without needing extra space.

Edge Cases

• Array length = 1: Return [1]
• Contains zeros: Works correctly
• Negative numbers: Works correctly
• Maximum/minimum products: Guaranteed to fit in 32-bit integer

Common Mistakes

• Using division (not allowed by problem constraints)
• Creating separate prefix and suffix arrays (uses extra space)
• Not handling array bounds correctly
• Forgetting to update running products