Frequency of Limited Range Array Elements | DSA | Programming Tutorials | GeeksforGeeks

Our courses :

This video is contributed by Rahul Singla

Please Like, Comment and Share the Video among your friends.

Install our Android App:

If you wish, translate into the local language and help us reach millions of other geeks:

Follow us on Facebook:

And Twitter:

Also, Subscribe if you haven't already! :)

[lakshyamehta]

GREAT EXPLAINATON!!
Everyone is just repeating the written code but you explained that why we do all the steps.

[anshikaaa]

I am commenting so that people should know that u have explained very well(every bit). And if someone doesn't get it then watch it again

[bravoboom]

TBH I spend more then hour to solve this problem and if you're beginner too then jump into second explanation that will be 23:05 and understand from there don't waste your time in first explanation because that is worst .

[princeshukla]

best explain sir and very very thanks from bottom of my heart

[poshettiakhil]

The best explaination I have seen so far, thanks a lot for the last two efficient approaches, but in the last but one approach I got confused when you said e as arr[i]-e, but it's actually arr[i]-1

[anushkajain]

Awesome thinking
In the starting i just got the frequency array concept
The new one is really gud

[a__saquibsheikh]

Extremely well explained. Thank you so much Sir. Keep it up!!!

[mohammedharoon]

For this solution public static void frequencyCount(int arr[], int N, int P) {
// do modify in the given array
int i = 0;

while(i < N) {

// To avoid array index out of bounds exception

if(arr[i] > N) {
arr[i] = 0;
continue;
}

if(arr[i] <= 0) {
i++;
continue;
}

int index = arr[i] - 1;

if(arr[index] <= 0) {
arr[index]--;
arr[i] = 0;
i++;
} else {
arr[i] = arr[index];
arr[index] = -1;
}
}

for(int j=0; j<N; j++) {
arr[j] = Math.abs(arr[j]);
}
} we get an array index of out of bounds exception if we dont add this base check
if(arr[i] > N) {

arr[i] = 0;
continue;
} cause the array somtimes be like arr = {8, 9} arr[i] - 1 index will give index out of bound exception make sure to add this check.

[satwik_dash]

Last approach is the best, 2nd last does count to O(N) in Big-Oh, but we iterate more than N times so its not as good as the last one.

[rakeshranjan]

Hi
I have an array of positive integer {12, 32, 34, 63, 16, 65, 60}. My task is to count the occurence of each digit and return array with digits having max counts .
Output
arr2={1, 2, 3, 6}.

[abhishekpattnaik]

initial array is 2 3 2 3 5 then answer should be 0 2 2 0 1, but in 18:49 you say that its 0 2 1 0 1

[saitama_capedbaldy]

Last approach is not good, it will not work in many cases

[hamzaansari]

The last method has some edge case issues

[bandaruneeraj]

JAVA SOLUTION IS HERE:
class Solution{
//Function to count the frequency of all elements from 1 to N in the array.
public static void frequencyCount(int arr[], int N, int P)
{
// code here
int i=0;
while(i<N){
if(arr[i]>N){
arr[i]=0;
}
if(arr[i]<=0){
i++;
continue;
}

int e =arr[i]-1;
if(arr[e]<=0 ){
arr[e]--;
arr[i]=0;
i++;
}
else{
arr[i]=arr[e];
arr[e]=-1;

}
}
for(int j=0;j<N;j++){
if(arr[j]<0){
arr[j]=arr[j]*-1;
}
}
}
}

[rohitvijayvargiya]

sorry but not pleased with the explanation(especially the last one)

[udbhavvikramsingh]

The last algorithmic approach is giving runtime error;

[shivendra]

Can anyone tell why Signal Abort 3 error coming in my code


void frequencyCount(vector<int>& arr, int N, int P)
{
//SUBTRACT 1 FROME EACH ELEMENT SO THAT IT BECOMES INT THE RANGE 0 TO P-1

for(int i=0;i<N;i++)
{
arr[i]--;
}
for(int i=0;i<N;i++)
{
long index = arr[i]%P;
arr[index] = arr[index] + P;
}
long b=P;
for(int i=0;i<N;i++)
{
arr[i]=arr[i]/b;
}
return ;
}

[abhishekupadhyay]

initial array is 2 3 2 3 5 then answer should be 0 2 2 0 1, but in 18:49 you say that its 0 2 1 0 1