Suggestions to reduce the compilation time in TRAINSET

Hello coders, I’m new to this site and i was just starting up with this TRAINSET problem. I don’t have much C++ coding experience but i do know the basics. I have tried to solve the problem using only the iostream and string header files. I made a code, but it keeps on giving me the Time Limit Exceeded error. I went through the other results and found them using vectors and stuffs. I haven’t yet studied that. So is there any way I can make my program more efficient using this code?

Thanks in advance!

It looks like that your code is using O(n^2) time which will give TLE verdict. Try using a better data structure like a map in order to reduce the complexity to O(n*logn).


You can do it without any complex data structure.
Input all of them, sort, and then compare. All the words that are the same will be together then. Use a O(nlog n) or the inbuilt sort.

But sorting also uses nested loops right? I don’t know much about big O notation and stuffs, but will sorting be faster (cause it feels like I’m adding an extra work for it to do).

Best sorting algorithm takes time of O(nlogn) while using a map or set uses logn which is faster and i would highly recommend that you need to learn about time complexities before attempting the questions :slight_smile:
Will give you a very good idea on how to attempt it :smiley: