C++ Solution in O(n) time, O(1) space and without sort function


  • 0
    A

    '''class Solution {
    public:
    int maximumProduct(vector<int>& nums)
    {
    int arrSize = nums.size();

        if(arrSize == 1)
            return nums[0];
        
        else if(arrSize == 2)
            return nums[0]*nums[1];
        
        else if(arrSize == 3)
            return nums[0]*nums[1]*nums[2];
        
        int first = nums[0], second, third, min1 = nums[0], min2;
        
        bool firstVal = true;
        bool secondVal = false;
        bool thirdVal = false;
        bool min1Val = true;
        bool min2Val = false;
        
        for(int i = 1; i < arrSize; i++)
        {
            if(nums[i] > first)
            {
                if(secondVal)
                {
                    thirdVal = true;
                    third = second;
                }
                
                else
                    secondVal = true;
                
                second = first;
                first = nums[i];
            }
            
            else if(!secondVal || nums[i] > second)
            {
                if(secondVal)
                {
                    thirdVal = true;
                    third = second;
                }
                
                else
                    secondVal = true;
                
                second = nums[i];
            }
            
            else if(!thirdVal || nums[i] > third)
            {
                third = nums[i];
                thirdVal = true;
            }
            
            if(nums[i] < min1)
            {
                if(min2Val)
                    min2Val = true;
                
                min2 = min1;
                min1 = nums[i];
            }
            
            else if(!min2Val || nums[i] < min2)
            {
                if(!min2Val)
                    min2Val = true;
                
                min2 = nums[i];
            }
        }
        
        return max((first*second*third), (first*min1*min2));
    }
    

    };'''


Log in to reply
 

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