Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

SeifShaheen's blog

By SeifShaheen, history, 15 months ago, In English

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

  • Vote: I like it
  • -20
  • Vote: I do not like it