238. Product of Array Except Self

Source : Click here

Problem Statement:

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 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 <= 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 notcount as extra space for space complexity analysis.)

Solution:

Thought process:

1. Brute force - O(n^2)
2. Division approach
   1. Calculate the product of all the numbers.
   2. Divide nums[i] for each i to get the product of all the number except ith position.
   3. Identify the edge cases where 0 is present.
      1. Can’t divide by zero.
      2. product turns 0 if anyone number is 0.
3. Calculate prefix product (excluding the number at ith position) and suffix product (excluding the number at ith position). For ith result : prefix[i] x suffix[i].

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

4. For post and prefix product we don’t need to store in different arrays. Let’s remove the arrays one by one.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] pre = new int[n];
        // int[] post = new int[n];
 
        pre[0] = 1;
        // post[n-1] = 1;
 
        //calc pre's
        for(int i = 1; i < n; i++){
            pre[i] = pre[i - 1] * nums[i - 1];
        }
        
        int[] ans = new int[n];
        // last position of array will be just pre[n-1];
        ans[n - 1] = pre[n - 1];
        
        int curr = 1;
        for(int i = n - 2; i >= 0; i--){
	        // curr storing post's result;
            curr = curr * nums[i + 1];
            ans[i] = curr * pre[i];
        }
 
        return ans;
    }
}

5. Similarly, we don’t need pre array as well, we can keep the result of pre array in ans array itself.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        Arrays.fill(ans, 1);
		
		// Calculate pre product
        for(int i = 1; i < n; i++){
            ans[i] = ans[i - 1] * nums[i - 1];
        }
 
		// nums[1,2,3,4]
		// ans [1,1,2,6]
        int curr = 1;
        for(int i = n - 2; i >= 0; i--){
            curr = curr * nums[i + 1];
            ans[i] = curr * ans[i]; //effectively -> post * pre
        }
        // curr = 4
        // ans[2] = 4 * 2 = 8
        // ans[1] = 12 * 1 = 12
        // ans[0] = 24 * 1 = 24
        // ans[24, 12, 8, 6]
        
 
        return ans;
    }
}