Count Elements Within a Range Using Sorting and Binary Search

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:

Another Query

[3, 6]

Elements within the range:

4, 5

Count:

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:

The first element greater than or equal to a
The first element greater than b

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:

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:
- Find the lower bound of a.
- Find the upper bound of b.
- Compute:

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:

Upper Bound of 15:

Count:

1 - 0 = 1

Query [25,45]

Lower Bound:

Upper Bound:

Count:

4 - 2 = 2

Query [10,50]

Lower Bound:

Upper Bound:

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.