Last Updated: 9 Jun, 2023

Count Frequency in a range

Easy

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

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.

Solve now

Approaches

01 Approach

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.

Solve now

02 Approach

We create a frequency array of size 'n'. Initialize with 0 at all the indices.

We traverse the array arr, and for each element in arr, we increment our hashmap at index ‘arr[i] - 1’ by 1.

Algorithm:

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

Solve now

03 Approach

Instead of creating a new frequency array, we will work around storing the frequency in the given array ‘arr’ itself.

For this, we will utilize the constraint ‘arr[i] >= 1’.

We store the frequencies as negative numbers to distinguish the original elements of the array and the frequencies we have stored.

We iterate through the array ‘arr’, and for each positive element found that is less than equal to n, we look at the index ‘arr[i] - 1’

The value at index ‘arr[i]-1’ might be negative, meaning it is a frequency. We can just simply decrement the value at this index. After this, we can mark index ‘i’ as 0, as we never want to consider it again, and move to the index ‘i+1’(if it exists)
The value might be positive, meaning it is an original array element. In this case, we can copy ‘arr[arr[i] - 1]’ to ‘arr[i]’ and mark index ‘arr[i] - 1’ as -1. Instead of moving to the next index, we redo the process for the ‘i’ index.

Algorithm:

int i = 0;
while(i < n)
if(arr[i] > n || arr[i] == 0)
i++;
continue;
int j = arr[i] - 1;
if(arr[j] < 0)
arr[j]--;
arr[i] = 0;
i++;
else
arr[i] = arr[j];
arr[j] = -1;
For integer x in arr
if(x < 0)
x*=1;
Else
x = 0;
return arr;

Solve now