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.

Comments

[Alex]

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 😉?

def thirdMax(list):
    result = None
    if len(list) > 3:
        new_list = []
        for element in list:
            if element not in new_list:
                new_list.append(element)
        new_list.sort()
        result = new_list[-3]
        del new_list
    elif len(list)==3:
        list.sort()
        result = list[0]
    else:
        result = max(list)
    return result

[Mridu Bhatnagar]

Hi Alex,

1. For getting unique elements. Instead of for loop. You can directly convert the original list into a set. And, then again convert set into a list. The remaining code can be kept as it is. You can store the resulting output in new_list.
2. While using index -3 also works. An alternate approach could be new_list.sort(reverse=True). Now, the new_list would contain elements in descending order and you can pick 3rd index from the beginning. And store it in your result variable.

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. :)

[Alex]

Thanks for your adivces ! It's helpful!
My new version, is it better?

def thirdMax(lister):
    result = None
    dicolist = set(lister)
    new_list = list(dicolist)
    if len(new_list) > 3:
        for i in range(0,2):
            new_list.remove(max(new_list))
        result = max(new_list)
    elif len(new_list)==3:
        result = min(new_list)
    else:
        result = max(new_list)
    del dicolist
    del new_list
    return result

[Mridu Bhatnagar]

Cool! IMO still there is no need to create a new_list. Can you test the below code for some inputs? Should work.

def thirdMax(lister):
    lister = list(set(lister))
    if len(lister) > 3:
        for i in range(0,2):
            lister.remove(max(lister))
        result = max(lister)
    elif len(lister)==3:
        result = min(lister)
    else:
        result = max(lister)
    return result

[Alex]

Great !!! Thanks for your share...
I keep this. Best regards

[Lishagopi]

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

[Mridu Bhatnagar]

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