LeetCode 414 - Third Maximum Number

The problem asks us to find the third distinct maximum number in an integer array. The key word is distinct. Duplicate values should only be counted once when determining rankings. For example, in the array [2,2,3,1], the distinct values are {3,2,1}.

leetcodeeasyarraysorting

LeetCode Problem 414

Difficulty: 🟢 Easy
Topics: Array, Sorting

Solution

Problem Understanding

The problem asks us to find the third distinct maximum number in an integer array. The key word is distinct. Duplicate values should only be counted once when determining rankings.

For example, in the array [2,2,3,1], the distinct values are {3,2,1}. Even though 2 appears twice, it only counts as one distinct number. The third distinct maximum is therefore 1.

If the array contains fewer than three distinct values, we return the overall maximum number instead. For example, in [1,2], there are only two distinct numbers, so the answer is the largest value, 2.

The input is an array of integers named nums. The output is a single integer representing either:

  • the third distinct maximum value, or
  • the maximum value if fewer than three distinct values exist

The constraints tell us several important things:

  • The array length can be as large as 10^4
  • Values can range from -2^31 to 2^31 - 1
  • Negative numbers are valid inputs
  • Duplicate values are common and must be handled carefully

The follow-up specifically asks for an O(n) solution, which means we should avoid sorting if possible. Sorting takes O(n log n) time, which is acceptable for the constraints but not optimal according to the follow-up requirement.

Several edge cases are important:

  • Arrays with fewer than three distinct numbers
  • Arrays where all numbers are identical
  • Arrays containing negative values
  • Arrays containing the minimum possible integer value
  • Arrays with many duplicates that could incorrectly inflate the count of maximum values

A naive implementation can easily fail if it counts duplicates separately or mishandles extreme integer values.

Approaches

Brute Force Approach

The most straightforward solution is to remove duplicates, sort the remaining numbers in descending order, and then return either:

  • the third element if at least three distinct numbers exist
  • the first element otherwise

For example:

  • Input: [2,2,3,1]
  • Distinct values: [2,3,1]
  • Sorted descending: [3,2,1]
  • Third distinct maximum: 1

This approach is easy to understand and guarantees correctness because sorting places all distinct values in order.

However, sorting requires O(n log n) time, which does not satisfy the follow-up requirement asking for O(n) complexity.

Optimal Approach

The key insight is that we do not need the full sorted order of the array. We only care about the top three distinct values.

Instead of sorting everything, we can scan through the array once while maintaining:

  • the largest distinct value
  • the second largest distinct value
  • the third largest distinct value

Whenever we encounter a new number:

  • Ignore it if it is already one of the tracked maximums
  • Update the tracked values appropriately if it belongs in the top three

This works because at any point during traversal, we maintain the invariant that the three variables always contain the three largest distinct numbers seen so far.

Since each number is processed exactly once, the algorithm runs in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Remove duplicates and sort descending
Optimal O(n) O(1) Track top three distinct values during one pass

Algorithm Walkthrough

  1. Initialize three variables named first, second, and third to represent the largest, second largest, and third largest distinct numbers seen so far. Initially, all are unset.
  2. Iterate through each number in the array.
  3. Before updating anything, check whether the current number is already equal to one of the tracked maximums. If it is, skip it because duplicates should not count multiple times.
  4. If the current number is larger than first, shift the existing values downward:
  • third becomes second
  • second becomes first
  • first becomes the current number
  1. Otherwise, if the number is smaller than first but larger than second, update:
  • third becomes second
  • second becomes the current number
  1. Otherwise, if the number is smaller than both first and second but larger than third, update third.
  2. After processing all numbers:
  • If third exists, return it
  • Otherwise, return first

We use only three variables because the problem only requires the third distinct maximum. Tracking anything beyond the top three would be unnecessary.

Why it works

At every iteration, the variables first, second, and third store the three largest distinct values encountered so far in descending order. Duplicate values are skipped, so each tracked value remains distinct. Since every number is examined exactly once and correctly inserted into its position among the top three, the final values after traversal represent the true top three distinct maximums in the array.

Python Solution

from typing import List

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        first = second = third = None

        for num in nums:
            # Skip duplicates
            if num == first or num == second or num == third:
                continue

            # Update first maximum
            if first is None or num > first:
                third = second
                second = first
                first = num

            # Update second maximum
            elif second is None or num > second:
                third = second
                second = num

            # Update third maximum
            elif third is None or num > third:
                third = num

        return third if third is not None else first

The implementation follows the algorithm directly.

The variables first, second, and third track the top three distinct values. They are initialized to None because the array may contain negative numbers, including the minimum possible integer value. Using None avoids needing special sentinel values.

The duplicate check is extremely important. Without it, repeated values could incorrectly occupy multiple ranking positions.

When a new largest value is found, the existing maximums shift downward to preserve ordering. The same logic applies when updating the second maximum.

