# Program to find all elements in array of integers which have at-least two greater elements in C++

## C++ program to find all elements in an array of integers that have at-least two greater elements.

Given: An array of n elements, we have to find all elements in the array which have at-least two greater elements than themselves.

Example:

Input: arr[] = { 15, 2, 20, 12, 40}

Output: 15, 2, 12

Input: arr[] = { -2, 9, 12, -7, 2, 10}
Output: -2, 9, -7, 2

### # Brute Force (using loops)

1. Input an array from the user having n elements.
2. Pick up elements one by one and count the number of greater elements.
3. If the count is greater than 2, then print that element.

Code:

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

// finds elements having at least two greater elements
void greater_elements(int arr[], int n) {
cout << "\nElements which have at least two greater elements are: ";
for (int i = 0; i < n; i++) {
int var = 0;
for (int j = 0; j < n; j++) {
if (arr[j] > arr[i]) {
var++;
}
}
if (var >= 2) {
cout << arr[i] << " ";
}
}
}

int main() {
int arr, n, i;
cout << "Enter number of elements: ";
cin >> n;
cout << "\nEnter elements: ";
for (i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "Elements are: ";
for (i = 0; i < n; i++) {
cout << arr[i] << " ";
}
greater_elements(arr, n);
return 0;
}

``````

Output

``````Enter number of elements: 5

Enter elements: 1 4 3 2 5
Elements are: 1 4 3 2 5

Elements which have at least two greater elements are: 1 3 2

``````

Time Complexity : O(n2)

### # Optimized Approach(using sorting)

1. Input array from user having n elements.
2. Sort the array in increasing order.
3. Print first n-2 elements.

Code:

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

void greater_elements(int arr[], int n) {
sort(arr, arr + n);
for (int i = 0; i < n - 2; i++) {
cout << "\n" << arr[i] << " ";
}
}

// Driver Code
int main() {
int arr, n, i;
cout << "Enter number of elements: ";
cin >> n;
cout << "\nEnter elements: ";
for (i = 0; i < n; i++) {
cin >> arr[i];
}
cout << "\nElements are: ";
for (i = 0; i < n; i++) {
cout << arr[i] << ", ";
}
cout << endl;
greater_elements(arr, n);
return 0;
}

``````

Output

``````Enter number of elements: 2
Enter elements: 1 2
Elements are: 1, 2,
``````

Time Complexity : O(n Log n)