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

Software Development
#1

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[0]);

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[0]);

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[0]);

findElements(arr, n);

return 0;

}

Output

2 -6 1

Time Complexity: O(n)