At the end, if third is still None, it means fewer than three distinct values exist, so we return the maximum value stored in first.

Go Solution

package main

import "math"

func thirdMax(nums []int) int {
	first := math.MinInt64
	second := math.MinInt64
	third := math.MinInt64

	hasFirst := false
	hasSecond := false
	hasThird := false

	for _, num := range nums {
		// Skip duplicates
		if (hasFirst && num == first) ||
			(hasSecond && num == second) ||
			(hasThird && num == third) {
			continue
		}

		// Update first maximum
		if !hasFirst || num > first {
			third = second
			hasThird = hasSecond

			second = first
			hasSecond = hasFirst

			first = num
			hasFirst = true

		} else if !hasSecond || num > second {
			// Update second maximum
			third = second
			hasThird = hasSecond

			second = num
			hasSecond = true

		} else if !hasThird || num > third {
			// Update third maximum
			third = num
			hasThird = true
		}
	}

	if hasThird {
		return third
	}

	return first
}

The Go implementation uses explicit boolean flags because Go integers cannot naturally represent an uninitialized state like Python's None.

We use math.MinInt64 as a placeholder initial value, but the boolean flags determine whether a value is actually valid. This avoids issues when the input itself contains the minimum integer value.

The rest of the logic mirrors the Python solution exactly.

Worked Examples

Example 1

Input: nums = [3,2,1]

Step Current Number first second third
Start - None None None
1 3 3 None None
2 2 3 2 None
3 1 3 2 1

Since third exists, return 1.

Example 2

Input: nums = [1,2]

Step Current Number first second third
Start - None None None
1 1 1 None None
2 2 2 1 None

third does not exist, so return first = 2.

Example 3

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

Step Current Number Action first second third
Start - Initialize None None None
1 2 New first max 2 None None
2 2 Duplicate, skip 2 None None
3 3 Shift down 3 2 None
4 1 New third max 3 2 1

Return 1.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed exactly once
Space O(1) Only three tracking variables are used

The algorithm performs a single pass through the array, making the runtime linear in the number of elements. No auxiliary data structures proportional to input size are required, so the space complexity remains constant.

Test Cases

from typing import List

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        first = second = third = None

        for num in nums:
            if num == first or num == second or num == third:
                continue

            if first is None or num > first:
                third = second
                second = first
                first = num

            elif second is None or num > second:
                third = second
                second = num

            elif third is None or num > third:
                third = num

        return third if third is not None else first

sol = Solution()

assert sol.thirdMax([3, 2, 1]) == 1  # basic case with exactly 3 distinct values
assert sol.thirdMax([1, 2]) == 2  # fewer than 3 distinct values
assert sol.thirdMax([2, 2, 3, 1]) == 1  # duplicates should not count twice
assert sol.thirdMax([1, 1, 1]) == 1  # all values identical
assert sol.thirdMax([5]) == 5  # single element array
assert sol.thirdMax([-1, -2, -3]) == -3  # negative numbers
assert sol.thirdMax([1, 2, 2, 5, 3, 5]) == 2  # mixed duplicates
assert sol.thirdMax([2, 2, 2, 3]) == 3  # only two distinct values
assert sol.thirdMax([-2147483648, 1, 2]) == -2147483648  # minimum int value
assert sol.thirdMax([10, 9, 8, 7, 6]) == 8  # descending order
assert sol.thirdMax([1, 2, 3, 4, 5]) == 3  # ascending order
Test Why
[3,2,1] Standard case with exactly three distinct values
[1,2] Fewer than three distinct numbers
[2,2,3,1] Duplicate handling
[1,1,1] All numbers identical
[5] Smallest possible array
[-1,-2,-3] Negative number handling
[1,2,2,5,3,5] Multiple duplicates mixed with unique values
[2,2,2,3] Only two distinct values despite many duplicates
[-2147483648,1,2] Extreme integer boundary
[10,9,8,7,6] Descending input
[1,2,3,4,5] Ascending input

Edge Cases

Arrays With Fewer Than Three Distinct Values

A common mistake is assuming the array always contains at least three unique numbers. For example, [1,2] only has two distinct values. The correct behavior is to return the maximum value, not produce an error or incorrect third value.

The implementation handles this by checking whether third was ever assigned. If not, it returns first.

Arrays With Many Duplicates

Duplicates can easily break naive solutions. In [2,2,3,1], the value 2 appears twice but should count only once in the ranking.

The implementation explicitly skips any number already equal to first, second, or third. This guarantees that only distinct values are tracked.

Arrays Containing Extreme Integer Values

The constraints allow values as small as -2^31. Using sentinel values carelessly can create subtle bugs when the sentinel itself appears in the input.

The Python solution avoids this entirely by using None for uninitialized values. The Go solution uses boolean flags to distinguish valid values from placeholder initialization values.