Count Elements in a Given Range Using Sorting and Binary Search

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:

An unsorted array arr[].
A list of queries queries[][], where each query [a, b] asks: how many elements in arr lie between a and b inclusive?

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.