Product of Array Except Self

Problem Statement

LeetCode-238: 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.

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Approach

As mentioned in the problem statement, we cannot use the division operation. Had we been allowed to use the division operation, we could have easily solved this problem by calculating the product of all the elements of the array and then dividing it by the element at the current index to get the answer.

A key observation to solve this problem is that the product of all the elements of the array except the element at the current index is the product of all the elements to the left of the current index multiplied by the product of all the elements to the right of the current index.

Consider the following example:

nums = [1, 2, 3, 4]
left = [1, 1, 2, 6]
right = [24, 12, 4, 1]

answer = [24, 12, 8, 6] i.e. left[i] * right[i]

Implementation

Here is a Java implementation of the approach:

public int[] productExceptSelf(int[] nums) {
    int[] left = new int[nums.length];
    int[] right = new int[nums.length];
    int[] ans = new int[nums.length];
    
    // as there is nothing to the left of first element
    left[0] = 1;
    for(int i=1; i < left.length; i++){
        left[i] = left[i-1]*nums[i-1];
    }
    
    // as there is nothing to the right of last element
    right[right.length-1] = 1;
    for(int i=right.length-2; i >=0; i--){
        right[i] = right[i+1]* nums[i+1];
    }
    
    for(int i=0; i < ans.length; i++){
        ans[i] = left[i]*right[i];
    }
    
    return ans;
}

We can optimize the above approach a bit by re-using the left (or right) array to store the product of all the elements to the left of the current index and the right array to store the products instead of creating a new ans array.

Complexity Analysis

As we are iterating the input array 3 times, the overall time complexity of this approach is $O(3N) \approx O(N)$ where $N$ is the number of elements in the input array nums.

Additionally, we are using three extra arrays of size N each, so the space complexity of this approach is $O(3N) \approx O(N)$.

Follow-up

Can we solve this problem without using extra space?

In the above approach, we are using two extra arrays left and right to store the product of all the elements to the left and right of the current index. We can solve this problem without using extra space by using the output array itself to store the product of all the elements to the left of the current index and then calculating the product of all the elements to the right of the current index on the fly.

Here is a Java implementation of this approach:

public int[] productExceptSelf(int[] nums) {
    int[] result = new int[nums.length];
    
    // as there is no prefix to 0th element
    result[0] = 1;
    // this will populate result[i] with the product
    // of all the elements to the left of nums[i]
    for(int i=1; i< nums.length; i++){
        result[i] = result[i-1]* nums[i-1];
    }
    
    // as there is nothing to the right of last element
    int prefix = 1;
    // this will populate result[i] with the product
    // of all the elements to the right of nums[i]
    for(int i=nums.length-1; i>=0; i--){
        result[i] = prefix * result[i];
        prefix = prefix * nums[i];
    }
    
    return result;
    
}

Consider the example nums = [1,2,3,4]. The result array will be populated as follows:

# first loop
result = [1, 1, 2, 6]

# second loop
prefix = 1, result = [1,1,2,6]; prefix = 4
prefix = 4, result = [1,1,8,6]; prefix = 12
prefix = 12, result = [1,12,8,6]; prefix = 24
prefix = 24, result = [24,12,8,6]

This approach has a time complexity of $O(N)$ and a space complexity of $O(N)$ due to new array result.