414. Third Maximum Number

• python3

Problem

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 1:

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

Example 2:

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

Example 3:

Input: nums = [2,2,3,1]
Output: 1
Explanation:
The first distinct maximum is 3.
The second distinct maximum is 2 (both 2's are counted together since they have the same value).
The third distinct maximum is 1.

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

Pseudocode

My Solution

1. Use a set to check if the number of elements in the set is smaller than 3. If it is, return the maximum value of the list.
2. Remove the maximum value from the set twice.
3. Return the maximum value of the set.

Another Solution

1. Use a set to check if the number of elements in the set is smaller than 3. If it is, return the maximum value of the list.
2. Compare the three elements sequentially with the current element of the list.
3. Return the third maximum element.

Code

My solution

class Solution:
    def thirdMax(self, nums: List[int]) -> int:

        nums = set(nums)
        if len(nums) < 3:
            return max(nums)
        else:
            nums.remove(max(nums))
            nums.remove(max(nums))
            return max(nums)

Another Solution

class Solution:
    def thirdMax(self, nums: List[int]) -> int:

        if len(set(nums)) < 3:
            return max(nums)
        
        first, second, third = float('-inf'), float('-inf'), float('-inf')

        for num in nums:
            if num > first:
                first, second, third = num, first, second
            elif first > num > second:
                second, third = num, second
            elif second > num > third:
                third = num
        
        return third

Result

My Solution

• Time Complexity : set(nums) -> O(n), max(nums) -> O(n) => O(n)
• Space Complexity : O(n) to make a set.

Another Solution

• Time Complexity : set(nums) -> O(n), for loop -> O(n)
• Space Complexity : O(n) to make a set.

-> if I don't use a set it's Space Complexity will be O(1).

Review

• I spent so much time trying to solve this with a stack. I need to remember to always think simply.