Given a non-empty integer array, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number in the array.

Example 1:

Input: [3, 2, 1]
Output: 1
Explanation: The third distinct maximum is 1.

Example 2:

Input: [1, 2]
Output: 2
Explanation: The third distinct maximum does not exist, so the maximum (2) is returned instead.

Example 3:

Input: [2, 2, 3, 1]
Output: 1
Explanation: The third distinct maximum refers to the third unique largest number. The distinct values here are 3, 2, 1, so the third maximum is 1.

Constraints:

• 1 <= nums.length <= 10000
• -2^31 <= nums[i] <= 2^31 - 1

Follow-up: Can you solve this in O(n) time complexity?

Approach 1: Linear Scan with Three Tracking Variables

This approach runs in O(n) time by maintaining three variables to track the top three distinct maximum values. We use 64-bit integers to avoid overflow issues with the minimum 32-bit integer input value.

int thirdMax(int* nums, int numsSize) {
    if (numsSize == 1) return nums[0];
    if (numsSize == 2) return nums[0] > nums[1] ? nums[0] : nums[1];

    long long first_max = LLONG_MIN;
    long long second_max = LLONG_MIN;
    long long third_max = LLONG_MIN;

    for (int i = 0; i < numsSize; i++) {
        int current = nums[i];
        // Skip duplicate values to ensure we track distinct maxima
        if (current == first_max || current == second_max || current == third_max) {
            continue;
        }

        if (current > first_max) {
            third_max = second_max;
            second_max = first_max;
            first_max = current;
        } else if (current > second_max) {
            third_max = second_max;
            second_max = current;
        } else if (current > third_max) {
            third_max = current;
        }
    }

    return third_max == LLONG_MIN ? (int)first_max : (int)third_max;
}

Approach 2: Sorting and Count Distinct Elements

This approach sorts the array in decsending order, then tarverses the sorted array to count distinct elements until we find the third unique maximum. This has O(n log n) time complexity due to sorting, and is simpler to implement for beginners.

int thirdMax(int* nums, int numsSize) {
    // Sort array in descending order using bubble sort
    for (int i = 0; i < numsSize - 1; i++) {
        for (int j = 0; j < numsSize - 1 - i; j++) {
            if (nums[j] < nums[j + 1]) {
                int temp = nums[j];
                nums[j] = nums[j + 1];
                nums[j + 1] = temp;
            }
        }
    }

    int distinct_count = 1;
    int current_max = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] != current_max) {
            distinct_count++;
            current_max = nums[i];
            if (distinct_count == 3) {
                return current_max;
            }
        }
    }

    return nums[0];
}