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:

1
2

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

Example 2:

1
2

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

Constraints

  • 2 <= nums.length <= 10^5
  • -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

Video explanation

Here is the video explaining below methods in detail. Please check it out:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        ans = [0] * n  # Create a result array filled with 0s
        
        # Iterate through the array
        for i in range(n):
            prod = 1  # Initialise product for current index
            
            for j in range(n):
                if i != j:  # Compute product of all numbers except at the current index
                    prod *= nums[j]
            
            ans[i] = prod  # Store the product in the result array
        
        return ans  # Return the computed array

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.

Using a division-based approach is a straightforward way to solve the problem. However, there are a few important considerations, such as handling edge cases like arrays containing zero or avoiding integer division errors.

Here are the edge case for this approach:

  • If there’s one zero in the array, the product will only be non-zero for the position of the zero.
  • If there are multiple zeros, all elements in the result array will be zeros.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n]; // Standard array declaration style
        int totalProduct = 1; // Variable to store the product of all elements
        int zeroCount = 0; // To count zeros in the array
		int zeroIdx = -1;
        // Step 1: Calculate total product and count zeros
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                zeroCount++;
                zeroIdx = i;
                // If more than 1 zero, all products will be 0
                if (zeroCount > 1) {
	                return ans;
                }; 
            } else {
                totalProduct *= num;
            }
        }
		if (zeroCount == 1) {
            ans[zeroIdx] = totalProduct;
            return ans;
        }
        
        // Step 2: Populate the result array
        for (int i = 0; i < n; i++) {
            ans[i] = totalProduct / nums[i]; // Regular case with no zeros
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        ans = [0] * n  # Initialise the result array with zeros
        totalProduct = 1  # Variable to store the product of non-zero elements
        zeroCount = 0  # To count the number of zeros in the array

        # Step 1: Calculate total product and count zeros
        for i in range(n):
            if nums[i] == 0:
                zeroCount += 1
                zeroIdx = i
                if zeroCount > 1:  # If more than 1 zero, all products will be 0
                    return ans
            else:
                totalProduct *= nums[i]
        if zeroCount == 1:
            ans[zeroIdx] = totalProduct
            return ans

        # Step 2: Populate the result array
        for i in range(n):
            ans[i] = totalProduct // nums[i]  # Regular case with no zeros

        return ans

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:

1
2
3

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

        // Initialise first prefix and last suffix
        prefix[0] = 1;
        suffix[n - 1] = 1;

        // Scan from left to right to fill prefix array
        for (int i = 1; i < n; i++) {
            prefix[i] = nums[i - 1] * prefix[i - 1];
        }

        // Scan from right to left to fill suffix array
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = nums[i + 1] * suffix[i + 1];
        }

        // Multiply prefix and suffix arrays to get the result
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = prefix[i] * suffix[i];
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        prefix = [1] * n  # Initialise prefix array
        suffix = [1] * n  # Initialise suffix array

        # Fill prefix array
        for i in range(1, n):
            prefix[i] = nums[i - 1] * prefix[i - 1]

        # Fill suffix array
        for i in range(n - 2, -1, -1):
            suffix[i] = nums[i + 1] * suffix[i + 1]

        # Multiply prefix and suffix to get the result
        ans = [0] * n
        for i in range(n):
            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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
	public int[] productExceptSelf(int[] nums) {
	    int n = nums.length;
	    int[] ans = new int[n];
	
	    // Calculate prefix product and store in ans
	    int prefix = 1;
	    for (int i = 0; i < n; i++) {
	        ans[i] = prefix;  // Ans holds prefix product for index i
	        prefix *= nums[i];
	    }
	
	    // Calculate suffix product and update ans
	    int suffix = 1;
	    for (int i = n - 1; i >= 0; i--) {
	        ans[i] *= suffix;  // Combine suffix product with prefix already in ans
	        suffix *= nums[i];
	    }
	
	    return ans;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        ans = [1] * n  # Initialise result array with 1s

        # Calculate prefix product and store in ans
        prefix = 1
        for i in range(n):
            ans[i] = prefix  # Store prefix product at index i
            prefix *= nums[i]

        # Calculate suffix product and update ans
        suffix = 1
        for i in range(n - 1, -1, -1):
            ans[i] *= suffix  # Multiply suffix with the value in ans
            suffix *= nums[i]

        return ans

Complexity

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