Simple Java Solution: Find product of all and then divide (O(N) time and O(1) space)


  • 0
    M

    Simple Solution.

    1. First we find out running product of all the elements in array. Keep track of zeros you see. If you see more than one zero, all the elements are going to be zero so we can just break out from here.
    2. To compute each element, just divide it with the value originally seen at that place.
      Special Case: If we saw exactly one zero in past, only that location will hold the running sum we computed before, everything else will be zero.

    The solution can be made concise but it is kept here like this to elaborate the idea. Also the original nums array is being modified. If that causes ill effect as being input, we can just create new result array.

    public class Solution {
        public int[] productExceptSelf(int[] nums) {
            if(nums == null){
                return null;    
            }
            
            int allMul = 1; boolean oneZero = false; boolean twoZero = false;
            for(int num: nums){
                if(num == 0){
                    if(oneZero == false){
                        oneZero = true;
                    }else{
                        twoZero = true;
                        break;
                    }
                }else{
                     allMul *= num;
                }
            }
            
            // Two zero or more seen 
            if(twoZero){
                for(int i=0 ; i < nums.length; i++){
                   nums[i] = 0;
                }
                return nums;
            }else if(oneZero){
                // Exactly one zero seen
                for(int i=0 ; i < nums.length; i++){
                    if(nums[i] == 0){
                        nums[i] = allMul;
                    }else{
                        nums[i] = 0;
                    }
                }
            }else{
                for(int i=0 ; i < nums.length; i++){
                    nums[i] = allMul/nums[i];
                }
            }
            
            return nums;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.