Count of elements from the array

I am counting the element from array, which is greater then the given element (k)

   // Java implementation of the approach
class GFG
{
     
// Function to return the count of elements
// from the array which are greater than k
static int countGreater(int arr[], int n, int k) //arr-array, n-array length, k-number
{
//here first I sorted array
    int l = 0;
    int r = n - 1;
 
    // Stores the index of the left most element
    // from the array which is greater than k
    int leftGreater = n;
 
    // Finds number of elements greater than k
    while (l <= r) {
        int m = l + (r - l) / 2;
 
        // If mid element is greater than
        // k update leftGreater and r
        if (arr[m] > k) {
            leftGreater = m;
            r = m - 1;
        }
 
        // If mid element is less than
        // or equal to k update l
        else
            l = m + 1;
    }
 
    // Return the count of elements greater than k
    return (n - leftGreater);
}

I solved with comparing only one number, but what if I have an array to compare with

Answer

A simple O(nk) solution would be to go through arr for each number in arr2 and count the number of values that are greater.

static int[] countGreater(Integer arr[], int n, Integer arr2[], int k)
{       
    int[] res = new int[arr2.length];
    
    for(int i=0; i<k; i++)
    {
        int count = 0;
        for(int v : arr)
            if(v > arr2[i]) count++;
        res[i] = count;
    }
    
    return res;
}

However, we can do better than this by extending the method you’ve already identified – sorting arr and using binary search to identify the position of each value in arr2. If arr2 is also sorted then we can use the previously identified position as the initial left-hand edge of our binary search, since we know that subsequent elements in arr2 have to be greater than the current value.

Here’s some Java code to illustrate:

static int[] countGreater(Integer arr[], int n, Integer arr2[], int k)
{
    Collections.sort(Arrays.asList(arr));
    // assume arr2 is sorted, otherwise results could be out of order
    
    int[] res = new int[arr2.length];
    
    for(int i=0, pos=0; i<k; i++)
    {
        pos = 1 + Arrays.binarySearch(arr, pos, n, arr2[i]);
        if(pos < 0) pos = -pos;
        res[i] = n - pos;
    }
    
    return res;
}

I’ve simplified the code quite a bit by making use of the Arrays.binarySearch method.

For small values of n and k the simple approach will probably be faster, but as they grow the binarySearch approach will take over, despite the cost of the initial sort.