Leetcode – Third Maximum Number Solution in Python

Spread the love

Introduction

One of the problems on Leetcode that explores array manipulation and handling edge cases is ‘Third Maximum Number’. In this detailed article, we will dissect several approaches to solving this problem in Python, analyzing time complexity, and understanding the logic involved.

Problem Statement

The ‘Third Maximum Number’ problem is listed as problem number 414 on Leetcode. The problem statement is as follows:

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

Example:

Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.

Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Approach 1: Keeping Track of Top 3 Elements

  1. Initialize three variables max1, max2, and max3 as negative infinity. These will keep track of the first, second, and third maximum elements.
  2. Iterate through each element in the array.
  3. If the element is greater than max1, update max3 to max2, max2 to max1, and max1 to the current element.
  4. If the element is smaller than max1 but greater than max2, update max3 to max2 and max2 to the current element.
  5. If the element is smaller than max2 but greater than max3, update max3 to the current element.
  6. Return max3 if it is not negative infinity, otherwise return max1.
def thirdMax(nums):
    max1 = max2 = max3 = float('-inf')

    for num in nums:
        if num > max1:
            max1, max2, max3 = num, max1, max2
        elif max1 > num > max2:
            max2, max3 = num, max2
        elif max2 > num > max3:
            max3 = num

    return max3 if max3 != float('-inf') else max1

Time Complexity

The time complexity of this approach is O(n) because we go through each element of the array once, and the operations inside the loop take constant time.

Approach 2: Using a Set

  1. Create an empty set to keep track of unique maximum numbers.
  2. Iterate through each element in the array.
  3. Add the element to the set.
  4. If the size of the set is greater than 3, remove the minimum element from the set.
  5. After the loop, if the size of the set is 3, return the minimum element. Otherwise, return the maximum element.
def thirdMax(nums):
    max_set = set()

    for num in nums:
        max_set.add(num)
        if len(max_set) > 3:
            max_set.remove(min(max_set))

    return min(max_set) if len(max_set) == 3 else max(max_set)

Time Complexity

The time complexity of this approach is O(n), as we iterate through each element once, and adding and removing elements from the set takes constant time.

Approach 3: Using Python’s heapq Module

  1. Convert the array into a set to remove duplicates.
  2. If the size of the set is less than 3, return the maximum element.
  3. Otherwise, use the heapq.nsmallest function to find the third smallest element, which corresponds to the third maximum.
import heapq

def thirdMax(nums):
    unique_nums = set(nums)

    if len(unique_nums) < 3:
        return max(unique_nums)

    return heapq.nsmallest(3, unique_nums)[-1]

Time Complexity

This approach has a time complexity of O(n), where n is the size of the array.

Conclusion

The ‘Third Maximum Number’ problem on LeetCode can be tackled with a variety of approaches, including keeping track of the top 3 elements, using sets, or employing Python’s heapq module. Understanding and being able to implement these different strategies is crucial for solving not only this specific problem but also similar ones that involve finding k-th statistics in an array. Furthermore, it is essential to manage edge cases efficiently and ensure that the solution adheres to the required time complexity.

Leave a Reply