# 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