Querying frequency of elements in a range
Given an array of N elements and num queries, In each query, you are given three numbers L, R, and K and you have to tell, how many indices are there in between L and R (L ≤ i ≤ R) such that the frequency of a[i] from index i to n-1 is K.
Examples:
Input: N = 5, num = 3, A = {1, 1, 3, 4, 3}, Q = {{0, 2, 2}, {0, 2, 1}, {0, 4, 2}}
Output: 2 1 2
Explanation: For query 1: L = 0, R = 2, K = 2, let L ≤ i ≤ R
- For i = 0: frequency of a[i] i.e. 1 from i to n-1 is 2.
- For i = 1: frequency of a[i] i.e. 1 from i to n-1 is 1.
- For i = 2: frequency of a[i] i.e. 3 from i to n-1 is 2.
- Hence we have two elements from index 0 to 2 whose frequency from i to n-1 is 2.
For query 2: L = 0, R = 2, K = 1
As we can see from the above query that there is only a single element in 0 to 2 whose frequency from i to n-1 is 1.For query 3: L = 0, R = 4, K = 2
The answer will be 2 because of the index 0 and 2.Input: N = 5, num = 2, A = {1, 1, 1, 1, 1}, Q = {{0, 4, 2}, {0, 4, 1}}
Output: 1 1
Explanation: For query 1: L = 0, R = 4, K = 4, let L ≤ i ≤ R
- For i = 0: frequency of a[i] i.e. 1 from i to n-1 is 5.
- For i = 1: frequency of a[i] i.e. 1 from i to n-1 is 4.
- For i = 2: frequency of a[i] i.e. 1 from i to n-1 is 3.
- For i = 3: frequency of a[i] i.e. 1 from i to n-1 is 2.
- For i = 4: frequency of a[i] i.e. 1 from i to n-1 is 1.
- Hence we have one elements from index 0 to 4 whose frequency from i to n-1 is 2.
Similarly, For query 2: there is only 1 element in 0 to 4 whose frequency from i to n-1 is 1.
Approach: To solve the problem follow the below idea:
The intuition is to preprocess all the element’s occurrences in the array. We are trying to find out the occurrences of all the elements between each interval in the array and storing them in another 2-d array. Now since we have the the frequency of each element between each interval so we can easily compute the range L to R.
Below are the steps for the above approach:
- Initialize an empty vector called ans to store the results.
- Create a 2D vector called pre of size N+1 by N+1 and initialize all elements to 0.
- For each index, i in the range 0 to N-1, do the following:
- Initialize a variable called cnt to 0.
- For each index j in the range i to N-1, do the following:
- If the value of A[i] is equal to the value of A[j], increment cnt.
- Increment pre[i][cnt] by 1.
- For each index j in the range i to N-1, do the following:
- For each index, i in the range 0 to N, and for each index j in the range 1 to N, do the following:
- Add the value of pre[j-1][i] to pre[j][i].
- For each index i in the range 0 to num-1, do the following:
- Get the values of L, R, and K from the ith element of Q.
- If L is equal to 0, Append the value of pre[R][K]. Otherwise, Append the value of pre[R][K] – pre[L-1][K] to the vector ans.
- Return the vector ans.
Below is the implementation for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; vector< int > solveQueries( int N, int num, vector< int >& A, vector<vector< int > >& Q) { vector< int > ans; vector<vector< int > > pre(N + 1, vector< int >(N + 1, 0)); for ( int i = 0; i < N; i++) { int cnt = 0; for ( int j = i; j < N; j++) { if (A[i] == A[j]) { cnt++; } } pre[i][cnt]++; } for ( int i = 0; i < N + 1; i++) { for ( int j = 1; j < N; j++) { pre[j][i] += pre[j - 1][i]; } } for ( int i = 0; i < num; i++) { int L = Q[i][0]; int R = Q[i][1]; int K = Q[i][2]; ans.push_back((L == 0 ? pre[R][K] : pre[R][K] - pre[L - 1][K])); } return ans; } // Drivers code int main() { int N = 5, num = 2; vector< int > A = { 1, 1, 1, 1, 1 }; vector<vector< int > > Q = { { 0, 4, 2 }, { 0, 4, 1 } }; vector< int > res = solveQueries(N, num, A, Q); for ( auto it : res) cout << it << " " ; return 0; } |
Java
// Java code for the approach import java.util.*; public class GFG { // Function to solve the problem public static List<Integer> solveQueries( int N, int num, List<Integer> A, List<List<Integer> > Q) { List<Integer> ans = new ArrayList<>(); int [][] pre = new int [N + 1 ][N + 1 ]; // Count the frequency of each element in the array for ( int i = 0 ; i < N; i++) { int cnt = 0 ; for ( int j = i; j < N; j++) { if (A.get(i).equals(A.get(j))) { cnt++; } } pre[i][cnt]++; } // Calculate prefix sum of pre array to efficiently // count the number of elements that occur K times for ( int i = 0 ; i < N + 1 ; i++) { for ( int j = 1 ; j < N; j++) { pre[j][i] += pre[j - 1 ][i]; } } // Process each query and store the answer in ans // list for ( int i = 0 ; i < num; i++) { int L = Q.get(i).get( 0 ); int R = Q.get(i).get( 1 ); int K = Q.get(i).get( 2 ); ans.add((L == 0 ? pre[R][K] : pre[R][K] - pre[L - 1 ][K])); } // Return the ans list return ans; } // Driver code public static void main(String[] args) { int N = 5 , num = 2 ; List<Integer> A = new ArrayList<>(Arrays.asList( 1 , 1 , 1 , 1 , 1 )); List<List<Integer> > Q = new ArrayList<>( Arrays.asList(Arrays.asList( 0 , 4 , 2 ), Arrays.asList( 0 , 4 , 1 ))); List<Integer> res = solveQueries(N, num, A, Q); for ( int i= 0 ; i<res.size(); i++) { System.out.print(res.get(i) + " " ); } } } |
Python3
# python code for the approach def solveQueries(N, num, A, Q): ans = [] pre = [[ 0 ] * (N + 1 ) for _ in range (N + 1 )] # Calculate the prefix array for i in range (N): cnt = 0 for j in range (i, N): if A[i] = = A[j]: cnt + = 1 pre[i][cnt] + = 1 # Calculate the prefix sums for i in range (N + 1 ): for j in range ( 1 , N): pre[j][i] + = pre[j - 1 ][i] # Process each query for i in range (num): L, R, K = Q[i] if L = = 0 : ans.append(pre[R][K]) else : ans.append(pre[R][K] - pre[L - 1 ][K]) return ans # Driver code N = 5 num = 2 A = [ 1 , 1 , 1 , 1 , 1 ] Q = [[ 0 , 4 , 2 ], [ 0 , 4 , 1 ]] res = solveQueries(N, num, A, Q) for item in res: print (item, end = " " ) |
C#
// c# code for the approach using System; using System.Collections.Generic; public class GFG { // Function to solve the problem public static List< int > SolveQueries( int N, int num, List< int > A, List<List< int >> Q) { List< int > ans = new List< int >(); int [,] pre = new int [N + 1, N + 1]; // Count the frequency of each element in the array for ( int i = 0; i < N; i++) { int cnt = 0; for ( int j = i; j < N; j++) { if (A[i] == A[j]) { cnt++; } } pre[i, cnt]++; } // Calculate prefix sum of pre array to efficiently // count the number of elements that occur K times for ( int i = 0; i < N + 1; i++) { for ( int j = 1; j < N; j++) { pre[j, i] += pre[j - 1, i]; } } // Process each query and store the answer in ans list for ( int i = 0; i < num; i++) { int L = Q[i][0]; int R = Q[i][1]; int K = Q[i][2]; ans.Add((L == 0 ? pre[R, K] : pre[R, K] - pre[L - 1, K])); } // Return the ans list return ans; } // Driver code public static void Main( string [] args) { int N = 5, num = 2; List< int > A = new List< int >( new int [] { 1, 1, 1, 1, 1 }); List<List< int >> Q = new List<List< int >>( new List< int >[] { new List< int > { 0, 4, 2 }, new List< int > { 0, 4, 1 } }); List< int > res = SolveQueries(N, num, A, Q); for ( int i = 0; i < res.Count; i++) { Console.Write(res[i] + " " ); } } } |
Javascript
// Function to solve the problem const solveQueries = (N, num, A, Q) => { const ans = []; const pre = Array.from({ length: N + 1 }, () => Array(N + 1).fill(0)); // Count the frequency of each element in the array for (let i = 0; i < N; i++) { let cnt = 0; for (let j = i; j < N; j++) { if (A[i] === A[j]) { cnt++; } } pre[i][cnt]++; } // Calculate prefix sum of pre array to efficiently // count the number of elements that occur K times for (let i = 0; i < N + 1; i++) { for (let j = 1; j < N; j++) { pre[j][i] += pre[j - 1][i]; } } // Process each query and store the answer in ans // list for (let i = 0; i < num; i++) { const L = Q[i][0]; const R = Q[i][1]; const K = Q[i][2]; ans.push(L === 0 ? pre[R][K] : pre[R][K] - pre[L - 1][K]); } // Return the ans list return ans; }; // Driver code const N = 5; const num = 2; const A = [1, 1, 1, 1, 1]; const Q = [[0, 4, 2], [0, 4, 1]]; const res = solveQueries(N, num, A, Q); for (const it of res) { console.log(it + " " ); } |
1 1
Time Complexity: O(N2) since 2 nested loops are running for calculating frequency.
Auxiliary Space: O(N2) since a 2-d array is used for storing the frequency.