[LeetCode] Problem 414 - Third Maximum Number

Posted on | In ,

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

No.1

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

No.2

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

No.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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int thirdMax(int[] nums) {
    long[] max = new long[3];
    Arrays.fill(max, Long.MIN_VALUE);

    for (int num : nums) {
        if (num == max[0] || num == max[1] || num == max[2])
            continue;
        
        if (max[0] == Long.MIN_VALUE || num > max[0]) {
            max[2] = max[1];
            max[1] = max[0];
            max[0] = num;
        }
        else if (max[1] == Long.MIN_VALUE || num > max[1]) {
            max[2] = max[1];
            max[1] = num;
        }
        else if (max[2] == Long.MIN_VALUE || num > max[2])
            max[2] = num;
    }

    return (int) (max[2] == Long.MIN_VALUE ? max[0] : max[2]);
}