Find the three largest distinct elements in the array

Some Examples

Input

arr = {30, 20, 10, 40, 100, 80}

Output

The largest three numbers are: 100, 80, 40 

Explanation

The largest three distinct elements in the array are 100, 80, 40.

Input

arr = {30, 20, 10, 40, 100, 80, 80, 100, 110}

Output

The Largest three numbers are: 110, 100, 80

Explanation

The largest three distinct elements in the array are 110, 100, 80.

Read more, Array in Java

Find the three largest distinct elements in the array

Now we will solve this problem on how to find the three largest distinct elements in the array in C++ using many different methods. These methods are as follows:

Method 1

First, let's start with a very simple program to  Find the three largest distinct elements in the array in C++ by iterating through the array and using comparison operators.

Code:

// C++ program to find the largest three elements in an array
#include <bits/stdc++.h>
using namespace std;
 
// Function to print three largest elements
void printThreeLargest(int arr[], int arr_size){
    int first, second, third;
 
    third = first = second = INT_MIN;
    for(int i=0; i < arr_size; i++) {
         
            // If current element is greater than first
            if (arr[i] > first) {
                    third = second;
                    second = first;
                    first = arr[i];
            } else if (arr[i] > second) {
                    third = second;
                    second = arr[i];
            } else if (arr[i] > third) {
                    third = arr[i];
                       }
    }
 
    cout<<"Largest three distinct numbers are: "<<first<< " " <<second<< " "<<third<< endl;
}
 
// Driver code
int main()
{
    int arr1[] = {30, 20, 10, 40, 100, 80};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
     
    printThreeLargest(arr1, n1);
    
    
    int arr2[] = {30, 20, 10, 40, 100, 80, 80, 100, 110};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    
    printThreeLargest(arr2, n2);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

The above code will find the three largest distinct elements in the array using the comparison operators by iterating through the array. The output of the above code is displayed below:

Output

Time Complexity: O(n) because we iterate through the whole array.

Space Complexity: O(1) because only three extra variables are used.

Method 2

Here simply, we will sort the complete array and then we can find the three largest distinct elements in the array simply by selecting the last three elements. 

We can implement this approach as mentioned below:

Code:

#include <bits/stdc++.h>
using namespace std;


// Function to print three largest elements
void printThreeLargest(int arr[], int n){
    // STL function to sort array in c++
    sort(arr, arr + n);
    
    int check = 0, count = 1;
    cout<<"Largest three distinct numbers are: ";
 
    for (int i = 1; i <= n; i++) {
 
        if (count < 4) {
            if (check != arr[n - i]) {
                // Checking duplicates
                cout << arr[n - i] << " ";
                check = arr[n - i];
                count++;
            }
        }
        else
            break;
    }
    
    cout<<endl;
}
 
// Driver code
int main()
{
    int arr1[] = {30, 20, 10, 40, 100, 80};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
     
    printThreeLargest(arr1, n1);
    
    
    int arr2[] = {30, 20, 10, 40, 100, 80, 80, 100, 110};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    
    printThreeLargest(arr2, n2);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

The above code will find the three largest distinct elements in the array using the inbuilt sort function in C++. The output of the above code will be the same as method 1.

Output

Time Complexity: O(n log n) because the sorting algorithm (inbuilt sort method) used here have an average time complexity of O(n logn).

Space Complexity: O(1) because no extra variable is used. 

You can try by yourself with the help of online C++ Compiler.

Also read -  Decimal to Binary c++

FAQs

1. Which method is best to find the three largest distinct elements in the array?
   The best method to find the three largest distinct elements in the array in C++ is by iterating through the array and using comparison operators. This method has a time complexity of O(n) and the space complexity of O(1).
    
2. What is the time complexity of std::sort() in C++?
   The time complexity of std::sort() in C++ is O(n log n).

Key Takeaways

In this article, we have extensively discussed how to find the three largest distinct elements in the array in C++ using different-different methods.

We hope that this blog has helped you enhance your knowledge on how to find the three largest distinct elements in the array in C++, and if you would like to learn more about Data Structures and Algorithms, you can enroll in our DSA in C++ Course.

Do upvote our blog to help other ninjas grow. Happy Coding!