Given an unsorted array and multiple range queries, the task is to determine how many elements lie within each range [a, b].
For every query:
a ≤ x ≤ b
we need to count all elements satisfying the condition.
The challenge is that both the number of array elements and queries can be as large as 10^5, making brute-force approaches inefficient.
Understanding the Problem
Consider:
arr = [1, 4, 2, 8, 5]
Query
[1, 4]
Elements within the range:
1, 2, 4
Count:
3
Another Query
[3, 6]
Elements within the range:
4, 5
Count:
2
Our goal is to answer many such queries efficiently.
Brute Force Approach
For every query:
Traverse the entire array.
Check whether each element lies between a and b.
Increment the count if it does.
Pseudo-code
for every query:
count = 0
for every element:
if a <= element <= b:
count++
answer.add(count)
Time Complexity
O(n × q)
With:
n = 100000
q = 100000
this becomes:
10^10 operations
which is far too slow.
Key Observation
We only need the count of numbers within a range.
If the array is sorted, all numbers within a range become contiguous.
Example
Original array:
arr = [1, 4, 2, 8, 5]
After sorting:
[1, 2, 4, 5, 8]
For the query:
[3, 6]
The valid elements:
4, 5
appear together.
Therefore, instead of scanning the entire array, we can locate:
using binary search.
The difference between these positions gives the count.
Using Lower Bound and Upper Bound
For a query:
[a, b]
Find:
left = first index having value ≥ a
and
right = first index having value > b
Then:
count = right - left
This works because all valid elements lie between these two positions.
Example
Sorted Array
[1, 2, 4, 5, 8]
Query
[3, 6]
Lower Bound of 3
index = 2
value = 4
Upper Bound of 6
index = 4
value = 8
Count
4 - 2 = 2
Answer:
2
Why Binary Search Works
Since the array is sorted:
Elements before the lower bound are too small.
Elements after the upper bound are too large.
Every valid element lies in between.
Binary search finds these boundaries in:
O(log n)
time.
Algorithm
Sort the array.
For every query:
count = upperBound - lowerBound
Store the result.
Java Solution
import java.util.*;
class Solution {
public ArrayList<Integer> cntInRange(int[] arr, int[][] queries) {
Arrays.sort(arr);
ArrayList<Integer> ans = new ArrayList<>();
for (int[] q : queries) {
int a = q[0];
int b = q[1];
int left = lowerBound(arr, a);
int right = upperBound(arr, b);
ans.add(right - left);
}
return ans;
}
private int lowerBound(int[] arr, int target) {
int low = 0;
int high = arr.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] < target)
low = mid + 1;
else
high = mid;
}
return low;
}
private int upperBound(int[] arr, int target) {
int low = 0;
int high = arr.length;
while (low < high) {
int mid = low + (high - low) / 2;
if (arr[mid] <= target)
low = mid + 1;
else
high = mid;
}
return low;
}
}
Dry Run
Input
arr = [10, 20, 30, 40, 50]
queries = [[5,15], [25,45], [10,50]]
Sorted Array
[10,20,30,40,50]
Query [5,15]
Lower Bound of 5:
0
Upper Bound of 15:
1
Count:
1 - 0 = 1
Query [25,45]
Lower Bound:
2
Upper Bound:
4
Count:
4 - 2 = 2
Query [10,50]
Lower Bound:
0
Upper Bound:
5
Count:
5 - 0 = 5
Final Answer
[1, 2, 5]
Complexity Analysis
Sorting
O(n log n)
Query Processing
Each query requires two binary searches:
O(log n)
For q queries:
O(q log n)
Overall Time Complexity
O(n log n + q log n)
Space Complexity
O(1)
excluding the output list.
Why This Approach Is Efficient
Sorting transforms the problem from repeated scanning into a search problem. Once the array is sorted, all values belonging to a query range become contiguous. Binary search can then quickly locate the start and end positions of those values, allowing each query to be answered in logarithmic time instead of linear time.
Key Insight
The main observation is that counting elements in a range becomes much easier after sorting. Once the array is sorted, binary search can instantly locate the start and end positions of valid elements. Instead of scanning every element for every query, we answer each query in logarithmic time by finding the lower and upper boundaries of the range.
Summary
To efficiently count elements within multiple ranges, first sort the array and then use binary search to find the lower bound of the range start and the upper bound of the range end. The difference between these two positions directly gives the number of elements in the range. This reduces the overall complexity from O(n × q) to O(n log n + q log n), making it suitable for large inputs.