Problem: Product of Array Except Self

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

Approach: Two-Pass Algorithm

The most efficient approach solves this problem in two passes using constant extra space (excluding the output array). The core idea is to build up the product from the left and right separately, then combine them.

Steps:

1. Initialization: Create an ans array of the same size as nums, filled with 1s. This array will store the final result.
2. Left Pass: Iterate through nums from left to right. For each element nums[i], ans[i] will store the product of all elements to the left of nums[i]. We achieve this by accumulating the product in a left variable.
3. Right Pass: Iterate through nums from right to left. For each element nums[i], multiply the current ans[i] (which already contains the left product) by the product of all elements to the right of nums[i]. We accumulate this right product in a right variable.

Time Complexity: O(n) - We perform two linear passes over the input array.

Space Complexity: O(1) - We use only a few variables in addition to the output array. The output array itself is not considered extra space in the space complexity analysis.

Code Examples

Below are code examples in several programming languages demonstrating this approach.

Python:

def productExceptSelf(nums):
    n = len(nums)
    ans = [1] * n  # Initialize with ones
    left = 1
    for i in range(n):
        ans[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):
        ans[i] *= right
        right *= nums[i]
    return ans
 

Java:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, 1); // Initialize with ones
        int left = 1;
        for (int i = 0; i < n; i++) {
            ans[i] = left;
            left *= nums[i];
        }
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] *= right;
            right *= nums[i];
        }
        return ans;
    }
}

C++:

vector<int> productExceptSelf(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, 1); // Initialize with ones
    int left = 1;
    for (int i = 0; i < n; i++) {
        ans[i] = left;
        left *= nums[i];
    }
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        ans[i] *= right;
        right *= nums[i];
    }
    return ans;
}

JavaScript:

var productExceptSelf = function(nums) {
    let n = nums.length;
    let ans = new Array(n).fill(1); // Initialize with ones
    let left = 1;
    for(let i = 0; i < n; i++){
        ans[i] = left;
        left *= nums[i];
    }
    let right = 1;
    for(let i = n -1; i >= 0; i--){
        ans[i] *= right;
        right *= nums[i];
    }
    return ans;
};

These examples all follow the same two-pass algorithm, achieving O(n) time and O(1) space complexity. Remember that the output array is not considered in the space complexity calculation.