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
- 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
Learnings
- 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.
Top comments (7)
Hey, I love challenge! Thanks for your share...
I have an over approach for resolving problem by creating a new list with unque values.
What do you think about that 😉?
Hi Alex,
Well, I just reduced some lines of your code by mentioning the above points. Your approach also works :). But, you need to be careful while using sort(). List.sort() built-in has a time complexity of O(nlogn). It would make the code considerably slower. While the approach I shared has the time complexity of O(n). It was mentioned in the problem statement that the time complexity of the solution needs to be O(n).
I hope this helps. :)
Thanks for your adivces ! It's helpful!
My new version, is it better?
Cool! IMO still there is no need to create a new_list. Can you test the below code for some inputs? Should work.
Great !!! Thanks for your share...
I keep this. Best regards
def thirdmax(li):
li=list(dict.fromkeys(li))
if(len(li)>=3):
for i in range(0,2):
maximum=max(li)
li.remove(maximum)
maximum=max(li)
print(maximum)
else:
return max(li)
Will it still exceeds the time and space complexity.?
This also would would work. The only difference being instead of converting the list to set. You are converting it to a dict. A dict would gain give unique elements. And converting this dict back to list. As long as you have got unique elements in the list. Remove would work as expected.
One could either do these conversions and built-in methods. Or follow the way I have mentioned in the write-up. All possible solutions work and have time complexity O(n).