# Find the largest three distinct elements in an array

• Difficulty Level : Easy
• Last Updated : 21 Jul, 2022

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```

Method 1:

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 and x != first)
{
third = second
second = x
}
d)  Else if (x > third and x != second)
{
third = x
}

3) Print first, second and third.```

Below is the implementation of the above algorithm.

## C++

 `// C++ program for find the largest``// three elements in an array``#include ``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 && arr[i] != first)``        ``{``            ``third = second;``            ``second = arr[i];``        ``}` `        ``else` `if` `(arr[i] > third && arr[i] != second)``            ``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);``    ` `    ``print3largest(arr, n);``    ``return` `0;``}` `// This code is contributed by Anjali_Chauhan`

## C

 `// C program for find the largest``// three elements in an array``#include /* For INT_MIN */``#include ` `/* Function to print three largest elements */``void` `print3largest(``int` `arr[], ``int` `arr_size)``{``    ``int` `i, first, second, third;` `    ``/* There should be atleast three elements */``    ``if` `(arr_size < 3) {``        ``printf``(``" Invalid Input "``);``        ``return``;``    ``}` `    ``third = first = second = INT_MIN;``    ``for` `(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];``    ``}` `    ``printf``(``"Three largest elements are %d %d %d\n"``, first, second, third);``}` `/* Driver program to test above function */``int` `main()``{``    ``int` `arr[] = { 12, 13, 1, 10, 34, 1 };``    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr);``    ``print3largest(arr, n);``    ``return` `0;``}``/*This code is edited by Ayush Singla(@ayusin51)*/`

## Java

 `// Java code to find largest three elements``// in an array` `class` `PrintLargest {``    ``/* Function to print three largest elements */``    ``static` `void` `print3largest(``int` `arr[], ``int` `arr_size)``    ``{``        ``int` `i, first, second, third;` `        ``/* There should be atleast three elements */``        ``if` `(arr_size < ``3``) {``            ``System.out.print(``" Invalid Input "``);``            ``return``;``        ``}` `        ``third = first = second = Integer.MIN_VALUE;``        ``for` `(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];``        ``}` `        ``System.out.println(``"Three largest elements are "` `+ first + ``" "` `+ second + ``" "` `+ third);``    ``}` `    ``/* Driver program to test above function*/``    ``public` `static` `void` `main(String[] args)``    ``{``        ``int` `arr[] = { ``12``, ``13``, ``1``, ``10``, ``34``, ``1` `};``        ``int` `n = arr.length;``        ``print3largest(arr, n);``    ``}``}``/*This code is contributed by Prakriti Gupta``and edited by Ayush Singla(@ayusin51)*/`

## Python3

 `# Python3 code to find largest three``# elements in an array``import` `sys` `# Function to print three largest``# elements``def` `print3largest(arr, arr_size):` `    ``# There should be atleast three``    ``# elements``    ``if` `(arr_size < ``3``):``    ` `        ``print``(``" Invalid Input "``)``        ``return``    ` `    ``third ``=` `first ``=` `second ``=` `-``sys.maxsize``    ` `    ``for` `i ``in` `range``(``0``, arr_size):``    ` `        ``# 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``        ``elif` `(arr[i] > second):``        ` `            ``third ``=` `second``            ``second ``=` `arr[i]``        ` `        ``elif` `(arr[i] > third):``            ``third ``=` `arr[i]``    ` `    ``print``(``"Three largest elements are"``,``                  ``first, second, third)` `# Driver program to test above function``arr ``=` `[``12``, ``13``, ``1``, ``10``, ``34``, ``1``]``n ``=` `len``(arr)``print3largest(arr, n)` `# This code is contributed by Smitha Dinesh Semwal``# and edited by Ayush Singla(@ayusin51).`

## C#

 `// C# code to find largest``// three elements in an array``using` `System;` `class` `PrintLargest {` `    ``// Function to print three``    ``// largest elements``    ``static` `void` `print3largest(``int``[] arr,``                              ``int` `arr_size)``    ``{``        ``int` `i, first, second, third;` `        ``// There should be atleast three elements``        ``if` `(arr_size < 3) {``            ``Console.WriteLine(``"Invalid Input"``);``            ``return``;``        ``}` `        ``third = first = second = 000;``        ``for` `(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 && arr[i] != first) {``                ``third = second;``                ``second = arr[i];``            ``}` `            ``else` `if` `(arr[i] > third && arr[i]!=second)``                ``third = arr[i];``        ``}` `        ``Console.WriteLine(``"Three largest elements are "` `+ first + ``" "` `+ second + ``" "` `+ third);``    ``}` `    ``// Driver code``    ``public` `static` `void` `Main()``    ``{``        ``int``[] arr = ``new` `int``[] { 12, 13, 1, 10, 34, 1 };``        ``int` `n = arr.Length;``        ``print3largest(arr, n);``    ``}``}` `// This code is contributed by KRV and edited by Ayush Singla(@ayusin51).`

