Third Maximum Number

🏠 ⬅️ ➡️

Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.

Example 1:

Input: nums = [3,2,1] Output: 1 Explanation: The first distinct maximum is 3. The second distinct maximum is 2. The third distinct maximum is 1.

Example 2:

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

Example 3:

Input: nums = [2,2,3,1] Output: 1 Explanation: The first distinct maximum is 3. The second distinct maximum is 2 (both 2's are counted together since they have the same value). The third distinct maximum is 1.

Constraints:

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

Follow up: Can you find an O(n) solution?

Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 3 ! number of elements in the array
    integer, dimension(n) :: nums = (/ 3, 2, 1 /) ! input array
    integer :: max_val, sec_max_val, thrd_max_val ! variables to store the values

    call get_distinct_max(nums, max_val, sec_max_val, thrd_max_val)

    write (*, '(A, I0)') 'Maximum value: ', max_val
    write (*, '(A, I0)') 'Second maximum value: ', sec_max_val
    write (*, '(A, I0)') 'Third maximum value: ', thrd_max_val

contains

    subroutine get_distinct_max(nums, max_val, sec_max_val, thrd_max_val)
        implicit none
        integer, intent(in) :: nums(:) ! input array
        integer, intent(out) :: max_val, sec_max_val, thrd_max_val ! output values
        integer :: i, j, k ! loop counters

        ! initialize variables
        max_val = nums(1)
        sec_max_val = max_val
        thrd_max_val = max_val

        ! loop through the array and find the distinct maxima
        do i = 2, size(nums)
            if (nums(i) > max_val) then
                thrd_max_val = sec_max_val
                sec_max_val = max_val
                max_val = nums(i)
            else if (nums(i) > sec_max_val) then
                thrd_max_val = sec_max_val
                sec_max_val = nums(i)
            end if
        end do

        ! check if the third maximum exists
        k = 0
        do j = 1, size(nums)
            if (nums(j) == sec_max_val) then
                k = k + 1
            end if
        end do

        if (k < 2) then
            thrd_max_val = max_val
        end if

    end subroutine get_distinct_max

end program main
❌ Compiled
❌ Executed
❌ Correct 
module third_distinct_maximum
    implicit none
    private
    public :: third_distinct_maximum

contains

    function third_distinct_maximum(nums) result(third_max)
        integer, intent(in) :: nums(:)
        integer :: third_max, max_count, max_val, i

        ! Initialize variables
        max_count = 0
        max_val = -huge(max_val)
        third_max = -huge(third_max)

        ! Loop through the array and find the maximum and maximum count
        do i = 1, size(nums)
            if (nums(i) > max_val) then
                max_count = max_count + 1
                if (max_count == 3) then
                    third_max = max_val
                    exit
                end if
                max_val = nums(i)
            end if
        end do

        ! If the third maximum does not exist, return the maximum
        if (third_max == -huge(third_max)) then
            third_max = max_val
        end if

    end function third_distinct_maximum
end module third_distinct_maximum

program test_third_distinct_maximum
    use third_distinct_maximum
    implicit none
    integer :: nums(3)

    ! Test case 1:
    nums = [3, 2, 1]
    write (*,*) "Third distinct maximum of ", nums, " is ", third_distinct_maximum(nums)

    ! Test case 2:
    nums = [1, 2]
    write (*,*) "Third distinct maximum of ", nums, " is ", third_distinct_maximum(nums)

    ! Test case 3:
    nums = [2, 2, 3, 1]
    write (*,*) "Third distinct maximum of ", nums, " is ", third_distinct_maximum(nums)
end program test_third_distinct_maximum
🌐 Data from online sources 
def third_max(nums):
    top3 = set()
    for num in nums:
        top3.add(num)
        if len(top3) > 3:
            top3.remove(min(top3))
    return min(top3) if len(top3) == 3 else max(top3)

The algorithm to solve the problem is as follows: 1. Initialize an empty set called top3 to keep track of the top 3 distinct maximum numbers in the array. 2. Iterate through the input array, nums. 3. For each number in nums, insert it into top3. 4. If the size of top3 becomes greater than 3, remove the smallest number in top3. 5. If the size of top3 is 3, which means there are three distinct maximum numbers, return the smallest number in top3. Otherwise, return the largest number in top3.

🌐 Data from online sources 
#include <set>

int thirdMax(vector<int>& nums) {
    set<int> top3;
    for (int num : nums) {
        top3.insert(num);
        if (top3.size() > 3) {
            top3.erase(top3.begin());
        }
    }
    return top3.size() == 3 ? *top3.begin() : *top3.rbegin();
}

The algorithm to solve the problem is as follows: 1. Initialize an empty set called top3 to keep track of the top 3 distinct maximum numbers in the array. 2. Iterate through the input array, nums. 3. For each number in nums, insert it into top3. 4. If the size of top3 becomes greater than 3, remove the smallest number in top3. 5. If the size of top3 is 3, which means there are three distinct maximum numbers, return the smallest number in top3. Otherwise, return the largest number in top3.