Range-Based Count of X in Sorted Array

Last Updated : 1 Aug, 2025

Given a sorted array arr[] and a list of queries represented as a 2D array queries[][]. Each query is a triplet of the form [l, r, x], where l and r are indices in the array, and x is the value to search for.
For each query, find how many times the number x appears in the subarray arr[l...r] (inclusive).

Examples:

Input: arr[] = [1, 2, 2, 4, 5, 5, 5, 8], queries[][] = [[0, 7, 5], [1, 2, 2], [0, 3, 7]]
Output: [3, 2, 0]
Explanation:
Query [0, 7, 5] → elements from index 0 to 7 are [1, 2, 2, 4, 5, 5, 5, 8]. Number 5 occurs 3 times.
Query [1, 2, 2] → subarray is [2, 2], and 2 occurs 2 times.
Query [0, 3, 7] → subarray is [1, 2, 2, 4], and 7 is not present → 0.

Input: arr[] = [1, 3, 3, 3, 6, 7, 8], queries[][] = [[0, 3, 3], [4, 6, 3], [1, 5, 6]]
Output: [3, 0, 1]
Explanation:
Query [0, 3, 3] → subarray [1, 3, 3, 3], and 3 appears 3 times.
Query [4, 6, 3] → subarray [6, 7, 8], 3 not found → 0.
Query [1, 5, 6] → subarray [3, 3, 3, 6, 7], and 6 occurs 1 time.

Try it on GfG Practice
redirect icon

Table of Content

[Naive Approach] Naive Linear Scan - O(q × n) Time and O(1) Space

For each query, iterate through the subarray from index l to r, and count how many times x appears.

C++ 
#include <iostream>
#include <vector>
using namespace std;

vector<int> countXInRange(vector<int>& arr, 
                    vector<vector<int>>& queries) {
    vector<int> result;

    for (auto& query : queries) {
        int l = query[0];
        int r = query[1];
        int x = query[2];
        int count = 0;

        // check every index from l to r
        for (int i = l; i <= r; i++) {
            if (arr[i] == x)
                count++;
        }

        result.push_back(count);
    }

    return result;
}

int main() {
    vector<int> arr = {1, 2, 2, 4, 5, 5, 5, 8};
    vector<vector<int>> queries = {
        {0, 7, 5},
        {1, 2, 2},
        {0, 3, 7}
    };

    vector<int> res = countXInRange(arr, queries);
    for (int count : res)
        cout << count << " ";
    cout << endl;

    return 0;
}
Java 
import java.util.ArrayList;

class GfG {
    public static ArrayList<Integer> 
            countXInRange(int[] arr, int[][] queries) {
                
        ArrayList<Integer> result = new ArrayList<>();

        for (int[] query : queries) {
            int l = query[0];
            int r = query[1];
            int x = query[2];
            int count = 0;

            // check every index from l to r
            for (int i = l; i <= r; i++) {
                if (arr[i] == x)
                    count++;
            }

            result.add(count);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 4, 5, 5, 5, 8};
        int[][] queries = {
            {0, 7, 5},
            {1, 2, 2},
            {0, 3, 7}
        };

        ArrayList<Integer> res = countXInRange(arr, queries);
        for (int count : res)
            System.out.print(count + " ");
        System.out.println();
    }
}
Python 
def countXInRange(arr, queries):
    result = []

    for query in queries:
        l, r, x = query
        count = 0

        # check every index from l to r
        for i in range(l, r + 1):
            if arr[i] == x:
                count += 1

        result.append(count)

    return result
    

if __name__ == "__main__":
    arr = [1, 2, 2, 4, 5, 5, 5, 8]
    queries = [
        [0, 7, 5],
        [1, 2, 2],
        [0, 3, 7]
    ]

    res = countXInRange(arr, queries)
    for count in res:
        print(count, end=" ")
    print()
C# 
using System;
using System.Collections.Generic;

class GfG {
    public static List<int> 
                countXInRange(int[] arr, int[][] queries) {
                    
        List<int> result = new List<int>();

        foreach (int[] query in queries) {
            int l = query[0];
            int r = query[1];
            int x = query[2];
            int count = 0;

            // check every index from l to r
            for (int i = l; i <= r; i++) {
                if (arr[i] == x)
                    count++;
            }

            result.Add(count);
        }

        return result;
    }

