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:

Code

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:

Code

arr = [1, 4, 2, 8, 5]

Query

Code

[1, 4]

Elements within the range:

Code

1, 2, 4

Count:

Code

Another Query

Code

[3, 6]

Elements within the range:

Code

4, 5

Count:

Code

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

Code

for every query:
    count = 0

    for every element:
        if a <= element <= b:
            count++

    answer.add(count)

Time Complexity

Code

O(n × q)

With:

Code

n = 100000
q = 100000

this becomes:

Code

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:

Code

arr = [1, 4, 2, 8, 5]

After sorting:

Code

[1, 2, 4, 5, 8]

For the query:

Code

[3, 6]

The valid elements:

Code

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:

Code

[a, b]

Find:

Code

left = first index having value ≥ a

and

Code

right = first index having value > b

Then:

Code

count = right - left

This works because all valid elements lie between these two positions.

Example

Sorted Array

Code

[1, 2, 4, 5, 8]

Query

Code

[3, 6]

Lower Bound of 3

Code

index = 2
value = 4

Upper Bound of 6

Code

index = 4
value = 8

Count

Code

4 - 2 = 2

Answer:

Code

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:

Code

O(log n)

time.

Algorithm

Sort the array.
For every query:
- Find the lower bound of a.
- Find the upper bound of b.
- Compute:

Code

count = upperBound - lowerBound

Store the result.

Java Solution

Java

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

Code

arr = [10, 20, 30, 40, 50]
queries = [[5,15], [25,45], [10,50]]

Sorted Array

Code

[10,20,30,40,50]

Query [5,15]

Lower Bound of 5:

Code

Upper Bound of 15:

Code

Count:

Code

1 - 0 = 1

Query [25,45]

Lower Bound:

Code

Upper Bound:

Code

Count:

Code

4 - 2 = 2

Query [10,50]

Lower Bound:

Code

Upper Bound:

Code

Count:

Code

5 - 0 = 5

Final Answer

Code

[1, 2, 5]

Complexity Analysis

Sorting

Code

O(n log n)

Query Processing

Each query requires two binary searches:

Code

O(log n)

For q queries:

Code

O(q log n)

Overall Time Complexity

Code

O(n log n + q log n)

Space Complexity

Code

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.