LeetCode 414: Third Maximum Number Solution in Python – A Step-by-Step Guide

What Is LeetCode 414: Third Maximum Number?

In LeetCode 414: Third Maximum Number, you’re given an integer array nums (e.g., [3, 2, 1]), and you need to return the third distinct maximum number. If there aren’t three distinct numbers, return the maximum instead. For example, in [3, 2, 1], the third max is 1 (6, 5, 4 → 3, 2, 1), but in [1, 2], with only two distinct numbers, you return 2 (the max). Duplicates count as one value, so [2, 2, 3, 1] is just 3, 2, 1.

Problem Statement

• Input: An integer array nums.
• Output: An integer—the third distinct maximum, or the maximum if fewer than three distinct numbers.
• Rules:
• Consider only distinct values.
• Return max if less than three distinct numbers.

Constraints

• 1 <= nums.length <= 10⁴.
• -2³¹ <= nums[i] <= 2³¹ - 1.

Examples

• Input: nums = [3,2,1]
• Output: 1 (third max: 3, 2, 1).
• Input: nums = [1,2]
• Output: 2 (less than 3, return max).
• Input: nums = [2,2,3,1]
• Output: 1 (distinct: 3, 2, 1).

Understanding the Problem: Finding the Third Biggest

To solve LeetCode 414: Third Maximum Number in Python, we need to identify the third largest distinct number in nums, or the largest if there aren’t three unique values. A naive idea might be to sort and pick the third—but that could waste time with big arrays! Instead, we’ll use:

• Best Solution (Three-Variable Tracking): O(n) time, O(1) space—tracks top three in one pass.
• Alternative Solution (Sorting): O(n log n) time, O(n) space—sorts and selects.

Let’s dive into the three-variable solution with a clear, step-by-step explanation.

Best Solution: Three-Variable Tracking

Why This Is the Best Solution

The three-variable tracking method is the top pick because it’s fast—O(n) time, O(1) space—and elegantly avoids sorting or extra storage. It uses three variables to keep the first, second, and third maximums, updating them as it scans the array, handling duplicates smartly. It’s like juggling three balls, swapping them out as bigger ones roll in!

How It Works

Think of the array as a stream of numbers you’re ranking:

• Step 1: Set Up Three Buckets:
• first: Biggest number seen.
• second: Second biggest.
• third: Third biggest.
• Start with negative infinity (or None) to handle initialization.
• Step 2: Scan and Update:
• For each number:
• If bigger than first, shift everything down (first → second, second → third).
• If between first and second, shift second down.
• If between second and third, update third.
• Skip if equal to any (distinct rule).
• Step 3: Decide the Answer:
• If third is valid (not infinity), return it.
• Else, return first (fewer than three distinct).
• Step 4: Why This Works:
• One pass keeps it O(n), no extra space beyond three variables.
• Distinctness check ensures duplicates don’t mess up the ranks.
• It’s like keeping a leaderboard with just three slots!

Step-by-Step Example

Example: nums = [3,2,1]

• Start: first = -inf, second = -inf, third = -inf.
• 3: > first, first = 3, second = -inf, third = -inf.
• 2: < 3, > second, first = 3, second = 2, third = -inf.
• 1: < 2, > third, first = 3, second = 2, third = 1.
• Result: third = 1, return 1.

Example: nums = [1,2]

• 1: first = 1, second = -inf, third = -inf.
• 2: > 1, first = 2, second = 1, third = -inf.
• End: third = -inf, return first = 2.

Example: nums = [2,2,3,1]

• 2: first = 2, second = -inf, third = -inf.
• 2: Equal, skip.
• 3: > 2, first = 3, second = 2, third = -inf.
• 1: < 2, > third, first = 3, second = 2, third = 1.
• Result: third = 1, return 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def thirdMax(self, nums: List[int]) -> int:
        # Step 1: Initialize three variables
        first = float('-inf')  # Max
        second = float('-inf') # Second max
        third = float('-inf')  # Third max

        # Step 2: Scan array
        for num in nums:
            # Skip if duplicate of current maxes
            if num == first or num == second or num == third:
                continue

            # Update ranks
            if num > first:
                third = second
                second = first
                first = num
            elif num > second:
                third = second
                second = num
            elif num > third:
                third = num

        # Step 3: Return result
        if third == float('-inf'):
            return first  # Less than 3 distinct, return max
        return third

• Line 4-6: Set up:
• Use -inf to start (handles all integers up to 2³¹ - 1).
• Line 9-19: Loop through nums:
• Line 10-11: Skip duplicates (e.g., second 2 in [2,2,3]).
• Line 13-19: Update ranks:
• Line 13-16: If > first, shift all down (e.g., 3 > 2).
• Line 17-18: If > second, shift second to third (e.g., 2 > 1).
• Line 19: If > third, update third (e.g., 1 > -inf).
• Line 22-24: Return:
• If third is -inf, fewer than 3 distinct, return first.
• Else, return third.
• Time Complexity: O(n)—one pass through array.
• Space Complexity: O(1)—three variables.

This is like keeping a podium for the top three in one sweep!

Alternative Solution: Sorting Approach

Why an Alternative Approach?

The sorting approach sorts the array and picks the third distinct number from the end, falling back to the max if needed. It’s O(n log n) time and O(n) space—simpler to understand but less efficient. It’s like lining up everyone and counting back three, skipping repeats!

How It Works

Picture it as a sorted lineup:

• Step 1: Sort array in descending order.
• Step 2: Remove duplicates (or track distinct).
• Step 3: Pick third element, or first if less than three.

Step-by-Step Example

Example: nums = [3,2,1]

• Sort: [3,2,1].
• Distinct: [3,2,1].
• Third: 1.
• Result: 1.

Example: nums = [2,2,3,1]

• Sort: [3,2,2,1].
• Distinct: [3,2,1].
• Third: 1.
• Result: 1.

Code for Sorting Approach

Copy codeclass Solution:
    def thirdMax(self, nums: List[int]) -> int:
        # Step 1: Remove duplicates and sort
        unique_nums = sorted(set(nums), reverse=True)

        # Step 2: Check length and return
        if len(unique_nums) < 3:
            return unique_nums[0]  # Max if less than 3
        return unique_nums[2]      # Third max

• Time Complexity: O(n log n)—sorting dominates.
• Space Complexity: O(n)—set and sorted list.

It’s a sorted podium picker!

Comparing the Two Solutions

• Three-Variable Tracking (Best):
• Pros: O(n), O(1), fast and lean.
• Cons: Logic to follow.
• Sorting (Alternative):
• Pros: O(n log n), O(n), simple.
• Cons: Slower, more space.

Tracking wins for efficiency.

Additional Examples and Edge Cases

• [1]: 1 (max).
• [2,1]: 2 (max).
• [1,1,1]: 1 (max).

Tracking handles all.

Complexity Breakdown

• Tracking: Time O(n), Space O(1).
• Sorting: Time O(n log n), Space O(n).

Tracking’s the champ.

Key Takeaways

• Tracking: Juggle three!
• Sorting: Line it up!
• Maxes: Distinctness counts.
• Python Tip: Loops are key—see [Python Basics](/python/basics).

Final Thoughts: Nab That Third

LeetCode 414: Third Maximum Number in Python is a number-ranking quest. Three-variable tracking zips to the answer, while sorting lines it up. Want more array fun? Try LeetCode 215: Kth Largest Element or LeetCode 628: Maximum Product of Three Numbers. Ready to rank? Head to Solve LeetCode 414 on LeetCode and find that third max today!