Java: O(n) time and O(1) space with explanation


  • 0
    E

    The optimal algorithm in this case must be O(n), since we know that we must visit each integer at least once in order to determine the 3rd maximum number.

    We accomplish this by keeping track of the top 3 numbers that we have come across. In addition, we must check to make sure that the encountered number is not already being stored in our top 3 values. The directions do not implicitly state this, but the maximum numbers must be unique,

    When a number is bigger than one of our stored maximums, we must then shift all of our stored maximum numbers down.

    public class Solution {
        public int thirdMax(int[] nums) {
            if (nums.length < 3)
                return nums[nums.length - 1];
            
            int max1 = Integer.MIN_VALUE;
            int max2 = Integer.MIN_VALUE;
            int max3 = Integer.MIN_VALUE;
            
            for (int i = 0; i < nums.length; i++) {
                int current = nums[i];
                
                if (current > max1) {
                    max3 = max2;
                    max2 = max1;
                    max1 = current;
                } else if (current != max1 && current > max2) {
                    max3 = max2;
                    max2 = current;
                } else if (current != max1 && current != max2 && current > max3) {
                    max3 = current;
                }
            }
            
            return max3;
        }
    }
    

Log in to reply
 

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