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)

Input an array from the user having n elements.
Pick up elements one by one and count the number of greater elements.
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[100], 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)

Input array from user having n elements.
Sort the array in increasing order.
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[100], 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)