I’ll first explain the concept of counting elements in a range, then discuss the elements involved, and finally provide a Java solution using an efficient approach.
Concept: Counting Elements in Range [a, b]
Given:
Goal
For each query, return the count of elements satisfying:
a ≤ x ≤ b
Naive Approach
Iterate over each query.
For each query, iterate through the array and count elements in the range [a, b].
Time Complexity
O(n × q)
This approach becomes too slow for large inputs where:
n, q ≤ 10^5
Efficient Approach
To optimize the solution, we can use sorting and binary search.
Step 1: Sort the Array
Sort arr[].
Sorting takes:
O(n log n)
Step 2: Process Each Query
For a query [a, b]:
Find the first index of an element greater than or equal to a (lower bound).
Find the first index of an element greater than b (upper bound).
Calculate:
Count = Upper Bound Index − Lower Bound Index
Since binary search is used for both operations, each query takes:
O(log n)
Total Time Complexity
O(n log n + q log n)
This is efficient and suitable for the given constraints.
Elements/Tools Used
Sorting – required to enable binary search.
Binary Search – used to find lower and upper bounds efficiently.
ArrayList – stores the answer for each query.
Looping through queries – processes all range queries.
Java Implementation
Here’s a clean solution using custom lower bound and upper bound methods:
import java.util.*;
class Solution {
public ArrayList<Integer> cntInRange(int[] arr, int[][] queries) {
Arrays.sort(arr); // Step 1: sort the array
ArrayList<Integer> result = new ArrayList<>();
for (int[] query : queries) {
int a = query[0];
int b = query[1];
// Find first index >= a
int left = lowerBound(arr, a);
// Find first index > b
int right = upperBound(arr, b);
result.add(right - left); // Count in range
}
return result;
}
// Custom lower bound (first index of element >= target)
private int lowerBound(int[] arr, int target) {
int low = 0, high = arr.length;
while (low < high) {
int mid = (low + high) / 2;
if (arr[mid] < target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
// Custom upper bound (first index of element > target)
private int upperBound(int[] arr, int target) {
int low = 0, high = arr.length;
while (low < high) {
int mid = (low + high) / 2;
if (arr[mid] <= target) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
How It Works
Input
arr = [1, 4, 2, 8, 5]
queries = [[1, 4], [3, 6], [0, 10]]
Step 1: Sort the Array
[1, 2, 4, 5, 8]
Query [1, 4]
lowerBound(1) → index 0
upperBound(4) → index 3
Count:
3 - 0 = 3
Elements in range:
[1, 2, 4]
Query [3, 6]
lowerBound(3) → index 2
upperBound(6) → index 4
Count:
4 - 2 = 2
Elements in range:
[4, 5]
Query [0, 10]
lowerBound(0) → index 0
upperBound(10) → index 5
Count:
5 - 0 = 5
Elements in range:
[1, 2, 4, 5, 8]
Complexity Analysis
Time Complexity
O(n log n + q log n)
Sorting the array takes O(n log n).
Each query is processed using two binary searches, each taking O(log n).
For q queries, the total query processing time is O(q log n).
Space Complexity
O(1)
Ignoring the output list, only a constant amount of extra space is used.
Key Insight
Instead of checking every element for every query, sort the array once and use binary search to locate the range boundaries. The difference between the upper bound and lower bound indices directly gives the number of elements within the required range, making the solution efficient even for very large inputs.
Summary
To count elements within multiple ranges efficiently, sort the array and use binary search to find the first element greater than or equal to the lower limit and the first element greater than the upper limit. The difference between these indices gives the count of elements in the range. This reduces the complexity from O(n × q) to O(n log n + q log n), making it suitable for large datasets.