Third Maximum Number - Leetcode Solution

Problem statement:

Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

Example:

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

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

Solution:

To solve this problem we can use a set to keep track of distinct numbers in the array. After that we can find the third maximum number by sorting the distinct numbers and returning the third from the end.

Here is the step by step solution:

1. Create a set s to keep track of distinct numbers in the array.

2. Loop through the input array nums and add each element to the set s.

3. Convert the set s to a list l.

4. Sort the list l in descending order.

5. If the length of the list l is less than 3, return the maximum element in the list.

6. Otherwise, return the third element in the list.

Here is the Python code:

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        
        # Create a set to keep track of distinct numbers
        s = set()
        
        # Loop through the input array and add each element to the set
        for num in nums:
            s.add(num)
        
        # Convert the set to a list and sort it in descending order
        l = sorted(list(s), reverse=True)
        
        # If the length of the list is less than 3, return the maximum element
        if len(l) < 3:
            return max(l)
        
        # Otherwise, return the third element
        return l[2]

Time Complexity: O(nlogn), where n is the number of elements in the input array nums. This is because we need to sort the distinct elements in the set.

Space Complexity: O(n), where n is the number of elements in the input array nums. This is because we need to store distinct elements in the set.

1