## Wednesday, May 10, 2017

### Third Maximum Number

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.```

### Solution

• We need to have 3 variables max1, max2 and max3
• In the initial 3 iteration all variables would be assigned null values based on the index
max1=n , max2=n max3=n
• We need to check if n is greater than max1 . If yes then we need to swap the values
• Next we need to check if  n is greater than max2
• Finally we would get the third max number
```package Algorithms.Arrays;

public class ThirdMaxNumber {

public static int get(int [] arr)
{
Integer max1=null;
Integer max2=null;
Integer max3=null;
//loop through the array
for(Integer n : arr)
{

if(n.equals(max1) || n.equals(max2) || n.equals(max3))
{
continue;
}
else if(max1==null || n> max1)
{
max3=max2;
max2=max1;
max1=n;
}
else if(max2==null || n> max2)
{
max3=max2;
max2=n;
}
else if(max3==null || n> max3)
{
max3=n;
}

}
return max3==null?max1 :max3;
}
}
```