Third Maximum Number


To find the third distinct maximum number in an array, we can use Python’s builtin set and list data structures along with some of its builtin functions. Here’s how you can do it:


This code first converts nums
to a set to eliminate any duplicates and then converts it back to a list.
If the length of nums
is less than 3, it returns the maximum number.
Otherwise, it removes the maximum number from nums
twice, effectively removing the first two distinct maximums.
Finally, it returns the maximum number from nums
, which is now the third distinct maximum.
Identifying Problem Isomorphism
“Kth Largest Element in an Array” is an approximate isomorphism to “Third Maximum Number”. The task in both problems involves identifying the kth largest element in an array.
In “Third Maximum Number”, you have to find the third maximum number in a given array. If the array does not have a third maximum number, the task is to return the maximum number.
“Kth Largest Element in an Array” generalizes this task. You are given an integer array and an integer k, and the problem asks you to find the kth largest element in the array.
While the “Third Maximum Number” problem is specific to finding the third maximum element, “Kth Largest Element in an Array” allows for any kth largest element to be found, making it more generalized. The implementation of both problems would involve sorting or priority queue data structures. The “Kth Largest Element in an Array” problem is more flexible, hence it could be seen as slightly more complex depending on the value of k.


Problem Classification
This problem is classified under:
Array Manipulation: The problem involves working with an array of integers (nums).
Searching and Sorting: To find the third maximum number, the problem inherently requires sorting or searching through the array.
Distinct Elements: The problem specifically mentions the need to consider distinct maximum numbers.
Conditional Logic: The solution requires conditional checks to decide whether to return the third maximum or the maximum number.
Mathematics: The problem involves concepts related to order statistics, specifically finding the kth maximum element.
Language Agnostic Coding Drills
Here are the key concepts in the problem, ordered by increasing level of difficulty:
Understanding Python Lists (Arrays): Python Lists are used in this problem to store the array of numbers and the top 3 distinct numbers.
Understanding Sets: Sets are a builtin data type in Python that are mutable and can contain distinct elements. They are used in this problem to remove duplicates from the array.
Understanding Floating Point Representation: In Python, floating point numbers are represented using the float keyword. Negative infinity is represented as float(’inf’) and is used in this problem to initialize the array that stores the top 3 distinct numbers.
Array Iteration and Conditional Statements: This problem requires iterating through the array and using conditional statements to update the top 3 distinct numbers. This involves understanding of for loops and ifelse conditions.
Array Manipulation: The problem involves manipulating the array that stores the top 3 distinct numbers, based on the values in the given array. This requires knowledge of array indexing and assignment.
Understanding Python Functions: The code is wrapped inside a function that takes an array as input and returns an integer. Understanding of how functions work is crucial to implement the solution.
Here’s the stepbystep problem solving approach:
Convert the array into a set to remove duplicates.
Initialize an array T of size 3 to store the top 3 distinct numbers. This array is initialized with negative infinity.
Iterate over the array. For each number:
 If it’s greater than the first element in T, shift the elements in T and place the number at the first position.
 Else if it’s greater than the second element in T, shift the last two elements in T and place the number at the second position.
 Else if it’s greater than the third element in T, replace the third element in T with this number.
After iterating through all the numbers, if the third number in T is still negative infinity (which means there were less than 3 distinct numbers), return the first number in T (which is the maximum number). Otherwise, return the third number in T (which is the third maximum distinct number).
Targeted Drills in Python
 Understanding Python Lists (Arrays): Create a list of integers and print the list.


 Understanding Sets: Convert the above list to a set to remove duplicates and print the set.


 Understanding Floating Point Representation: Initialize a list with floating point negative infinity and print it.


 Array Iteration and Conditional Statements: Write a for loop to iterate over the ‘distinct_nums’ set. Print each number.


 Array Manipulation: In the above loop, add an if statement to check if the number is greater than the first element in T. If it is, shift the elements in T and place the number at the first position. Print T after every iteration.


 Understanding Python Functions: Wrap the above code into a function that takes ’nums’ as an input and returns the maximum number in ’nums’.


These drills cover the key concepts needed to solve the problem. The final solution would require combining these concepts and adding some additional logic to handle the cases for the second and third maximum numbers.