## PHP

 ` ``\$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``];``    ``}` `    ``echo` `"Three largest elements are "``,``       ``\$first``, ``" "``, ``\$second``, ``" "``, ``\$third``;``}`  `// Driver Code``\$arr` `= ``array``(12, 13, 1,``             ``10, 34, 1);``\$n` `= ``count``(``\$arr``);``print3largest(``\$arr``, ``\$n``);` `// This code is contributed by anuj_67 and edited by Ayush Singla(@ayusin51).``?>`

## Javascript

 ``

Output

`Three largest elements are 34 13 12`

Time Complexity: O(n)
Auxiliary Space: O(1)

Method 2:

An efficient way to solve this problem is to use any O(nLogn) sorting algorithm & simply returning the last 3 largest elements.

## C++

 `// C++ code to find largest three elements in an array``#include ``using` `namespace` `std;` `void` `find3largest(``int` `arr[], ``int` `n)``{``    ``sort(arr, arr + n); ``// It uses Tuned Quicksort with``    ``// avg. case Time complexity = O(nLogn)` `    ``int` `check = 0, count = 1;``    ``for` `(``int` `i = 1; i <= n; i++) {``        ``if` `(count < 4) {``            ``if` `(check != arr[n - i]) {``                ``// to handle duplicate values``                ``cout << arr[n - i] << ``" "``;``                ``check = arr[n - i];``                ``count++;``            ``}``        ``}``        ``else``            ``break``;``    ``}``}` `// Driver code``int` `main()``{``    ``int` `arr[] = { 12, 45, 1, -1, 45, 54, 23, 5, 0, -10 };``    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr);``    ``find3largest(arr, n);``}` `// This code is contributed by Aditya Kumar (adityakumar129)`

## C

 `// C code to find largest three elements in an array``#include ``#include ` `// Compare function for qsort``int` `cmpfunc(``const` `void``* a, ``const` `void``* b)``{``    ``return` `(*(``int``*)a - *(``int``*)b);``}` `void` `find3largest(``int` `arr[], ``int` `n)``{``    ``qsort``(arr, n, ``sizeof``(``int``),``          ``cmpfunc); ``// It uses Tuned Quicksort with``    ``// avg. case Time complexity = O(nLogn)` `    ``int` `check = 0, count = 1;``    ``for` `(``int` `i = 1; i <= n; i++) {``        ``if` `(count < 4) {``            ``if` `(check != arr[n - i]) {``                ``// to handle duplicate values``                ``printf``(``"%d "``, arr[n - i]);``                ``check = arr[n - i];``                ``count++;``            ``}``        ``}``        ``else``            ``break``;``    ``}``}` `// Driver code``int` `main()``{``    ``int` `arr[] = { 12, 45, 1, -1, 45, 54, 23, 5, 0, -10 };``    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr);``    ``find3largest(arr, n);``}` `// This code is contributed by Aditya Kumar (adityakumar129)`

## Java

 `// Java code to find largest``// three elements in an array` `import` `java.io.*;``import` `java.util.Arrays;` `class` `GFG {``    ``void` `find3largest(``int``[] arr)``    ``{``        ``Arrays.sort(arr); ``// It uses Tuned Quicksort with``        ``// avg. case Time complexity = O(nLogn)``        ``int` `n = arr.length;``        ``int` `check = ``0``, count = ``1``;` `        ``for` `(``int` `i = ``1``; i <= n; i++) {` `            ``if` `(count < ``4``) {``                ``if` `(check != arr[n - i]) {``                    ``// to handle duplicate values``                    ``System.out.print(arr[n - i] + ``" "``);``                    ``check = arr[n - i];``                    ``count++;``                ``}``            ``}``            ``else``                ``break``;``        ``}``    ``}` `    ``// Driver code``    ``public` `static` `void` `main(String[] args)``    ``{``        ``GFG obj = ``new` `GFG();``        ``int``[] arr = { ``12``, ``45``, ``1``, -``1``, ``45``, ``54``, ``23``, ``5``, ``0``, -``10` `};``        ``obj.find3largest(arr);``    ``}``}``// This code is contributed by Prashant Malik`

