Hi!

I am getting TLE in the question ALTARAY Problem - CodeChef even when I wrote a O(n) solution as given in the editorial. Any help appreciated.

Thanks!

My solution- CodeChef: Practical coding for everyone

Your code is not O(n). Inserting an element at the beginning of an vector takes O(n) time. I couldn’t help but notice that since you are only inserting elements at the front, you could instead index your vector backwards. Also since it’s a constant size vector, why not initialise it, then you don’t need to use backward indexing.

3 Likes

Inserting at the beginning of a vector takes time proportional to the size of the vector; i.e. your solution is O(N^2).

Edit:

Damnit XD

4 Likes

Thanks!

I did not think about it.

1 Like

Thanks for the help!

1 Like