My Java O(n) time and O(1) space solution, with only one pass.


  • 0
    W
        public int thirdMax(int[] nums) {
            int firstmax = Integer.MIN_VALUE;
            int secondmax = firstmax;
            int thirdmax = secondmax;
            boolean hasMin = false;
            for(int i = 0; i < nums.length; i ++) {
                if(nums[i] > firstmax && nums[i] > secondmax && nums[i] > thirdmax) {
                    thirdmax = secondmax;
                    secondmax = firstmax;
                    firstmax = nums[i];
                }
                else if(nums[i] < firstmax && nums[i] > secondmax && nums[i] > thirdmax) {
                    thirdmax = secondmax;
                    secondmax = nums[i];
                }
                else if(nums[i] < secondmax && nums[i] > thirdmax) {
                    thirdmax = nums[i];
                }
                else if(nums[i] == Integer.MIN_VALUE) {
                    hasMin = true;
                }
            }
            if(thirdmax == Integer.MIN_VALUE && secondmax == Integer.MIN_VALUE) return firstmax;
            else if(thirdmax == Integer.MIN_VALUE && !hasMin) return firstmax;
            else return thirdmax;
            
        }
    

    Two edge cases needs to be considered. (a) If the array does not has a third maximum. (b) If the array has the third maximum and the third maximum is Integer.MIN_VALUE. Otherwise, just return third maximum.


Log in to reply
 

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