Count Frequency in a range

Easy
0/40
profile
Contributed by
251 upvotes

Problem statement

You are given an array 'arr' of length 'n' containing integers within the range '1' to 'x'.


Your task is to count the frequency of all elements from 1 to n.

Note: 
You do not need to print anything. Return a frequency array as an array in the function such that index 0 represents the frequency of 1, index 1 represents the frequency of 2, and so on.
Example: 
Input: ‘n’ = 6 ‘x’ = 9 ‘arr’ = [1, 3, 1, 9, 2, 7]    
Output: [2, 1, 1, 0, 0, 0]
Explanation: Below Table shows the number and their counts, respectively, in the array
Number         Count 
 1                2
 2              1
 3                1
 4                0
 5                0
 6                0
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains two integers, ‘n’ and ‘x’.
The following line contains ‘n’ integers and the array ‘arr’.
Output format: 
Return the frequency array.
Sample Input 1:
6 4
1 3 4 3 4 1
Sample Output 1:
2 0 2 2 0 0
Explanation Of Sample Input 1 :
Frequency table:
Number         Count 
 1                2
 2              0
 3                2
 4                2
 5                0
 6                0
Sample Input 2 :
5 5
1 2 3 4 5
Sample Output 2 :
1 1 1 1 1
Explanation Of Sample Input 2 :
Frequency table:
Number         Count 
 1                1
 2              1
 3                1
 4                1
 5                1
Constraints:
1  <= n <= 10^5
1  <= x <= 10^5
1 <= arr[i] <= x


Hints:
1. Since the range of the elements is known, we can iterate over the range.
2. Since the bounds of the elements are known, a frequency array can be maintained.
3. Try to use the input array as the answer array itself.
Approaches (3)
Brute Force

We iterate over ‘1’ to 'n', and for each value in ‘1’ to 'n', we loop over the array ‘arr’ and find the frequency of that element. 

Algorithm:

  • Initialize a frequency array ‘freq’ of size ‘n’ with all elements initialized to 0.
  • for ‘i’ from 1 to ‘n.’
  • for ‘j’ from 0 to ‘N-1
  • if(j == i) freq[i-1]++;
  • return freq.
Time Complexity

O(n^2) where n is the size of the array

We are iterating through the array for each integer in 1 to n, so there would be n iterations in total.

Hence the time complexity is O(n^2).
 

Space Complexity

O(n), Where n is the length of the array. 

We are creating a new freq array of size n to store the frequency for each element from 1 to n.

Hence the space complexity is O(n).


 

Code Solution
(100% EXP penalty)
Count Frequency in a range
Full screen
Console