Third Maximum Number

Third Maximum Number

Problem Description

Given an integer array nums, the task is to find the third distinct maximum number in the array. If the third maximum does not exist, return the maximum number.

Naive Approach

A straightforward approach would be to sort the array in descending order and then find the third distinct element. This involves sorting and then iterating through the sorted array to find distinct elements.

Algorithm

1. Remove duplicate elements from the array.
2. Sort the array in descending order.
3. If the array has at least three elements, return the third element.
4. Otherwise, return the maximum element (the first element after sorting).

Code (Python)

def third_max_naive(nums):
    nums = sorted(list(set(nums)), reverse=True)
    if len(nums) >= 3:
        return nums[2]
    elif len(nums) > 0:
        return nums[0]
    else:
        return None # or handle the empty list case as appropriate

Time Complexity

• Sorting the array takes O(n log n) time.
• Removing duplicates using set() and converting back to list takes O(n) time.
• Overall: O(n log n)

Space Complexity

• O(n) in the worst case to store the unique elements.

Optimal Approach

A more efficient approach involves iterating through the array once and keeping track of the first, second, and third maximum numbers.

Algorithm

1. Initialize max1, max2, and max3 to negative infinity (or None in Python).
2. Iterate through the array:
   • If the current number is greater than max1, update max3 = max2, max2 = max1, and max1 = num.
   • Else if the current number is greater than max2 and not equal to max1, update max3 = max2 and max2 = num.
   • Else if the current number is greater than max3 and not equal to max1 and max2, update max3 = num.
3. If max3 is still negative infinity (or None), return max1. Otherwise, return max3.

Code (Python)

import math

def third_max_optimal(nums):
    max1 = float('-inf')
    max2 = float('-inf')
    max3 = float('-inf')

    for num in nums:
        if num > max1:
            max3 = max2
            max2 = max1
            max1 = num
        elif num > max2 and num != max1:
            max3 = max2
            max2 = num
        elif num > max3 and num != max1 and num != max2:
            max3 = num

    if max3 == float('-inf'):
        return max1
    else:
        return max3

Time Complexity

• Iterating through the array takes O(n) time.

Space Complexity

• O(1) as we are only using a fixed number of variables.

Edge Cases

1. Empty Array: The problem statement specifies 1 <= nums.length <= 10^4, so we do not need to consider an empty array.
2. Array with One or Two Distinct Elements: The optimal solution handles the case where there are fewer than three distinct elements by returning the maximum element.
3. Duplicate Elements: The optimal solution correctly handles duplicate elements by ensuring that only distinct maximum numbers are tracked.
4. Negative Numbers: The optimal solution correctly handles negative numbers, including the minimum integer (-2^31), by initializing max1, max2, and max3 to negative infinity.

Summary

The optimal solution provides a more efficient way to find the third distinct maximum number in an array with O(n) time complexity and O(1) space complexity, making it preferable over the naive O(n log n) solution.