Number of Elements less than or equal to a given number in a given subarray

Introduction- 

This blog will discuss the problem of evaluating the queries to find the number of elements less than or equal to a given number in a given subarray. 

In this problem, we will be given an array of integers containing ‘N’ elements, and ‘q’ number of queries. Each query is of the form {X, L, R} and for each query, we have to find the number of elements less than or equal to ‘X’ in subarray [L, R] of the given array.

Let's take an example to understand the problem:

Assume the given array and number of queries are:

arr = {2, 4, 3, 6, 9}

q = 3

And the queries are: {{2, 0, 3},  {7, 0, 4}, {3, 0, 2}}

The given queries will be evaluated as follows:

Query 1: {2, 0, 3} = Number of elements less than or equal to 2 in the subarray {2, 4, 3, 6} = 1

Query 1: {7, 0, 4} = Number of elements less than or equal to 7 in the subarray {2, 4, 3, 6, 9} = 4

Query 1: {3, 0, 2} = Number of elements less than or equal to 3 in the subarray {2, 4, 3} = 2

 Now that we understand the problem let's discuss the approach to solve it in the next section.

Solution Approach

This section will discuss the approach to find the number of elements less than or equal to a given number in a given subarray. A simple approach is to traverse the given subarray in each query and count the number of elements less than or equal to the given value of ‘X’.  

The efficient approach is to use a Binary Indexed tree. We can use a binary indexed tree “bit” array to store the number of elements less than or equal to ‘x’ in arr[0……i] for each value of ‘i’ and then for a query {x, L, R}, calculate the number of elements less than equal to ‘x’ in the range [L, R] as the number of elements less than equal to ‘x’ in the range [0, R] minus the number of elements less than or equal to ‘x’ in the range [0, L-1].

Algorithm -

Step 1. First, the main function. Inside the main function, create an array ‘arr’ to store the given array and a two-dimensional vector to store queries of the form {x, L, R}. Then call the function “evaluateQueries()” to find the number of elements less than or equal to a given number in a given subarray for each query.

Step 2. Next, create the function “evaluateQueries()” to find the number of elements less than or equal to a given number in a given subarray for each query. It takes following input parameters:

1. arr: Given array of elements
2. queries: A 2-dimensional vector storing the queries of thr form {x, L, R}
3. n: Number of elements in the given array
4. q: Number of queries

Step 3.  Inside the function “evaluateQueries()”, create “bit” array of size ‘n’ and store all its elements as ‘0’ initially. Sort the array ‘arr’ and the ‘queries’ vector accoriding to increasing order of ‘x’. Before sorting the ‘queries’ vector, store the original index of each query. 

Step 4. Now, for each query traverse the array till the array elements are less than equal to ‘x’ and update ‘bit’ array. Then store ans for each query as number of elements less than equal to ‘x’ in range [0, R] minus number of elements less than or equal to ‘x’ in range [0, L-1].

Step 5. Finally, write the helper functions “update()” to store the number of elements less than or equal to a given number for each index and “query()” to find the number of elements less than or equal to a given number in a given subarray.

C++ code:

// C++ code to evaluate the queries to find the number of elements less than or equal to a given number in a given subarray
#include<bits/stdc++.h>
using namespace std;


// Helper function used to sort the queries vector in the increasing order of 'x'
bool sortByCol(const vector<int>& v1, const vector<int>& v2)
{
    return v1[0] < v2[0];
}


// updating the bit array
void update(int bit[], int index, int val, int n)
{
	for(int i = index; i <= n; i+= i&-i)
	{
		bit[i] += val;
	}
}


// querying the bit array
int query(int bit[], int index, int n)
{
	int sum = 0;
	for(int i= index; i>0; i -= i&-i)
	{
		sum += bit[i];
	}
	return sum;
}


// Function to evaluate the queries to find the number of elements less than or equal to a given number in a given subarray
vector<int> evaluateQueries(int arr[], vector<vector<int>> queries, int q, int n)
{

	// initialising array for Binary Indexed Tree
	int bit[n+1];
	memset(bit, 0, sizeof(bit));


	// sorting the array
	sort(arr, arr+n);


	// Add each query index in the queries vector, so that after sorting we can know the original index of the query
	for(int i=0; i<q; i++)
	{
		queries[i].push_back(i);
	}
      
	// sorting queries according to the increasing order of 'x' 
	sort(queries.begin(), queries.end(), sortByCol);


	// Variable to store the current index of array
	int curr = 0;


	// array to hold answer of each Query
	vector<int> ans(q);


	// Evaluate each query
	for (int i=0; i<q; i++)
	{

		// Traverse the array elements till it is less than equal to 'x' of the query
		while (arr[curr] <= queries[i][0] && curr<n)
		{
		
			// updating the bit array for the array index
			update(bit, curr+1, 1, n);
			curr++;
		}
        	
		/*
		store the answer for each query as the
		number of elements less than or equal to x 
		in [0, R] minus number of elements less than
		or equal to x in [0, L-1]
		*/
		ans[queries[i][3]] = query(bit, queries[i][2]+1, n) - query(bit, queries[i][1], n);
	}


   return ans;
}


// Main Function
int main()
{

	// Number of elements in the given array
	int n = 5;

	// Given array
	int arr[] = {2, 4, 3, 6, 9};

	// Number of queries
	int q = 3;

	// Given queries of the form {x, L, R}
	vector<vector<int>> queries= {{2, 0, 3},  {7, 0, 4}, {3, 0, 2}};


    /*
           Call the function to evaluate the queries
           to find the number of elements less than or equal to a 
           given number in a given subarray
    */
	vector<int> ans = evaluateQueries(arr, queries, q, n);

     // printing the he number of elements less than or equal to a given number in a given subarray for each query
	for (int i=0 ; i<q; i++)
	{
		cout << "Query "<<i+1<<": "<<ans[i] << endl;
	}


	return 0;
}

Output

Output:
Query 1: 1
Query 2: 4
Query 3: 2

Also read, Euclid GCD Algorithm

Algorithm Complexity: 

Time Complexity: O(Q * log(N))

In the function “evaluateQueries()” for evaluating the queries to find the number of elements less than or equal to a given number in a given subarray, “update()” and “query()” functions having time complexity of log(N), are called for each query. So, the overall time complexity is O(Q * log(N)), where ‘Q’ and 'N' are the number of queries and the number of elements in the array respectively.

Space Complexity: O(N) 

In the function “evaluateQueries()” for evaluating the queries to find the number of elements less than or equal to a given number in a given subarray, we have created a vector 'bit' for Binary indexed tree, so the space complexity is O(N), where 'N' is the number of elements in the given array.

Check out this problem - Count Inversions