Third Maximum Number

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

        for n in nums:
            if n > first:
                third, second, first = second, first, n
            elif n > second and n != first:
                third, second = second, n
            elif n > third and n != first and n != second:
                third = n

        return third if third != float('-inf') else first

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        # convert the list to a set to remove duplicates
        nums = list(set(nums))

        # If the length of the list is less than 3, return the max number
        if len(nums) < 3:
            return max(nums)

        # remove the max number from the list twice
        nums.remove(max(nums))
        nums.remove(max(nums))

        # return the max number (which is now the third distinct maximum)
        return max(nums)

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def thirdMax(self, nums: List[int]) -> int:
    	n, T = list(set(nums)), [float('-inf')]*3

    	for i in n:
    		if i > T[0]:
    			T = [i,T[0],T[1]]
    			continue
    		if i > T[1]:
    			T = [T[0],i,T[1]]
    			continue
    		if i > T[2]:
    			T = [T[0],T[1],i]

    	return T[2] if T[2] != float('-inf') else T[0]

Problem Classification

This problem is classified under:

  1. Array Manipulation: The problem involves working with an array of integers (nums).

  2. Searching and Sorting: To find the third maximum number, the problem inherently requires sorting or searching through the array.

  3. Distinct Elements: The problem specifically mentions the need to consider distinct maximum numbers.

  4. Conditional Logic: The solution requires conditional checks to decide whether to return the third maximum or the maximum number.

  5. Mathematics: The problem involves concepts related to order statistics, specifically finding the k-th maximum element.

Language Agnostic Coding Drills

Here are the key concepts in the problem, ordered by increasing level of difficulty:

  1. Understanding Python Lists (Arrays): Python Lists are used in this problem to store the array of numbers and the top 3 distinct numbers.

  2. Understanding Sets: Sets are a built-in data type in Python that are mutable and can contain distinct elements. They are used in this problem to remove duplicates from the array.

  3. 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.

  4. 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 if-else conditions.

  5. 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.

  6. 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 step-by-step problem solving approach:

  1. Convert the array into a set to remove duplicates.

  2. Initialize an array T of size 3 to store the top 3 distinct numbers. This array is initialized with negative infinity.

  3. 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.

  4. 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

  1. Understanding Python Lists (Arrays): Create a list of integers and print the list.
1
2

nums = [3, 2, 1, 5, 6, 3, 2]
print(nums)
  1. Understanding Sets: Convert the above list to a set to remove duplicates and print the set.
1
2

distinct_nums = set(nums)
print(distinct_nums)
  1. Understanding Floating Point Representation: Initialize a list with floating point negative infinity and print it.
1
2

T = [float('-inf')] * 3
print(T)
  1. Array Iteration and Conditional Statements: Write a for loop to iterate over the ‘distinct_nums’ set. Print each number.
1
2

for num in distinct_nums:
    print(num)
  1. 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.
1
2
3
4

for num in distinct_nums:
    if num > T[0]:
        T = [num] + T[:-1]
    print(T)
  1. Understanding Python Functions: Wrap the above code into a function that takes ’nums’ as an input and returns the maximum number in ’nums’.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def max_num(nums):
    distinct_nums = set(nums)
    T = [float('-inf')] * 3
    for num in distinct_nums:
        if num > T[0]:
            T = [num] + T[:-1]
    return T[0]

nums = [3, 2, 1, 5, 6, 3, 2]
print(max_num(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.