Elements in range [a, b]

JavaView on GFG

Time: O(n)

Space: O(h)

Intuition

Count or find elements in a sorted array within range [a, b]. Binary search for lower and upper bounds.

Algorithm

1lower = lower_bound(a), upper = upper_bound(b). Count = upper - lower.

Common Pitfalls

•Two binary searches. Same as LC 34 extended to a range. O(log n).

Elements in range [a, b].java

Java

// Approach: Traverse BST. Collect all nodes with values in [a, b] using in-order traversal.
// Time: O(n) Space: O(h)
import java.util.*;

class Solution {
    public ArrayList<Integer> cntInRange(int[] arr, int[][] queries) {
        Arrays.sort(arr);
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < queries.length; i++) {
            int s = queries[i][0];
            int e = queries[i][1];
            result.add(bisectRight(arr, e) - bisectLeft(arr, s));
        }
        
        return result;
    }

    private int bisectLeft(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;
    }

    private int bisectRight(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;
    }
}

Was this solution helpful?