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

Find all elements in array which have at-least two greater elements - GeeksforGeeks
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.

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

void findElements(int arr[], int n)

{

    sort(arr, arr+n);

 

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

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

}

The naive 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 its true then print array element.

Time Complexity : O(n2)

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] << " ";

    }

}

Read full article from Find all elements in array which have at-least two greater elements - GeeksforGeeks