Formatted question description: https://leetcode.ca/all/414.html

414. Third Maximum Number

Level

Easy

Description

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

Use three variables to store the three distinct maximum numbers. Also use a variable to store the count of distinct numbers in the array. Initially, the three variables for three maximum numbers are Long.MIN_VALUE, where data type long is used to avoid overflow.

Loop over the array. Use the idea of insertion sort and update the three distinct maximum numbers. If the current number is greater than at least one of the three distinct maximum numbers, then update the distinct maximum numbers that has a smaller value, and increase the counter by 1.

Finally, if the counter is greater than or equal to 3, return the third distinct maximum number. Otherwise, return the first maximum number.

class Solution {
    public int thirdMax(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        long firstMax = Long.MIN_VALUE;
        long secondMax = Long.MIN_VALUE;
        long thirdMax = Long.MIN_VALUE;
        int count = 0;
        for (int num : nums) {
            long numLong = (long) num;
            if (numLong == firstMax || numLong == secondMax || numLong == thirdMax)
                continue;
            if (numLong > firstMax) {
                thirdMax = secondMax;
                secondMax = firstMax;
                firstMax = numLong;
                count++;
            } else if (numLong > secondMax) {
                thirdMax = secondMax;
                secondMax = numLong;
                count++;
            } else if (numLong > thirdMax) {
                thirdMax = numLong;
                count++;
            }
        }
        return count >= 3 ? (int) thirdMax : (int) firstMax;
    }
}

All Problems

All Solutions