Find Third maximum Number in an array with O(N) Time Complexity
Tags: java, codenewbie, computerscience
Published: 2020-09-01 12:19:52

Here is the Question Description:-
 
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example 1:
Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.
Example 2:
Input: [1, 2]

Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3:
Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

Here is my Solution in JAVA :


    class Solution{
    public  int thirdMax(int[] nums){
        int first=nums[0],second=Integer.MIN_VALUE,third=Integer. MIN_VALUE,n=nums.length,count=0;
        if(n<3)
            {
            if(n==1)
                {
              return nums[0];  
                
            }
            else
            {
              return Math.max(nums[0],nums[1]);  
                }
        }
       for(int i=1;i<n;i++)
           {
           if(first<nums[i])
               {
               first=nums[i];
               
          }
           
       }
        for(int i=0;i<n;i++)
            {
            if(first>nums[i]&&nums[i]>second)
                {
                second=nums[i];
            }
        }
        for(int i=0;i<n;i++)
            {
            if(second>nums[i]&&nums[i]>=third)
            {
              third=nums[i]; 
                count++;
          
            }
          
            
        }
        if(third==Integer.MIN_VALUE)
           {
          
              if(count!=0)
                  {
                  return third;
              }
             
                  
            
            third=first;
                 
            
           }
        return third;
    }
    }

Here in this solution i just wrote the function of How to find thirdMax number!
Firstly i take 4 integer type variable such as first(initialize as very 1st element),second,third,n(for size of the array),count(it is basically used for one important testcase)
point to be noted that we have to find max value so here we initialize the variables as min value(in second and third).So that we can compare the initialize value with array elements.
By the way you would know after reading the Question description !
So, after initialization of variable..
1st if condition is for array length from 1 to 2 then return should be max element.
Thereafter here is 3 for loop 1st for loop is for finding Very first max no.
2nd for loop is to finding second max no.
3rd for loop is to finding third max no. in the array.
And atlast if condition is for one special case which is, if 3rd max element is not present in the array then it will return the 1st max element.
Note: Here suppose that the array element is same as Integer.MIN_VALUE , the and also is if it is third max element then return as it is!
I hope it will help you!!
and if any confusion regarding this then feel free to ask in comment.I would love to explain:)

HappyCoding❤️