Find the Largest Three Distinct Elements in an Array using C/C++

In this tutorial, we will demonstrate how to use a C/C++ programme to locate the highest three different elements in an array.

C/C++ Program to Find the Largest Three Different Elements in an Array. Expected time complexity is O (n), but additional space is O (1).

Examples:

Input: array [] = {20, 18, 6, 10, 46, 75}
Output: 75, 46, 20

1^st Approach:

Algorithm

• We will create three elements called maximum1, maximum2, and maximum3 that hold the values of the three largest elements and assign their values to array [0].
• Then, for each element, we shall loop from i -> 1 to n - 1.
• if ( array [i] > maximum1 ) -> maximum 3 = maximum 2, maximum 2 = maximum1 , maximum1 = array [i].
• else if ( array [i] > maximum2 ) -> maximum3 = maximum2, maximum2 = array [i].
• else if ( array [i] > max3 ) -> maximum3 = array [i].
• We will print all max three values at the completion of the loop.

The above algorithm is implemented as follows-

C Program:

#include <stdio.h>


void locatethethreelargestelements ( int array [], int array_size )
{
   int maximum1, maximum2, maximum3;
   maximum3 = maximum1 = maximum2 = array [0];
   for ( int i = 0; i < array_size; i++ )
   {
      if ( array[i] > maximum1 )
	  {
         maximum3 = maximum2;
         maximum2 = maximum1;
         maximum1 = array[i];
      }
      else if ( array [i] > maximum2 ) 
	  {
         maximum3 = maximum2;
         maximum2 = array [i];
      }
      else if ( array [i] > maximum3 )
         maximum3 = array [i];
   }
   printf ("\nLargest Three Different Elements in an Array are %d %d %d", maximum1 , maximum2 , maximum3 ) ;
}
int main ()
{
   int array [] = { 20, 18, 6, 10, 46, 75 };
   int n = sizeof ( array ) / sizeof ( array [0] ); 
   printf ("The array elements are : \n" );
   for (int i = 0; i < n; i++)  
      printf ("%d \t", array[i]); 
     locatethethreelargestelements (array, n);
   return 0;
} 

C++ Program:

#include <iostream>
using namespace std;


void locatethethreelargestelements ( int array [], int array_size )
{
   int maximum1, maximum2, maximum3;
   maximum3 = maximum1 = maximum2 = array [0];
   for ( int i = 0; i < array_size; i++ )
   {
      if ( array [i] > maximum1 )
	  {
         maximum3 = maximum2;
         maximum2 = maximum1;
         maximum1 = array[i];
      }
      else if ( array [i] > maximum2 ) 
	  {
         maximum3 = maximum2;
         maximum2 = array [i];
      }
      else if ( array [i] > maximum3 )
         maximum3 = array [i];
   }
   cout << endl << "\nLargest Three Different Elements in an Array are "<< maximum1 
   														 <<", "
														 << maximum2 
														 <<", "
														 << maximum3;
}
int main ()
{
   int array [] = { 20, 18, 6, 10, 46, 75 };
   int n = sizeof ( array ) / sizeof ( array [0] ); 
   cout << "The array elements are : " <<endl;
   for (int i = 0; i < n; i++)  
      cout << array[i] <<"\t"; 
     locatethethreelargestelements (array, n);
   return 0;
}

Output:

The array elements are :
20      18      6       10      46      75
Largest Three Different Elements in an Array are 75 46 20

Time Complexity: O (n)

Space Complexity: O (1)

2^nd Approach:

Algorithm:

• The array will be sorted using a sorting method.
• Print the largest three digits.

C Program:

#include <stdio.h>
#include <stdlib.h>
 
int comparefunc ( const void* x, const void* y )
{
    return (*(int*)x - *(int*)y);
}


void findthreelargest( int array [], int no )
{
    qsort ( array, no, sizeof(int),
          comparefunc ) ;
  
printf ("Largest Three Different Elements in an Array are :");
    int checkpt = 0, cnt = 1;
    for ( int i = 1; i <= no; i++ ) 
	{
        if (cnt < 4)
		 {
            if ( checkpt != array [no - i] ) 
			{
                printf ("%d ", array [no - i]);
                checkpt = array [no - i];
                cnt++;
            }
        }
        else
            break;
    }
}
 
int main()
{
    int array[] = { 56, 78, 93, 21, 60, 100 };
    
    int no = sizeof ( array ) / sizeof ( array [0] );
    findthreelargest ( array, no );
}

C++ Program:

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


void findthreelargest ( int array[], int no )
{
	cout <<"Largest Three Different Elements in an Array are: ";
	sort( array, array + no );
	int checkpt = 0, cnt = 1;
	for ( int i = 1; i <= no; i++ ) 
	{
		if ( cnt < 4 ) 
		{
			if ( checkpt != array [ no - i ] ) 
			{
				cout << array [ no - i ] << " ";
				checkpt = array [ no - i] ;
				cnt ++;
			}
		}
		else
			break;
	}
}
int main()
{
	int array[] = { 56, 78, 93, 21, 60, 100 };
	int n = sizeof ( array ) / sizeof (array [0] );
	findthreelargest ( array, n );
}

Output:

Largest Three Different Elements in an Array are: 100 93 78

Time Complexity: O (n log n)

Space Complexity: O (1)