Is the frequency array is the solution?

Revision en1, by SeifShaheen, 2023-09-09 19:09:04

I think all people have issues with time limit exceed. so i will write a small blog about the frequency array which is the solution of 70% of the time limit exceed error.

What is the frequency array? frequency array is an array that saves how many times this value repeated like i have input: 1 2 3 1 1 5 the frequency array will have values of: {0,3,1,1,0,1} when you use it, the time decreases from 2 seconds to maybe 400ms in 100 000 inputs (2 seconds if you used nested loop the know the values).

How to write it as a code? first we have an array of size n(100 000) and we get its elements from a loop like:

int n;
cin >> n;
int arr[n];
int freq[100001] = {0};
for(int i = 0; i < n; i++)
{
    cin >> arr[i];
    //here we use frequency array
    freq[arr[i]]++; // this makes the place of the number increases from 0 to 1 and it's the count for the first loop
}

What is the benefit of it? - You can search easily with just the number if it's more than 0 so it exists. - time is almost the quarter of the nested loops time. more and more of benefits you can search for them. I hope my blog about the frequency array makes your code more efficient and increases your knowledge. See you in another blog <3

Tags frequency array

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English SeifShaheen 2023-09-09 19:09:04 1337 Initial revision (published)