This problem statement is a part of LeetCode's learn card Introduction to Data Structures Fun with Arrays - 101. Under the sub-heading conclusion.
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).
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.
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.
- 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.
- 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.
- Create a variable maximum and store some arbitrary value in it.
- 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.
- 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.
- The result would be the third max element.
- 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
- Time complexity of the above solution is O(n).
- 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.