package com.fishercoder.solutions;

/**
 * 414. 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.
 */
public class _414 {

    public static int thirdMax(int[] nums) {

        if (nums == null || nums.length == 0) return 0;
        if (nums.length < 3) {
           int max = 0;
           for (int i : nums) {
               max = Math.max(i, max);
           }
           return max;
        }
        
        long first = Long.MIN_VALUE, second = Long.MIN_VALUE, third = Long.MIN_VALUE;
        
        for (int i = 0; i < nums.length; i++){
            if (nums[i] > first) {
                long tmpFirst = first;
                first = nums[i];
                
                long tmpSecond = second;
                second = tmpFirst;
                
                third = tmpSecond;
            } else if (nums[i] == first) continue;
            else if (nums[i] > second) {
                long tmpSecond = second;
                second = nums[i];
                
                third = tmpSecond;
            } else if (nums[i] == second) continue; 
            else if (nums[i] > third) {
                third = nums[i];
            }
        }
        
        if (third == Long.MIN_VALUE){
           return (int) first;
        }
        
        return (int) third;
    
    }
    
    public static void main(String...strings){
//        int[] nums = new int[]{1,2};
//        int[] nums = new int[]{2,2,3,1};
//        int[] nums = new int[]{1,1,2};//should be 2
        int[] nums = new int[]{1,2,-2147483648};//should be -2147483648
//        int[] nums = new int[]{3,2,1};
//        System.out.println(thirdMax(nums));
        System.out.println(thirdMax(nums));
    }

}

@@ -687,23 +687,16 @@
  public 
-static 
 int thir
@@ -714,25 +714,24 @@
 nums) %7B%0A
-%0A
         
 if (nums
@@ -726,255 +726,17 @@
     
-if (nums == null %7C%7C nums.length == 0) return 0;%0A        if (nums.length %3C 3) %7B%0A           int max = 0;%0A           for (int i : nums) %7B%0A               max = Math.max(i, max);%0A           %7D%0A           return max;%0A        %7D%0A        %0A        long first
+long max1
  = L
@@ -750,22 +750,20 @@
 _VALUE, 
-second
+max2
  = Long.
@@ -773,21 +773,20 @@
 _VALUE, 
-third
+max3
  = Long.
@@ -796,25 +796,16 @@
 _VALUE;%0A
-        %0A
         
@@ -819,108 +819,54 @@
 t i 
-= 0; i %3C nums.length; i++)%7B%0A            if (nums%5Bi%5D %3E first) %7B%0A                long tmpFirst = first
+: nums) %7B%0A            max1 = Math.max(max1, i)
 ;%0A  
@@ -863,32 +863,34 @@
 x1, i);%0A        
+%7D%0A
         first = 
@@ -886,260 +886,102 @@
    f
-irst = nums%5Bi%5D;%0A                %0A                long tmpSecond = second;%0A                second = tmpFirst;%0A                %0A                third = tmpSecond;%0A            %7D else if (nums%5Bi%5D == first) continue;%0A            else if (nums%5Bi%5D %3E second) %7B
+or (int i : nums) %7B%0A            if (i == max1) continue;%0A            max2 = Math.max(max2, i);
 %0A   
@@ -985,24 +985,26 @@
         
+%7D%0A
         
 long tmp
@@ -999,159 +999,67 @@
     
-long tmpSecond = second;%0A                second = nums%5Bi%5D;%0A                %0A                third = tmpSecond;%0A            %7D else if (nums%5Bi%5D == second
+for (int i : nums) %7B%0A            if (i == max1 %7C%7C i == max2
 ) co
@@ -1065,17 +1065,16 @@
 ontinue;
- 
 %0A       
@@ -1082,169 +1082,32 @@
     
-else if (nums%5Bi%5D %3E third) %7B%0A                third = nums%5Bi%5D;%0A            %7D%0A        %7D%0A        %0A        if (third == Long.MIN_VALUE)%7B%0A           return (int) first
+max3 = Math.max(max3, i)
 ;%0A  
@@ -1118,17 +1118,8 @@
   %7D%0A
-        %0A
     
@@ -1139,414 +1139,45 @@
 nt) 
-third;%0A    %0A    %7D%0A    %0A    public static void main(String...strings)%7B%0A//        int%5B%5D nums = new int%5B%5D%7B1,2%7D;%0A//        int%5B%5D nums = new int%5B%5D%7B2,2,3,1%7D;%0A//        int%5B%5D nums = new int%5B%5D%7B1,1,2%7D;//should be 2%0A        int%5B%5D nums = new int%5B%5D%7B1,2,-2147483648%7D;//should be -2147483648%0A//        int%5B%5D nums = new int%5B%5D%7B3,2,1%7D;%0A//        System.out.println(thirdMax(nums));%0A        System.out.println(thirdMax(nums)
+(max3 == Long.MIN_VALUE ? max1 : max3
 );%0A 

edit 414