Program to find third distinct maximum number in the array.

Given an integer array nums[] of size n, we need to find the third distinct maximum number in an integer array nums. If the third maximum number does not exist, we need to return the maximum number present in the array.

Note: If the array has less than three distinct maximum numbers, then we need to return the maximum number from the array.

Let's understand the problem with an example:

Example 1:
Input: nums[] = {3, 5, 1, 8, 5, 4, 2, 9}
Output: 5

Explanation:

The distinct maximum numbers in the array are 9, 8, and 5. 
So, the third distinct maximum number is 5.

Example 2:
Input: nums[] = {2, 8}
Output: 8

Explanation:

No third element is present in the given array 
so return the maximum element that is 8

Example 3:
Input: nums[] = {2, 2, 3, 1}
Output: 1

Explanation:

The distinct maximum numbers in the array are 3, 2, and 1.

So, the third distinct maximum number is 1.

There are multiple approaches by which we can solve this problem and here we are going to discuss each of them one by one.

Approach 1: Using Sorting.

The brute force approach to solve this problem is by arranging the given array in descending order which will make our task easier to find the third distinct element.

Steps-by-step algorithm:

Step 1: We can sort the array in descending order.

Step 2: Then, we can iterate through the sorted array and keep track of distinct maximum numbers.

Step 3: If we find the third distinct maximum number, we return it. Otherwise, we return the maximum number.

C++ Code Implementation for the above approach:

//C++ Program to find third distinct maximum
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

//function
int thirdMax(vector<int>& nums) {
    //arrange the vector in descending order
    sort(nums.begin(), nums.end(), greater<int>());

    int count = 1;
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] != nums[i - 1]) {
            count++;
        }
        if (count == 3) {
            return nums[i];
        }
    }
    //return max if no third distinct max is found
    return nums[0];
}

int main(){
    vector<int> nums = {3, 5, 1, 8, 5, 4, 2, 9};

    cout<< thirdMax(nums);

    return 0;
}

Output:

Time Complexity: The sorting operation using sort takes O(n * log n) time, where n is the number of elements in the input array. After sorting, we iterate through the sorted array once to find the third distinct maximum number. This step takes O(n) time. So, the overall time complexity is O(n * log n + n) = O(n * log n).

Space Complexity: The space complexity is O(1) as we are not using any additional data structure.

Approach 2: Using Set.

As we know a set container is used to store unique elements in a specific order and allows for efficient insertion, deletion, and retrieval of elements based on their values.

Step-by-step algorithm:

Step 1: We can use a set to keep track of distinct numbers while traversing the array.

Step 2: If the set size is less than 3 after traversing the array, it means we have less than three distinct maximum numbers, so we return the maximum number present in the array.

Step 3: If the set size is greater than or equal to 3, we return the third element from the set.

C++ Code Implementation for the above approach:

//C++ Program to find third distinct maximum using set
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;

//function
int thirdMax(vector<int>& nums) {
    set<int> distinctNums;

    //traverse the array and atmost
    //store three elements in the set
    for (int num : nums) {
        distinctNums.insert(num);
        if (distinctNums.size() > 3) {
            distinctNums.erase(distinctNums.begin());
        }
    }
    //size of set is less than 3 
    //no third distinct element present
    if(distinctNums.size() < 3)
    //return max element present in set
       return *(--distinctNums.end());
    //size of set is equal to 3 
    //top most element of set is the third distinct
    else
       return *(distinctNums.begin());
}

int main(){
    vector<int> nums = {3, 5, 1, 8, 5, 4, 2, 9};

    cout<< thirdMax(nums);

    return 0;
}

Output:

Note: The expression *(--distinctNums.end()) is used to access the last element in a set.

Time Complexity: The set insertion and deletion operations have an average time complexity of O(log n) then we iterate through the entire input array once, performing set operations on each element, so the overall time complexity is O(n * log n).

Space Complexity: The space required for the set depends on the number of distinct elements in the array, which is at most 3 in this case. Therefore, the space complexity is O(1), as it remains constant regardless of the input size.

Approach 3: Using three variables. (Most Optimized).

The idea for this optimized approach comes from the requirement to find the third distinct maximum number in a single pass through the array with O(n) time complexity. To achieve this efficiently, we need to keep track of the first, second, and third distinct maximum numbers while traversing the array.

Step-by-step algorithm:

Step 1: We declare three variables (firstMax, secondMax, thirdMax) to keep track of the first, second, and third distinct maximum numbers, respectively.

Step 2: We initialize them with the minimum possible value (INT_MIN).

Step 3: We traverse the input array and update these variables as follows:

If the current number is greater than firstMax, we update thirdMax with secondMax, secondMax with firstMax, and then update firstMax with the current number.
If the current number is between firstMax and secondMax, we update thirdMax with secondMax and secondMax with the current number.
If the current number is between secondMax and thirdMax, we update thirdMax with the current number.

Step 4: After the loop, if thirdMax remains equal to the initial value (INT_MIN), it means there are less than three distinct maximum numbers in the array, and we return firstMax (the maximum number). Otherwise, we return thirdMax.

C++ Code Implementation for the above approach:

//C++ Program to find third distinct maximum
#include <bits/stdc++.h>
using namespace std;

int thirdMax(vector<int>& nums) {
    int firstMax = INT_MIN;
    int secondMax = INT_MIN;
    int thirdMax = INT_MIN;

    for (int num : nums) {
        //current number is greater
        if (num > firstMax) {
            thirdMax = secondMax;
            secondMax = firstMax;
            firstMax = num;
        } 
        //current number is between first and second max
        else if (num < firstMax && num > secondMax) {
            thirdMax = secondMax;
            secondMax = num;
        } 
        //current number is between second and third max
        else if (num < secondMax && num > thirdMax) {
            thirdMax = num;
        }
    }

    return (thirdMax == INT_MIN) ? firstMax : thirdMax;
}


int main(){
    vector<int> nums = {3, 5, 1, 8, 5, 4, 2};

    cout<< thirdMax(nums);

    return 0;
}

Output:

Time Complexity: The time complexity of this solution is O(n) as we are able to find the required answer just in a single traversal.

Space Complexity: The space complexity is constant O(1) as we are only using three variables for solving this problem.

I hope you are able to understand all three approaches to solving this problem. We have covered all three approaches in sequence order from brute force to optimized one.

Program to find third distinct maximum number in the array.

Approach 1: Using Sorting.

Approach 2: Using Set.

Approach 3: Using three variables. (Most Optimized).

No comments:

Post a Comment