medium Range Frequency Queries

Problem Statement

You are given an integer array nums[] and a list of queries queries[], where each query is defined as queries[i] = [left_i, right_i, value_i]. For each query, determine the frequency of value_i in the subarray of nums that starts at index left_i and ends at index right_i for each query.

Return an array answer[] where answer[i] is the result for the i^th query.

Examples

1. Example 1:

   • Input: nums = [2, 1, 2, 3, 2, 1, 3], queries = [[0, 4, 2], [2, 6, 3], [1, 5, 1]]
   • Expected Output: [3, 2, 2]
   • Justification:
     • In the first query, 2 appears 3 times in the subarray [2, 1, 2, 3, 2].
     • In the second query, 3 appears 2 times in the subarray [2, 3, 2, 1, 3].
     • In the third query, 1 appears 2 time in the subarray [1, 2, 3, 2, 1].

2. Example 2:

   • Input: nums = [4, 4, 4, 2, 4, 2, 2], queries = [[0, 2, 4], [3, 6, 2], [1, 4, 4]]
   • Expected Output: [3, 3, 3]
   • Justification:
     • In the first query, 4 appears 3 times in the subarray [4, 4, 4].
     • In the second query, 2 appears 3 times in the subarray [2, 4, 2, 2].
     • In the third query, 4 appears 3 times in the subarray [4, 4, 2, 4].

3. Example 3:

   • Input: nums = [5, 3, 5, 5, 3, 3, 5, 3, 5], queries = [[0, 8, 5], [1, 5, 3], [2, 7, 5]]
   • Expected Output: [5, 3, 3]
   • Justification:
     • In the first query, 5 appears 5 times in the subarray [5, 3, 5, 5, 3, 3, 5, 3, 5].
     • In the second query, 3 appears 3 times in the subarray [3, 5, 5, 3, 3].
     • In the third query, 5 appears 3 times in the subarray [5, 5, 3, 3, 5, 3].

Constraints:

• 1 <= arr.length <= 10⁵
• 1 <= arr[i], value <= 10⁴
• 0 <= left <= right < arr.length

Solution

To solve this problem efficiently, we can use Mo's algorithm, which is well-suited for answering range queries on static arrays. Mo's algorithm sorts queries in a way that minimizes the movement of the left and right pointers, thereby reducing the number of operations needed to adjust the frequency counts. The algorithm processes the queries in a specific order, based on their left and right bounds, and maintains a frequency array that keeps track of the occurrence of each element in the current subarray.

This approach is effective because it reduces the complexity of each query from potentially linear time to logarithmic time. By processing the queries in this way, we minimize the number of elements that need to be added or removed from the subarray, making the solution both time and space-efficient.

Step-by-Step Algorithm

1. Initialization:

   • Start by receiving the input array nums and the list of queries queries.
   • Determine the length of the nums array, denoted as n.
   • Initialize a frequency array frequency[] with a size 100001 to accommodate the range of values in nums.

2. Query Preparation:

   • For each query in queries, create an object (or structure) that contains the left index left, the right index right, the value to search value, and the index i of the query in the original list.
   • Store all these query objects in an array queryObjects[].

3. Sorting Queries:

   • Sort the queryObjects[] array using the following criteria:
     1. Primary Criterion: Sort by the block number of the left index. The block number is calculated by dividing the left index by the square root of n (the length of nums). This helps in minimizing the movement of the left pointer during query processing.
     2. Secondary Criterion: For queries that belong to the same block, sort by the right index. This ensures that the right pointer mostly moves in a single direction, further reducing the computational complexity.

4. Query Processing:

   • Initialize two pointers currentLeft and currentRight, both set to 0. These pointers will represent the current subarray that is being processed.
   • Initialize an array result[] to store the result of each query, with the same length as queries.

5. Processing Each Query:

   • For each query in the sorted queryObjects[]:
     1. Adjust Right Pointer:
        • Expansion: While currentRight is less than or equal to query.right, increase frequency[nums[currentRight]] by 1, and then increment currentRight. This step adds elements to the current subarray and updates their frequency.
        • Shrinkage: While currentRight is greater than query.right + 1, decrement currentRight and decrease frequency[nums[currentRight]] by 1. This step removes elements from the current subarray that are no longer part of the required range.
     2. Adjust Left Pointer:
        • Expansion: While currentLeft is less than query.left, decrease frequency[nums[currentLeft]] by 1, and then increment currentLeft. This step removes elements from the left side of the subarray that are no longer part of the required range.
        • Shrinkage: While currentLeft is greater than query.left, decrement currentLeft and increase frequency[nums[currentLeft]] by 1. This step adds elements to the left side of the subarray.
     3. Record the Result:
        • The frequency of query.value in the current subarray is now stored in frequency[query.value]. Assign this value to result[query.index].

6. Return the Result:

   • After all queries have been processed, return the result[] array, which contains the frequency counts for each query.

Algorithm Walkthrough

Given:

• nums = [2, 1, 2, 3, 2, 1, 3]
• queries = [[0, 4, 2], [2, 6, 3], [1, 5, 1]]

Step 1: Initialization

• n = 7 (length of nums)
• frequency[] = [0] * 100001

Step 2: Query Preparation

• Create query objects:
  • query1: left=0, right=4, value=2, index=0
  • query2: left=2, right=6, value=3, index=1
  • query3: left=1, right=5, value=1, index=2
