Find the largest three distinct elements in an array

Hello Everyone,

Given an array with all distinct elements, find the largest three elements. Expected time complexity is O(n) and extra space is O(1).
Examples :

Input: arr[] = {10, 4, 3, 50, 23, 90} Output: 90, 50, 23

Below is algorithm:

  1. Initialize the largest three elements as minus infinite. first = second = third = -∞ 2) Iterate through all elements of array. a) Let current array element be x. b) If (x > first) { // This order of assignment is important third = second second = first first = x } c) Else if (x > second) { third = second second = x } d) Else if (x > third) { third = x } 3) Print first, second and third.

Below is the implementation of the above algorithm.

// C++ program for find the largest

// three elements in an array

#include <bits/stdc++.h>

using namespace std;

// Function to print three largest elements

void print3largest( int arr[], int arr_size)

{

int first, second, third;

// There should be atleast three elements

if (arr_size < 3)

{

cout << " Invalid Input " ;

return ;

}

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];

}

// If arr[i] is in between first

// and second then update second

else if (arr[i] > second)

{

third = second;

second = arr[i];

}

else if (arr[i] > third)

third = arr[i];

}

cout << "Three largest elements are "

<< first << " " << second << " "

<< third << endl;

}

// Driver code

int main()

{

int arr[] = { 12, 13, 1, 10, 34, 1 };

int n = sizeof (arr) / sizeof (arr[0]);

print3largest(arr, n);

return 0;

}

Output :

Three largest elements are 34 13 12