## Python3

 `# Python3 code to find largest``# three elements in an array``def` `find3largest(arr, n):``    ``arr ``=` `sorted``(arr) ``# It uses Tuned Quicksort with``                      ``# avg. case Time complexity = O(nLogn)` `    ``check ``=` `0``    ``count ``=` `1` `    ``for` `i ``in` `range``(``1``, n ``+` `1``):` `        ``if``(count < ``4``):``            ``if``(check !``=` `arr[n ``-` `i]):``                ` `                ``# to handle duplicate values``                ``print``(arr[n ``-` `i], end ``=` `" "``)``                ``check ``=` `arr[n ``-` `i]``                ``count ``+``=` `1``        ``else``:``            ``break` `# Driver code``arr ``=` `[``12``, ``45``, ``1``, ``-``1``, ``45``,``       ``54``, ``23``, ``5``, ``0``, ``-``10``]``n ``=` `len``(arr)``find3largest(arr, n)` `# This code is contributed by mohit kumar`

## C#

 `// C# code to find largest``// three elements in an array``using` `System;` `class` `GFG {``    ``void` `find3largest(``int``[] arr)``    ``{``        ``Array.Sort(arr); ``// It uses Tuned Quicksort with``        ``// avg. case Time complexity = O(nLogn)``        ``int` `n = arr.Length;``        ``int` `check = 0, count = 1;` `        ``for` `(``int` `i = 1; i <= n; i++) {``            ``if` `(count < 4) {``                ``if` `(check != arr[n - i]) {``                    ``// to handle duplicate values``                    ``Console.Write(arr[n - i] + ``" "``);``                    ``check = arr[n - i];``                    ``count++;``                ``}``            ``}``            ``else``                ``break``;``        ``}``    ``}` `    ``// Driver code``    ``public` `static` `void` `Main()``    ``{``        ``GFG obj = ``new` `GFG();``        ``int``[] arr = { 12, 45, 1, -1, 45,``                      ``54, 23, 5, 0, -10 };``        ``obj.find3largest(arr);``    ``}``}` `// This code is contributed by Code_Mech`

## Javascript

 ``

Output

`54 45 23 `

Time Complexity: O(n log n)
Auxiliary Space: O(1)

Method 3:
We can use Partial Sort of C++ STL. partial_sort uses Heapselect, which provides better performance than Quickselect for small M. As a side effect, the end state of Heapselect leaves you with a heap, which means that you get the first half of the Heapsort algorithm “for free”. The complexity is “approximately” O(N log(M)), where M is distance(middle-first).

## C++

 `#include ``using` `namespace` `std;``int` `main()``{``    ``vector<``int``> V = { 11, 65, 193, 36, 209, 664, 32 };``    ``partial_sort(V.begin(), V.begin() + 3, V.end(), greater<``int``>());` `    ``cout << ``"first = "` `<< V << ``"\n"``;``    ``cout << ``"second = "` `<< V << ``"\n"``;``    ``cout << ``"third = "` `<< V << ``"\n"``;``    ``return` `0;``}`

## Java

 `// java program to find``// three largest elements``// in array.``import` `java.io.*;``import` `java.util.Arrays;``class` `GFG{``  ``public` `static` `void` `main(String[] args)``  ``{``    ``int``[] V = { ``11``, ``65``, ``193``, ``36``, ``209``, ``664``, ``32` `};` `    ``// sorting the array``    ``Arrays.sort(V);` `    ``// taking the length of array``    ``int` `x = V.length;` `    ``System.out.println(``"first = "` `+ V[x-``1``] );``    ``System.out.println(``"second = "` `+ V[x-``2``]);``    ``System.out.println(``"third = "` `+ V[x-``3``] );` `  ``}``}` `// This code is Contributed Machhaliya Muhammad`

## Python3

 `# Python program to implement``# the above approach` `# Driver Code``V ``=` `[ ``11``, ``65``, ``193``, ``36``, ``209``, ``664``, ``32` `];``V.sort()``V.reverse()` `print``(f``"first =  {V}"``);``print``(f``"second =  {V}"``);``print``(f``"third =  {V}"``);``    ` `# This code is contributed by Saurabh Jaiswal`

## C#

 `// C# program to implement``// the above approach``using` `System;` `class` `GFG``{`  `// Driver Code``public` `static` `void` `Main()``{``    ``int``[] V = { 11, 65, 193, 36, 209, 664, 32 };``    ``Array.Sort(V);``    ``Array.Reverse(V);``   ` ` ` `    ``Console.WriteLine(``"first = "` `+ V );``    ``Console.WriteLine(``"second = "` `+ V);``    ``Console.WriteLine(``"third = "` `+ V );``    ` `}``}` `// This code is contributed by code_hunt.`

## Javascript

 ``

Output

```first = 664
second = 209
third = 193```

Time Complexity: O(n log m) where m is distance(middle-first).
Auxiliary Space: O(1)

My Personal Notes arrow_drop_up