Problem

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

Examples

Example 1:

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

Example 2:

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

Constraints

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

Follow up

Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Can you solve it without using division operator?

Solution

Method 1 - Brute force

  1. Run 2 nested loops
  2. Inner loop calculates the product, and outer loop sets the calculated product to answer index

Code

Java
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int ans[] = new int[n];
        
        for(int i = 0; i < n; i++) {
            int prod = 1;
            for(int j = 0; j < n; j++) {
                if(i == j) {
	                continue;
	            }
                prod *= nums[j];
            }
            ans[i] = prod;
        }
        
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(1)

Method 2 - Using Division

We can calculate product of all elements. Now, for each element, we can just divide the element and store it in new array.

Code

Java
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int ans[] = new int[n];
        int prod = 1;
        for(int i : nums) {
            prod *= i;
        }
        
        for(int i = 0; i < n; i++) {
            ans[i] = prod / nums[i];
        }
        return ans;
    }
}
Javascript

const productExceptSelf = (list) => {
   let prod = 1;
   for(let i=0; i< list.length; i++) {
   // Product of every element in the input array
       prod *= list[i];

   }

   for(let i=0; i< list.length; i++) {
   // Divide by current index and push
       list[i] = prod / list[i];

   }

   return list;
}

Now lets work on follow up.

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 3 - Using Prefix and Suffix product

Algorithm

  1. Create a temporary array prefix[] such that prefix[i] contains product of all elements on left of nums[i] excluding nums[i].
  2. Create another temporary array suffix[] such that suffix[i] contains product of all elements on on right of nums[i] excluding nums[i].
  3. To get ans[], multiply prefix[] and suffix[].

Dry Run

So, for eg. consider the array, and prefix and suffix:

nums = [1,2,3,4]
prefix = [1,1, 2, 6]
suffix = [24,12,4,1]

Code

Java

public int[] productExceptSelf(int[] nums) {
	int[] prefix = new int[nums.length];
	int[] suffix = new int[nums.length];

	prefix[0] = 1;
	suffix[nums.length - 1] = 1;

	//scan from left to right
	for (int i = 1; i<nums.length - 1; i++) {
		prefix[i] = nums[i - 1] * prefix[i - 1];
	}

	//scan from right to left
	for (int i = nums.length - 2; i > 0; i--) {
		suffix[i] = suffix[i + 1] * nums[i + 1];
	}

	int[] ans = new int[nums.length];
	//multiply
	for (int i = 0; i<nums.length; i++) {
		ans[i] = prefix[i] * suffix[i];
	}

	return ans;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 4 - Space Optimized Method 3 🏆

We can actually use answer array as prefix array first, and multiply by the suffices.

Code

Java
public int[] productExceptSelf(int[] nums) {
	int[] ans = new int[nums.length];

	int prefix = 1;
	for (int i = 0; i<nums.length; i++) {
		ans[i] = prefix;
		prefix *= nums[i];
	}

	int suffix = 1;
	for (int i = nums.length - 1; i >= 0; i--) {
		ans[i] *= suffix;
		suffix *= nums[i];
	}

	return ans;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)