Element Count in Ranges

Easy

0/40

0 upvote

Asked in company

Problem statement

You are given an array of integers, arr, and a series of Q queries. Each query is defined by an inclusive range [low, high].

For each query, your task is to determine the total number of elements in the original array arr that fall within that specific range. That is, for a given [low, high], you need to count how many elements x in arr satisfy low <= x <= high.

You must return a list of answers, where the i-th element is the count corresponding to the i-th query.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer N, the size of the array arr.

The second line contains N space-separated integers, the elements of arr.

The third line contains a single integer Q, the number of queries.

The next Q lines each contain two space-separated integers, low and high, representing a query range.

Output Format:

Print Q lines, where each line contains a single integer representing the answer to the corresponding query.

Note:

A naive approach of iterating through the entire array for each query might be too slow and result in a "Time Limit Exceeded" error. Sorting the array first allows for a much more efficient method (like binary search) to find the counts for each range.

Sample Input 1:

Sample Output 1:

3
4

Explanation for Sample 1:

Query 1 [0, 2]: The elements from arr in this range are {1, 2, 2}. The count is 3.
Query 2 [2, 4]: The elements from arr in this range are {2, 2, 3, 4}. The count is 4.

Expected Time Complexity:

The expected time complexity is O(NLogQ).

Constraints:

1 <= N, Q <= 10^5
-10^9 <= arr[i], low, high <= 10^9

Time Limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Element Count in Ranges

Console