Java code without sorting


  • 0
    A

    Need to keep track of 3 max numbers & 2 min numbers from the array. Runs in O(N) & constant space.

    public int maximumProduct(int[] nums) {
            int SPLNUM = 1001;
            int min1 = SPLNUM, min2 = SPLNUM, max1 = nums[0], max2 =SPLNUM, max3 = SPLNUM;
            for(int i = 1; i < nums.length; i++) {
                int elem = nums[i];
            if(elem >= max1) {
                       if(min1 == SPLNUM) min1 = max3;
                       else if(min2 == SPLNUM) min2 = max3;
                       max3 = max2;
                       max2 = max1;
                       max1 = elem;
                } else if(elem >= max2 || max2 == SPLNUM){
                        if(min1 == SPLNUM) min1 = max3;
                        else if(min2 == SPLNUM) min2 = max3;
                        max3 = max2;
                        max2 = elem;
                } else if(elem > max3 || max3 == SPLNUM ){
                        if(min1 == SPLNUM) min1 = max3;
                        else if(min2 == SPLNUM) min2 = max3;
                        max3 = elem;
                } else if(elem <= min1 || min1 == SPLNUM) {
                        min2 = min1;
                        min1 = elem;
                }   else if(elem < min2 || min2 == SPLNUM) {
                        min2 = elem;
                } 
            }
            if(min1 ==SPLNUM) {
                min1 = max3;
                min2 = max2;
            } else if(min2 == SPLNUM) 
                min2 = max3;
            int a = max1*max2*max3, b = min1*min2*max1;
            return a > b ? a : b;
        }
    

Log in to reply
 

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