# Find all elements in array which have at-least two greater elements

Hello Everyone,

Given an array of n distinct elements, the task is to find all elements in array which have at-least two greater elements than themselves.

Examples :

Input : arr[] = {2, 8, 7, 1, 5};
Output : 2 1 5
Explanation:
The output three elements have two or more greater elements

Explanation:
Input : arr[] = {7, -2, 3, 4, 9, -1};
Output : -2 3 4 -1

Method 1
The naïve approach is to run two loops and check one by one element of array check that array elements have at-least two elements greater than itself or not. If it’s true then print array element.

`// Simple C++ program to find`

`// all elements in array which`

`// have at-least two greater`

`// elements itself.`

`#include<bits/stdc++.h>`

`using` `namespace` `std;`

`void` `findElements(` `int` `arr[], ` `int` `n)`

`{`

` ` `// Pick elements one by one and`

` ` `// count greater elements. If`

` ` `// count is more than 2, print`

` ` `// that element.`

` ` `for` `(` `int` `i = 0; i < n; i++)`

` ` `{`

` ` `int` `count = 0;`

` ` `for` `(` `int` `j = 0; j < n; j++)`

` ` `if` `(arr[j] > arr[i])`

` ` `count++;`

` ` `if` `(count >= 2)`

` ` `cout << arr[i] << ` `" "` `;`

` ` `}`

`}`

`// Driver code`

`int` `main()`

`{`

` ` `int` `arr[] = { 2, -6 ,3 , 5, 1};`

` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr);`

` ` `findElements(arr, n);`

` ` `return` `0;`

`}`

Output

2 -6 1

Time Complexity: O(n2)

Method 2 (Use Sorting)
We sort the array first in increasing order, then we print first n-2 elements where n is size of array.

`// Sorting based C++ program to`

`// find all elements in array`

`// which have atleast two greater`

`// elements itself.`

`#include<bits/stdc++.h>`

`using` `namespace` `std;`

`void` `findElements(` `int` `arr[], ` `int` `n)`

`{`

` ` `sort(arr, arr + n);`

` ` `for` `(` `int` `i = 0; i < n - 2; i++)`

` ` `cout << arr[i] << ` `" "` `;`

`}`

`// Driver Code`

`int` `main()`

`{`

` ` `int` `arr[] = { 2, -6 ,3 , 5, 1};`

` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr);`

` ` `findElements(arr, n);`

` ` `return` `0;`

`}`

Output

-6 1 2

Time Complexity: O(n Log n)

Method 3 (Efficient)
In the second method we simply calculate the second maximum element of the array and print all element which is less than or equal to the second maximum.

`// C++ program to find all elements`

`// in array which have atleast two`

`// greater elements itself.`

`#include<bits/stdc++.h>`

`using` `namespace` `std;`

`void` `findElements(` `int` `arr[], ` `int` `n)`

`{`

` ` `int` `first = INT_MIN,`

` ` `second = INT_MIN;`

` ` `for` `(` `int` `i = 0; i < n; i++)`

` ` `{`

` ` `/* If current element is smaller`

` ` `than first then update both first`

` ` `and second */`

` ` `if` `(arr[i] > first)`

` ` `{`

` ` `second = first;`

` ` `first = arr[i];`

` ` `}`

` ` `/* If arr[i] is in between first`

` ` `and second then update second */`

` ` `else` `if` `(arr[i] > second)`

` ` `second = arr[i];`

` ` `}`

` ` `for` `(` `int` `i = 0; i < n; i++)`

` ` `if` `(arr[i] < second)`

` ` `cout << arr[i] << ` `" "` `;`

`}`

`// Driver code`

`int` `main()`

`{`

` ` `int` `arr[] = { 2, -6, 3, 5, 1};`

` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(arr);`

` ` `findElements(arr, n);`

` ` `return` `0;`

`}`

Output

2 -6 1

Time Complexity: O(n)