    static void Main() {
        int[] arr = {1, 2, 2, 4, 5, 5, 5, 8};
        int[][] queries = {
            new int[] {0, 7, 5},
            new int[] {1, 2, 2},
            new int[] {0, 3, 7}
        };

        List<int> res = countXInRange(arr, queries);
        foreach (int count in res)
            Console.Write(count + " ");
        Console.WriteLine();
    }
}
JavaScript 
function countXInRange(arr, queries) {
    const result = [];

    for (const query of queries) {
        const l = query[0];
        const r = query[1];
        const x = query[2];
        let count = 0;

        // check every index from l to r
        for (let i = l; i <= r; i++) {
            if (arr[i] === x)
                count++;
        }

        result.push(count);
    }

    return result;
}

// Driver Code
const arr = [1, 2, 2, 4, 5, 5, 5, 8];
const queries = [
    [0, 7, 5],
    [1, 2, 2],
    [0, 3, 7]
];

const res = countXInRange(arr, queries);
console.log(res.join(" "));

Output
3 2 0

[Expected Approach] Using Binary Search

The idea is to use binary search (lower_bound and upper_bound) to find the first and last positions where the element x appears in the sorted array. Once we know all the positions where x occurs, we simply check how many of those lie within the given index range [l, r]. If there's no overlap between the index range of occurrences and the query's [l, r], we return 0. Otherwise, we return the number of overlapping positions, which is right - left + 1.

Step by Step Implementation:

  • For each query [l, r, x], extract l, r, and x.
  • Use lower_bound to find the first index where x could appear.
  • If x doesn't exist in the array, directly store 0 as the answer for this query.
  • Use upper_bound to find the first index where the value becomes greater than x; subtract 1 to get the last index of x.
  • Clamp the range of x's occurrences to within [l, r] using max(left, l) and min(right, r).
  • If the clamped range is valid (left ≤ right), count the occurrences as right - left + 1.
  • Otherwise, store 0 for this query.
C++ 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> countXInRange(vector<int>& arr, 
                         vector<vector<int>>& queries) {
                             
    vector<int> result;
    int n = arr.size();

    for (auto& query : queries) {
        int l = query[0];
        int r = query[1];
        int x = query[2];

        // find first index where arr[i] == x
        int left = lower_bound(arr.begin(), arr.end(), x)
                   - arr.begin();

        // if x is not present at all
        if (left == n || arr[left] != x) {
            result.push_back(0);
            continue;
        }

        // find first index where arr[i] > x
        int right = upper_bound(arr.begin(), arr.end(), x)
                    - arr.begin();
                    
        // last index where arr[i] == x
        right--; 

        // clip the indices to [l, r]
        left = max(left, l);
        right = min(right, r);

        // if no overlap
        if (left > right)
            result.push_back(0);
        else
            result.push_back(right - left + 1);
    }

    return result;
}

int main() {
    vector<int> arr = {1, 2, 2, 4, 5, 5, 5, 8};
    vector<vector<int>> queries = {
        {0, 7, 5},
        {1, 2, 2},
        {0, 3, 7}
    };

    vector<int> res = countXInRange(arr, queries);
    for (int count : res)
        cout << count << " ";
    cout << endl;

    return 0;
}
Java 
import java.util.*;

class GfG {
    public static ArrayList<Integer> 
                countXInRange(int[] arr, int[][] queries) {
                    
        ArrayList<Integer> result = new ArrayList<>();
        int n = arr.length;

        for (int[] query : queries) {
            int l = query[0];
            int r = query[1];
            int x = query[2];

            // find first index where arr[i] == x
            int left = lowerBound(arr, x);

            // if x is not present at all
            if (left == n || arr[left] != x) {
                result.add(0);
                continue;
            }

            // find first index where arr[i] > x
            int right = upperBound(arr, x);

            // last index where arr[i] == x
            right--;

            // clip the indices to [l, r]
            left = Math.max(left, l);
            right = Math.min(right, r);

            // if no overlap
            if (left > right)
                result.add(0);
            else
                result.add(right - left + 1);
        }

        return result;
    }

