How do you solve Third Maximum Number on LeetCode?

Third Maximum Number (LeetCode #414) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Distinct values matter, not duplicates.

What is the time complexity of Third Maximum Number?

The optimal solution for Third Maximum Number runs in O(n) time and uses O(1) space. This approach runs in O(n) time since we only traverse the list once and use a fixed amount of space for the set.

What is the brute force solution for Third Maximum Number?

The brute force approach for Third Maximum Number is Brute Force, with O(n log n) time complexity and O(n) space complexity. We can find the third maximum number by sorting the array and then picking the distinct values. This is straightforward but not efficient. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Third Maximum Number?

Third Maximum Number uses the following concepts: Array, Sorting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Third Maximum Number?

Always consider edge cases, like arrays with fewer than three distinct numbers. Explain your thought process clearly, especially when transitioning from brute force to optimal solutions.

What are common mistakes when solving Third Maximum Number?

Not handling duplicates correctly. Forgetting to check the size of distinct values.

#414

Third Maximum Number

Easy

ArraySortingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n log n)	O(n)
Space	O(n)	O(1)

💡

Intuition

Time O(n)Space O(1)

We can find the third maximum number in a single pass using a set to track distinct values, which is more efficient.

⚙️

Algorithm

4 steps

1Step 1: Initialize a set to store distinct maximum values.
2Step 2: Iterate through the array, adding each number to the set.
3Step 3: If the size of the set exceeds 3, remove the smallest element.
4Step 4: After processing, if the set has less than 3 elements, return the maximum; otherwise, return the smallest in the set.

solution.py7 lines

1def thirdMax(nums):
2    distinct = set()
3    for num in nums:
4        distinct.add(num)
5        if len(distinct) > 3:
6            distinct.remove(min(distinct))
7    return max(distinct) if len(distinct) < 3 else min(distinct)

ℹ

Complexity note: This approach runs in O(n) time since we only traverse the list once and use a fixed amount of space for the set.

1Distinct values matter, not duplicates.
2Using a set helps manage unique values efficiently.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.