Day-19 Third Maximum Number

Background

This problem statement is a part of LeetCode’s learn card Introduction to Data Structures Fun with Arrays – 101. Under the sub-heading conclusion.

Problem Statement

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 1

Input: [3, 2, 1]

Output: 1

Explanation: The third maximum is 1.

Example 2

Input: [1, 2]

Output: 2

Explanation: The third maximum does not exist, so the maximum (2) is returned instead.

Example 3

Input: [2, 2, 3, 1]

Output: 1

Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

Solution Approach 1

• Intuitively initial thought that came was to keep calculating max from the array. But, this would also mean every time the maximum element is found. Then we would have to remove the same element from the array. Then again calculate max from the remaining elements in the array.

Problems with solution approach 1

• Built-in remove cannot be used for deleting an element because there can be duplicate elements present in the list. Remove will only delete the first occurrence of the element.

Solution Approach 2

1. Create a variable maximum and store some arbitrary value in it.
2. If the length of the list is greater than 3. Then iterate over the list. If the value of the element is greater than the value of the maximum variable. Store the value of the element in maximum.
3. Store some arbitrary value in variable second_max. Iterate over the list. If element value is not equal to the value of the maximum. Then again compare all element values with the value of second_max. If the value of element is greater than the stored value in second_max. Replace.
4. The result would be the third max element.
5. Else if the length of the list is not greater than 3. Then return a max of the array.

import sys
class Solution:
    def thirdMax(self, nums: List[int]) -> int:
        maximum = -sys.maxsize
        if len(nums) >= 3:
            for element in nums:
                if element > maximum:
                    maximum = element
            second_max = -sys.maxsize
            for element in nums:
                if (element != maximum) and (second_max < element):
                    second_max = element
            third_max = -sys.maxsize
            for element in nums:
                if (element != maximum) and (element != second_max) and (third_max < element):
                    third_max = element
            if (maximum != -sys.maxsize) and (second_max != -sys.maxsize) and (third_max != -sys.maxsize):
                result = third_max
            else:
                result = max(nums)
        else:
            result = max(nums)

        return result

Learnings

1. Time complexity of the above solution is O(n).
2. The initial value of the maximum, second_max, third_max has to be a number that doesn’t exist in the original list. Otherwise, it would lead to unexpected output.

原文链接：Day-19 Third Maximum Number