Java O(n) time, O(1) space (with explanation)


  • 0
    D

    This is a simple solution that keeps track of 3 values and updates all the necessary values when a larger number is seen. In the first case, if the value is bigger than the maxValue1, the other values need to be updated first (pushing things downward).

    In addition, we need to ensure that the new value won't be the same as one of the bigger values, which causes duplicate (highest) values.

    Finally, I have a check to see whether the number of elements is less than 3. If so, return the highest value. Otherwise return the 3rd max number.

    public class Solution {
        public int thirdMax(int[] nums) {
    
            int maxValue1 = Integer.MIN_VALUE;
            int maxValue2 = Integer.MIN_VALUE;
            int maxValue3 = Integer.MIN_VALUE;
            
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > maxValue1) {
                    maxValue3 = maxValue2;
                    maxValue2 = maxValue1;
                    maxValue1 = nums[i];
                } else if (nums[i] > maxValue2 && nums[i] != maxValue1) {
                    maxValue3 = maxValue2;
                    maxValue2 = nums[i];
                } else if (nums[i] > maxValue3 && nums[i] != maxValue2 && nums[i] != maxValue1) {
                    maxValue3 = nums[i];
                }
            }
            
            return (nums.length < 3) ? maxValue1 : maxValue3;
        }
    }
    

Log in to reply
 

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