Home » Technical Interview Questions » Array Interview Questions » Queries for counts of array elements with values in given range

Queries for counts of array elements with values in given range


Reading Time - 6 mins


Difficulty Level Medium

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.

Queries for counts of array elements with values in given range

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.

READ  Shuffle 2n integers as a1-b1-a2-b2-a3-b3-..bn without using extra space

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).

READ  Find the Only Repetitive Element Between 1 to N-1

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.

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions