1.
Introduction
2.
The Problem Statement
2.1.
Example
3.
Approach
3.1.
Algorithm
3.2.
Program
3.2.1.
Input
3.2.2.
Output
3.3.
Time Complexity
3.4.
Space Complexity
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Frequency Range Count

Ujjawal Gupta
0 upvote

## Introduction

One day, the ninja's teacher gave him an assignment in which he had given an array. His task was to find the count of all such numbers whose frequency in the subarray is equal to the number itself. Your task is to help ninja.

The above problem is the standard Range Query problem. Range query based-coding problems are widely asked in coding contests and various coding interviews. Here we will discuss the naive approach.

## The Problem Statement

Given an array, ‘ARR’ of size ‘N’ and the number of queries ‘Q.’ You are given two integers, ‘L’ and ‘R’ in each query. For each query, your task is to find the count of all such numbers in the subarray of ‘ARR’ starting from the ‘L’ index and ending on the ‘R’ index, whose frequency in this subarray is equal to the number itself.

### Example

Suppose an array ‘ARR’ = {2,3,1,3,2,3,4} and there are one queries:

• L = 0 and R = 6. Here the frequency of all the subarray elements starting from the 0th index and ending on the 6th index is given below:
• The frequency of 1 is 1.
• The frequency of 2 is 2.
• The frequency of 3 is 3.
• The frequency of 4 is 1.

We have seen that all the numbers except 4 have the same frequency as the number itself. Hence the total count for this subarray is 3.

Check out Euclid GCD Algorithm

## Approach

For each query, the naive approach to solve the above problem is to traverse the whole subarray and count the frequency of each element. If the frequency of an element in the subarray is equal to the number itself, then consider it in the final answer; otherwise, leave it.

The algorithm of the approach is described below.

### Algorithm

• Create a function getCount():
• Function Description:
• It takes array ‘ARR’, ‘L’ and ‘R’ as an input.
• It returns the count of all such numbers in the subarray(starting from the Lth index and ending on the Rth index) whose frequency is equal to the number itself.

• Function Working:
• Create a variable ‘ANS’ to store the total count. Initialize ANS = 0.
• Create a map to store the frequency of elements.
• Iterate loop in the subarray and do the following in each traversal:
• MP[ARR[i]] ++.
• Iterate map and check if the key and value are equal then:
• ANS ++.
• Return ANS.

• Call the above function for all the queries.

### Program

``````#include <bits/stdc++.h>
using namespace std;

/*Function to get the count.*/
int getCount(vector<int> &arr, int l, int r)
{

/*Variable to store the total count.*/
int ans = 0;

/*Map to store the frequency of elements.*/
unordered_map<int, int> mp;
for (int i = l; i <= r; i++)
{
mp[arr[i]]++;
}

for (auto it : mp)
{
/*Check if the frequency of the element is equal to the number itself.*/
if (it.first == it.second)
ans++;
}
return ans;
}
int main()
{

/*Taking the array as an input.*/
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++)
{
cin >> arr[i];
}

/*taking the number of queries as an input.*/
int q;
cin >> q;
while (q--)
{
int l, r;
cin >> l >> r;

/*Function call.*/
int ans = getCount(arr, l, r);
cout << ans << endl;
}
return 0;
}``````

#### Input

``````7
3 1 2 2 3 3 7
2
0 6
2 3``````

#### Output

``````3
1``````

### Time Complexity

O(Q * N), where ‘N’ is the number of elements in the array, and ‘Q’ is the total number of queries.
Reason: Storing the frequency of each element takes O(N) time, and we need to perform this for all the queries. Hence, its time complexity is O(Q * N).

### Space Complexity

O(N), where N is the number of elements in the array.
Reason: Creating a map takes O(N) space in the worst case.

## FAQs

1. What is a map?
The map is a data structure that stores data in key-value pairs. The map is of two types, i.e., ordered and unordered maps.

2. What is the difference between ordered and unordered maps?
The ordered map uses the concept of the red-black tree for its implementation, while the unordered map uses the concept of hashing.

3. What is the time complexity of the above code if we use an ordered map?
If we use an ordered map instead of an unordered map, its time complexity is O(N * Q *log(Q)). As insertion takes log(N) time in the ordered map and O(1) time in the unordered map.

4. How can we calculate the frequency of elements?
We can calculate the frequency of an element in the subarray by creating a map data structure and storing the number and its frequency as key-value pairs.

5. Can we solve the above problem in O(1) extra space?
Yes, we can, but time complexity increases in that implementation, as we need to traverse the whole array for all the elements.

## Key Takeaways

In this blog, we learned about an interesting problem based on a range query. We solved the problem using the brute force approach. Another problem involving range query is: here.

Hence learning never stops, and there is a lot more to learn.

Check out this problem - Longest Subarray With Sum K

So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!

Live masterclass