Product of Array Except Self LeetCode Solution

Problem Statement

Product of Array Except Self LeetCode Solution – 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 operation.

Example

Test Case 1:

Input:

nums = [1, 2, 3, 4]

Output:

[24, 12, 8, 6]

Test Case 2:

Input:

nums = [-1, 1, 0, -3, 3]

Output:

[0, 0, 9, 0, 0]

Explanation

The output array is the product of each element in the array except the number present at that index.

Approach:

Before we look at the constraints, let’s just think of solving the problem as is.

At first glance, it becomes evident that we could easily solve this problem in one of two ways:

1. Calculate the product of every item in the array nums. Then create a result array of the same length as nums, such that for each item in the result result[i] = product / nums[i]. This is super simple and runs in O(n).
2. Create a result array of the same size as nums. We can calculate the results array by:

   <span class="hljs-keyword">for</span> (int i = <span class="hljs-number">0</span>; i < nums.length; i++) {
   		results[i] = <span class="hljs-number">1</span>;
   		<span class="hljs-keyword">for</span> (int j = <span class="hljs-number">0</span>; j < nums.length; j++) {
   			<span class="hljs-keyword">if</span> (i != j) {
   				result[i] *= nums[j];
   			}
   		}
   }

   Now, in this second attempt, what are we actually doing? For each item in the nums array, we manage to get the product of everything in nums but that item itself. How would we explain this a bit more mathematically? Let’s try to define how we calculate results[i]:

   <span class="hljs-function">For all i in the middle of <span class="hljs-title">nums</span> <span class="hljs-params">(i.e., not at either end)</span>:
       results[i] </span>= nums[<span class="hljs-number">0</span>] * ...... * nums[i-<span class="hljs-number">1</span>] * nums[i + <span class="hljs-number">1</span>] * ...... * nums[nums.length - <span class="hljs-number">1</span>]
   
   For i = <span class="hljs-number">0</span>:
       results[i] = nums[i + <span class="hljs-number">1</span>] * ...... * nums[nums.length - <span class="hljs-number">1</span>]
   		
   For i = nums.length - <span class="hljs-number">1</span>:
       results[i] = nums[<span class="hljs-number">0</span>] * ...... * nums[i-<span class="hljs-number">1</span>]

   Hopefully, this spells it out a bit better. Essentially, to get results[i], for any i, we calculate the product everything to the left and to the right of nums[i]. Keep this in mind for later!

Insight

We know the constraints, and we need to come up with a solution!

Left and Right Products

Let’s say we have an array of integers: [1, 2, 3, 4, 5, 6, 7, 8]. Let’s calculate the product of all items except for the 4 (index = 3)

1 * 2 * 3 * 5 * 6 * 7 * 8

is how we would do that. This product is the product of everything to the left and to the right of 4. This is equivalent to doing:

(1 * 2 * 3) * (5 * 6 * 7 * 8)

This is the product of the left product (the product of everything on the left) and the right product (the product of everything on the right)
Now, for any i-th item in nums, we should be able to calculate the product of everything but itself, by multiplying its left and right product!

Finding the Left Products (and Right Products) can be done in O(n)!

Let’s try to calculate a left product array, such that for left[i] = the product of everything to the left of nums[i], using this example ([1,2,3,4]).

left[0] = 1 (There is nothing to the left of nums[0], so we set it to 1)
left[1] = 1 (1 is to the left of nums[0], so we set it to 1)
left[2] = 1 * 2
left[3] = 1 * 2 * 3

Look for the pattern in those products (There’s a pattern here!)
left[1] = 1 = left[0] * 1 = left[0] * nums[0]
left[2] = 1 * 2 = left[1] * 2 = left[1] * nums[1]
left[3] = 1 * 2 * 3 = left[2] * 3 = left[2] * nums[2]

The pattern: left[i] = left[i-1] * nums[i-1] !!!

We can show a similar situation for the right product array-> right[i] = right[i+1] * nums[i+1]

right[3] = 1 (There is nothing to the left of nums[3], so we set it to 1)
right[2] = 4 (4 is to the right of nums[2])
right[1] = 4 * 3
right[0] = 4 * 3 * 2

Look for the pattern in those products (There’s a pattern here!)
right[2] = 4 = right[3] * 4 = right[3] * nums[3]
right[1] = 4 * 3 = right[2] * 3 = right[2] * nums[2]
right[0] = 4 * 3 * 2 = right[1] * 2 = right[1] * nums[1]

Solution

Now that we know how to calculate the left product array and right product array, we can simply say that results[i] = left[i] * right[i]!!

Code for Product of Array Except Self

Java Program

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] left = new int[nums.length];
        
        int[] right = new int[nums.length];
        
        left[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            left[i] = left[i-1] * nums[i-1];
        }
        
        right[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            right[i] = right[i+1] * nums[i+1];
        }
        
        int[] product = new int[nums.length];
        for (int i = 0; i < product.length; i++) {
            product[i] = left[i] * right[i];
        }
        
        return product;
    }
}

C++ Program

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n= nums.size();      
        vector<int> res(n);
        
        res[0] = nums[0];
        for(int i=1;i<n;i++){
            res[i] = res[i-1] * nums[i];
        }
      
        res[n-1] = res[n-2];
        int r=1;
        for(int i=n-1;i>0;i--){
            res[i] = res[i-1] * r;
            r *= nums[i];
        }
        res[0] = r;
       
        return res;
    }
};

Complexity Analysis for Product of Array Except Self LeetCode Solution

Time Complexity: O(n)

Space Complexity: O(n)