Number of elements greater than K in the range L to R

Problem

Given an array of N integers, and a number of queries. Each query is represented by three integers: l (the starting index), r (the ending index, inclusive), and k. The task is to calculate how many elements in the subarray [l, r] (inclusive) are greater than k. Solve this efficiently for multiple queries.

Examples

Example 1

Input: array = [1, 4, 2, 6, 8], queries = [(1, 3, 3), (0, 4, 5)]
Output: [2, 2]
Explanation: 
For (1, 3, 3): The subarray is [4, 2, 6]. Elements greater than 3: [4, 6], count = 2.
For (0, 4, 5): The subarray is [1, 4, 2, 6, 8]. Elements greater than 5: [6, 8], count = 2.

Example 2

Input:  array = [10, 20, 30, 40], queries = [(0, 2, 15), (1, 3, 25)]
Output: [2, 1]
Explanation: 
For (0, 2, 15): Subarray is [10, 20, 30]. Elements greater than 15: [20, 30], count = 2.
For (1, 3, 25): Subarray is [20, 30, 40]. Elements greater than 25: [30, 40], count = 1.

Solution

Method 1 - Naive

This can be the naive approach:

1. Parse the array and the list of queries.
2. For each query (l, r, k):
   • Extract the subarray [l, r] from the main array.
   • Count the number of elements in the subarray greater than k.
3. Return the count for each query.

Code

Java

public class Solution {
    public List<Integer> countGreaterThanK(int[] arr, int[][] queries) {
        List<Integer> result = new ArrayList<>();
        
        // Process each query
        for (int[] query : queries) {
            int l = query[0];
            int r = query[1];
            int k = query[2];
            
            int count = 0;
            // Iterate over subarray [l, r]
            for (int i = l; i <= r; i++) {
                if (arr[i] > k) {
                    count++;
                }
            }
            result.add(count);
        }
        
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        
        int[] arr = {1, 4, 2, 6, 8};
        int[][] queries = {
            {1, 3, 3},
            {0, 4, 5}
        };
        
        // Output the results for the queries
        System.out.println(sol.countGreaterThanK(arr, queries)); // Output: [2, 2]
    }
}

Python

class Solution:
    def countGreaterThanK(self, arr, queries):
        result = []
        for l, r, k in queries:
            count = 0
            # Iterate over the subarray [l, r]
            for i in range(l, r + 1):
                if arr[i] > k:
                    count += 1
            result.append(count)
        return result

# Example usage:
arr = [1, 4, 2, 6, 8]
queries = [(1, 3, 3), (0, 4, 5)]  # List of queries
sol = Solution()
output = sol.countGreaterThanK(arr, queries)
print(output)  # Output: [2, 2]

Complexity

• ⏰ Time complexity: O(N * Q) for iterating over subarray for each query.
• 🧺 Space complexity:  O(1) (no extra memory used apart from input).

Method 2 - Using Fenwick Tree

Using a Fenwick Tree (also known as a Binary Indexed Tree or BIT) is a powerful technique for solving range queries efficiently, especially when preprocessing helps achieve better performance than direct iteration. Below is the solution using Fenwick Tree.

Approach

The Fenwick Tree enables us to maintain and query frequencies across ranges efficiently. Here's how we adapt the problem:

1. Preprocessing: Create a Fenwick Tree to maintain a frequency count of numbers in the array. For each number x in the array, we store its frequency in the Fenwick Tree (indexed at x or adjusted for range if numbers aren't naturally bounded).

2. Answering Queries: For each query (l, r, k), we:

   • Query the cumulative frequency range for numbers greater than k within indices [l, r] by adjusting the Fenwick Tree structure.

This approach makes it possible to preprocess and answer range-based queries in logarithmic time for both updates and queries.

Preparation for Fenwick Tree

1. Coordinate compression (if needed): Fenwick Tree indices depend on naturally bounded values. If array values are large or sparse, coordinate compression maps array values to smaller integer ranges.

2. Fenwick Tree constructs a 1D structure to process range sums.

Code

Java

class FenwickTree {
    private int size;
    private int[] tree;

    // Constructor to initialise Fenwick Tree
    public FenwickTree(int size) {
        this.size = size;
        this.tree = new int[size + 1]; // Fenwick Tree indices are 1-based
    }

    // Update the frequency of a number at 'index' by 'value'
    public void update(int index, int value) {
        while (index <= size) {
            tree[index] += value;
            index += index & -index; // Move to the next index
        }
    }

    // Query cumulative frequency up to 'index'
    public int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index; // Move to the parent node
        }
        return sum;
    }

    // Query range [left, right]
    public int rangeQuery(int left, int right) {
        return query(right) - query(left - 1);
    }
}

