Getting 'TLE' for O(n) algorithm in https://www.codechef.com/problems/ALTARAY

help
, ,
1

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

2

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
3

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
4

Thanks!
I did not think about it.

1 Like
5

Thanks for the help!

1 Like