    // lower_bound implementation
    private static int lowerBound(int[] arr, int x) {
        int low = 0, high = arr.length;
        while (low < high) {
            int mid = (low + high) / 2;
            if (arr[mid] < x) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    // upper_bound implementation
    private static int upperBound(int[] arr, int x) {
        int low = 0, high = arr.length;
        while (low < high) {
            int mid = (low + high) / 2;
            if (arr[mid] <= x) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 4, 5, 5, 5, 8};
        int[][] queries = {
            {0, 7, 5},
            {1, 2, 2},
            {0, 3, 7}
        };

        ArrayList<Integer> res = countXInRange(arr, queries);
        for (int count : res)
            System.out.print(count + " ");
        System.out.println();
    }
}
Python 
import bisect

def countXInRange(arr, queries):
    result = []
    n = len(arr)

    for query in queries:
        l, r, x = query

        # find first index where arr[i] == x
        left = bisect.bisect_left(arr, x)

        # if x is not present at all
        if left == n or arr[left] != x:
            result.append(0)
            continue

        # find first index where arr[i] > x
        right = bisect.bisect_right(arr, x)
        right -= 1  # last index where arr[i] == x

        # clip the indices to [l, r]
        left = max(left, l)
        right = min(right, r)

        # if no overlap
        if left > right:
            result.append(0)
        else:
            result.append(right - left + 1)

    return result

if __name__ == "__main__":
    arr = [1, 2, 2, 4, 5, 5, 5, 8]
    queries = [
        [0, 7, 5],
        [1, 2, 2],
        [0, 3, 7]
    ]

    res = countXInRange(arr, queries)
    print(' '.join(map(str, res)))
C# 
using System;
using System.Collections.Generic;

class GfG {
    public static List<int>
            countXInRange(int[] arr, int[][] queries) {
                
        List<int> result = new List<int>();
        int n = arr.Length;

        foreach (var query in queries) {
            int l = query[0];
            int r = query[1];
            int x = query[2];

            // find first index where arr[i] == x
            int left = LowerBound(arr, x);

            // if x is not present at all
            if (left == n || arr[left] != x) {
                result.Add(0);
                continue;
            }

            // find first index where arr[i] > x
            int right = UpperBound(arr, x);
            right--; // last index where arr[i] == x

            // clip the indices to [l, r]
            left = Math.Max(left, l);
            right = Math.Min(right, r);

            // if no overlap
            if (left > right)
                result.Add(0);
            else
                result.Add(right - left + 1);
        }

        return result;
    }

    private static int LowerBound(int[] arr, int x) {
        int low = 0, high = arr.Length;
        while (low < high) {
            int mid = (low + high) / 2;
            if (arr[mid] < x) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    private static int UpperBound(int[] arr, int x) {
        int low = 0, high = arr.Length;
        while (low < high) {
            int mid = (low + high) / 2;
            if (arr[mid] <= x) low = mid + 1;
            else high = mid;
        }
        return low;
    }

    public static void Main(string[] args) {
        int[] arr = {1, 2, 2, 4, 5, 5, 5, 8};
        int[][] queries = new int[][] {
            new int[] {0, 7, 5},
            new int[] {1, 2, 2},
            new int[] {0, 3, 7}
        };

        List<int> res = countXInRange(arr, queries);
        Console.WriteLine(string.Join(" ", res));
    }
}
JavaScript 
function countXInRange(arr, queries) {
    let result = [];

    for (let query of queries) {
        let [l, r, x] = query;

        // find first index where arr[i] == x
        let left = lowerBound(arr, x);

        // if x is not present at all
        if (left === arr.length || arr[left] !== x){
            result.push(0);
            continue;
        }

        // find first index where arr[i] > x
        let right = upperBound(arr, x);
        right--; // last index where arr[i] == x

        // clip the indices to [l, r]
        left = Math.max(left, l);
        right = Math.min(right, r);

        // if no overlap
        if (left > right)
            result.push(0);
        else
            result.push(right - left + 1);
    }

    return result;
}

// lower_bound for sorted array
function lowerBound(arr, x) {
    let low = 0, high = arr.length;
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (arr[mid] < x) low = mid + 1;
        else high = mid;
    }
    return low;
}

// upper_bound for sorted array
function upperBound(arr, x) {
    let low = 0, high = arr.length;
    while (low < high) {
        let mid = Math.floor((low + high) / 2);
        if (arr[mid] <= x) low = mid + 1;
        else high = mid;
    }
    return low;
}

// Driver Code
let arr = [1, 2, 2, 4, 5, 5, 5, 8];
let queries = [
    [0, 7, 5],
    [1, 2, 2],
    [0, 3, 7]
];

let res = countXInRange(arr, queries);
console.log(res.join(" "));

Output
3 2 0

Time Complexity: O(q × log n), for each of the q queries, we perform two binary searches (lower_bound and upper_bound) on the sorted array of size n.
Auxiliary Space : O(1)

Comment
Article Tags:
DSA

Explore