public class Solution {
    public List<Integer> countGreaterThanK(int[] arr, int[][] queries) {
        // Step 1: Coordinate compression
        TreeSet<Integer> uniqueVals = new TreeSet<>();
        for (int val : arr) {
            uniqueVals.add(val);
        }
        List<Integer> sortedVals = new ArrayList<>(uniqueVals);
        Map<Integer, Integer> mapping = new HashMap<>();
        for (int i = 0; i < sortedVals.size(); i++) {
            mapping.put(sortedVals.get(i), i + 1); // Map values to compressed indices (1-based)
        }

        // Step 2: Initialize Fenwick Tree
        int maxIndex = sortedVals.size();
        FenwickTree fenwick = new FenwickTree(maxIndex);

        // Step 3: Populate Fenwick Tree with array values
        for (int val : arr) {
            int compressedIndex = mapping.get(val);
            fenwick.update(compressedIndex, 1); // Add frequency for the number
        }

        // Step 4: Process each query
        List<Integer> result = new ArrayList<>();
        for (int[] query : queries) {
            int l = query[0];
            int r = query[1];
            int k = query[2];

            int count = 0;
            // Find compressed index for K
            Integer kCompressed = mapping.get(k);

            // Query for range: All values greater than k
            if (kCompressed != null) {
                count = fenwick.query(maxIndex) - fenwick.query(kCompressed);
            }

            result.add(count);
        }

        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr = {1, 4, 2, 6, 8};
        int[][] queries = {
            {1, 3, 3},
            {0, 4, 5}
        };
        
        // Output the results for queries
        System.out.println(sol.countGreaterThanK(arr, queries)); // Output: [2, 2]
    }
}

Python

class FenwickTree:
    def __init__(self, size):
        # Fenwick Tree size is based on the maximum value of the array
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index, value):
        # Update the frequency of 'index' by 'value'
        while index <= self.size:
            self.tree[index] += value
            index += index & -index

    def query(self, index):
        # Get the cumulative frequency up to 'index'
        sum = 0
        while index > 0:
            sum += self.tree[index]
            index -= index & -index
        return sum

    def range_query(self, left, right):
        # Query the cumulative frequency in range [left, right]
        return self.query(right) - self.query(left - 1)

class Solution:
    def countGreaterThanK(self, arr, queries):
        # Step 1: Coordinate compression for large values
        sorted_vals = sorted(set(arr))  # Unique sorted values
        mapping = {val: idx + 1 for idx, val in enumerate(sorted_vals)}  # Map values to indices
        
        # Step 2: Initialize Fenwick Tree
        max_index = len(sorted_vals)  # Size of compressed value range
        fenwick = FenwickTree(size=max_index)

        # Step 3: Populate Fenwick Tree with array values
        for val in arr:
            compressed_val = mapping[val]
            fenwick.update(compressed_val, 1)  # Add frequency of the number in Fenwick Tree

        # Step 4: Process each query
        result = []
        for l, r, k in queries:
            # Find bounds in the compressed range for querying
            left = l + 1   # Convert 0-based to 1-based for coordinates
            right = r + 1  # Convert 0-based to 1-based for coordinates
            
            # Start query with numbers greater than K;
            count = 0
            # Find the index in the compressed range for k
            # If K is greater than all array values, count will be 0
            if k in mapping:
                k_compressed = mapping[k]
            else:
                count = 0
                result.append(count)
                continue
            
            # Query for range: all values greater than `k`
            count = fenwick.query(max_index) - fenwick.query(k_compressed)
            result.append(count)

        return result

# Example usage
arr = [1, 4, 2, 6, 8]
queries = [(1, 3, 3), (0, 4, 5)]

sol = Solution()
output = sol.countGreaterThanK(arr, queries)
print(output)  # Output: [2, 2]

Complexity

• ⏰ Time complexity: O(n log(max))
  • Fenwick Tree Updates (Preprocessing): O(N log(Max))
  • Fenwick Tree Queries: O(Q log(Max)), where Max is the maximum value in the array.
• 🧺 Space complexity: O(max), for Fenwick Tree storage.