• Store them in queryObjects[].

Step 3: Sorting Queries

• Block size sqrt(n) = sqrt(7) ≈ 2.65. We round down to 2 for block calculations.
• Sort queries:
  • All queries fall in block 0 or block 1.
  • After sorting by the block and right index, the order is:
    • query1 (block 0)
    • query3 (block 0)
    • query2 (block 1)

Step 4: Query Processing Initialization

• currentLeft = 0
• currentRight = 0
• result[] = [0, 0, 0]

Step 5: Processing Each Query

Processing query1: left=0, right=4, value=2

• Adjust Right Pointer:
  • Expand currentRight:
    • frequency[2] = 1 at currentRight=0
    • frequency[1] = 1 at currentRight=1
    • frequency[2] = 2 at currentRight=2
    • frequency[3] = 1 at currentRight=3
    • frequency[2] = 3 at currentRight=4
• The subarray is [2, 1, 2, 3, 2].
• Adjust Left Pointer:
  • No adjustments needed, currentLeft is already at query.left.
• Store the Result:
  • result[0] = frequency[2] = 3

Processing query3: left=1, right=5, value=1

• Adjust Right Pointer:
  • Expand currentRight:
    • frequency[1] = 2 at currentRight=5
• The subarray is [1, 2, 3, 2, 1].
• Adjust Left Pointer:
  • Expand currentLeft:
    • Decrease frequency[2] to 2. currentLeft=1
• The subarray is now [1, 2, 3, 2, 1] from currentLeft=1 to currentRight=5.
• Store the Result:
  • result[2] = frequency[1] = 2

Processing query2: left=2, right=6, value=3

• Adjust Right Pointer:
  • Expand currentRight:
    • frequency[3] = 2 at currentRight=6
• The subarray is [2, 3, 2, 1, 3].
• Adjust Left Pointer:
  • Expand currentLeft:
    • Decrease frequency[1] to 1. currentLeft=2
• The subarray is [2, 3, 2, 1, 3] from currentLeft=2 to currentRight=6.
• Store the Result:
  • result[1] = frequency[3] = 2

Step 6: Return the Result

• The final result[] = [3, 2, 2].

Code

import java.util.Arrays;

class Solution {
    private int[] nums;
    private int[] frequency;

    public int[] rangeFrequencyQueries(int[] nums, int[][] queries) {
        this.nums = nums;
        int n = nums.length;
        frequency = new int[100001]; // assuming nums[i] is <= 100000
        Query[] queryObjects = new Query[queries.length];

        // Prepare the queries for Mo's algorithm
        for (int i = 0; i < queries.length; i++) {
            queryObjects[i] = new Query(queries[i][0], queries[i][1], queries[i][2], i);
        }

        // Sort the queries
        Arrays.sort(queryObjects, (q1, q2) -> {
            int block1 = q1.left / (int) Math.sqrt(n);
            int block2 = q2.left / (int) Math.sqrt(n);
            if (block1 != block2) {
                return block1 - block2;
            }
            return q1.right - q2.right;
        });

        int[] result = new int[queries.length];
        int currentLeft = 0, currentRight = 0;
        for (Query query : queryObjects) {
            // Adjust right boundary
            while (currentRight <= query.right) frequency[nums[currentRight++]]++;
            while (currentRight > query.right + 1) frequency[nums[--currentRight]]--;

            // Adjust left boundary
            while (currentLeft < query.left) frequency[nums[currentLeft++]]--;
            while (currentLeft > query.left) frequency[nums[--currentLeft]]++;

            // Store the result for this query
            result[query.index] = frequency[query.value];
        }

        return result;
    }

    private class Query {
        int left, right, value, index;
        Query(int left, int right, int value, int index) {
            this.left = left;
            this.right = right;
            this.value = value;
            this.index = index;
        }
    }

    // Main method for testing the examples
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Example 1
        int[] nums1 = {2, 1, 2, 3, 2, 1, 3};
        int[][] queries1 = {{0, 4, 2}, {2, 6, 3}, {1, 5, 1}};
        int[] result1 = solution.rangeFrequencyQueries(nums1, queries1);
        System.out.println(Arrays.toString(result1)); // Output: [3, 2, 2]

        // Example 2
        int[] nums2 = {4, 4, 4, 2, 4, 2, 2};
        int[][] queries2 = {{0, 2, 4}, {3, 6, 2}, {1, 4, 4}};
        int[] result2 = solution.rangeFrequencyQueries(nums2, queries2);
        System.out.println(Arrays.toString(result2)); // Output: [3, 3, 3]

        // Example 3
        int[] nums3 = {5, 3, 5, 5, 3, 3, 5, 3, 5};
        int[][] queries3 = {{0, 8, 5}, {1, 5, 3}, {2, 7, 5}};
        int[] result3 = solution.rangeFrequencyQueries(nums3, queries3);
        System.out.println(Arrays.toString(result3)); // Output: [5, 3, 3]
    }
}

Complexity Analysis

Time Complexity

The overall time complexity is , according to Mo's algorithm.

Space Complexity

• The primary space usage is the freq array, which is of size , i.e., in this case. Additionally, we use space for storing the results (O(q)), and the queries themselves, which is .

Thus, the space complexity is , which simplifies to assuming a constant maximum element value.