Queries for counts of array elements with values in given range

Problem Statement

The problem “Queries for counts of array elements with values in given range” states that you have an integer array and two number x and y. The problem statement asks to find out the count of numbers present in array that lies between the given x and y.

Example

arr[]={2,4,6,8,1,10}
x = 2, y = 8

4

Explanation

Because there are 4 elements present in an array, that is 2, 4, 6, and 8 that lie between the 2 and 8, inclusively.

arr[]={2,4,6,8,1,10}
x = 5, y = 10

3

Explanation

Because there are 3 elements present in an array, that are 6, 8, and 10, that lies between the 5 and 10 inclusively.

Algorithm

1. Sort the array.
2. Find out the greater index of the array of the element y by using binary search, return the greater index.
3. Find out the smaller index of the array of the element x by using binary search, return the smaller index.
4. Return the difference between the greater index and the smaller index and plus 1.

Explanation

We have given an integer array and two numbers x and y. We have asked to find out the total numbers present in a given array that lies between the given x and y. Basically, we have to find the count of numbers greater than the “x”. And the count of numbers smaller than “y”. We will be sorting the array. The reason behind it is that we are going to use a binary search method. That is also being modified.

Get the index of the number y in the array by using binary search. In the binary search, we try to find the index at which y is present. We continue the loop until the value of low is less than or equal to the value of high. Usually low is the 0th index and high is the array’s last index because we are doing a binary search over the array indices. Using binary search allows us ti answer Queries for counts of array elements with values in given range in logarithmic time complexity for each query.

We will get the middle of the low and high value, and check if the element present at array[mid] is greater than equal to x. If this is true, then update the value of high to mid-1. Else update the value of low to mid+1. The same is to be applied with the element y. But in that case, we will be finding the greater index, and instead of checking the array[mid] is greater than equal to y. Then keep checking if the array[mid] is less than equal to y, and update the value of low to mid+1 and value of high to mid-1.

Get both of the indices as greater and smaller, and return the difference of them and add 1 to it. This will be our required answer which is returned. Remember, we wanted to answer queries for counts of array elements with values in given range.

Code

C++ code to find the count of array elements within a given range

#include<iostream>
#include<algorithm>

using namespace std;

int smallerElement(int arr[], int n, int x)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] >= x)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return low;
}
int greaterElement(int arr[], int n, int y)
{
    int low = 0, high = n - 1;
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (arr[mid] <= y)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return high;
}
int countInRange(int arr[], int n, int x, int y)
{
    int count = 0;
    count = greaterElement(arr, n, y) - smallerElement(arr, n, x) + 1;
    return count;
}
int main()
{
    int arr[] = {2,4,6,8,1,10 };
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);

    int i = 2, j = 8;
    cout << countInRange(arr, n, i, j) << endl;

    i = 5, j = 10;
    cout << countInRange(arr, n, i, j) << endl;
    return 0;
}

4
3

Java program to find the count of array elements within a given range

import java.io.*;
import java.util.Arrays;

class NumberOfElements
{
    private static int countInRange(int arr[], int n, int x, int y)
    {
        int count = 0;
        count = greaterElement(arr, n, y) -
                smallerElement(arr, n, x) + 1;
        return count;
    }
    
    private static int smallerElement(int arr[], int n, int x)
    {
        int low = 0, high = n - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (arr[mid] >= x)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return low;
    }
    
    private static int greaterElement(int arr[], int n, int y)
    {
        int low = 0, high = n - 1;
        while (low <= high)
        {
            int mid = (low + high) / 2;
            if (arr[mid] <= y)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return high;
    }

    public static void main (String[] args)
    {
        int arr[] = {2,4,6,8,1,10 };
        int n = arr.length;

        Arrays.sort(arr);

        int x = 2, y = 8;
        System.out.println( countInRange(arr, n, x, y)); ;

        x = 5;
        y = 10;
        System.out.println( countInRange(arr, n, x, y));
    }
}

4
3

Complexity Analysis

Time Complexity

Time for running each query will be O(log n) and for sorting the array once will be O(n log n).

Space Complexity

O(n) where “n” is the number of elements in the array. Space which we have considered is because of the space taken during sorting of the array. The space required for storing the input is not considered in the “Queries for counts of array elements with values in given range” problem.