Blogs Hub

by Sumit Chourasia | Nov 18, 2020 | Category :coding | Tags : algorithm array data-structure leetcode medium

Product of Array Except Self - Array - Medium - LeetCode

Product of Array Except Self - Array - Medium - LeetCode

Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Input:  [1,2,3,4]
Output: [24,12,8,6]
Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

Note: Please solve it without division and in O(n).

Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

public class Solution {
    public int[] ProductExceptSelf(int[] nums) {        
        int totalProduct = 1;
        int zero = 0;
        for(int i=0;i<nums.Length;i++){
            if(nums[i]==0){
                zero++;
            }
            else{
                totalProduct *= nums[i];
            }            
        }
        
        for(int i=0;i<nums.Length;i++){
            if(zero>1){
                nums[i]=0;
            }
            else if(zero==1){
                if(nums[i]==0){
                    nums[i]=totalProduct;
                }
                else{
                    nums[i]=0;
                }
            }
            else{
                nums[i]=totalProduct/nums[i];
            }            
        }
        
        return nums;
    }
}

Time Complexity: O(n)

Space Complexity: O(1)