How could I optimize my approach (ALTARAY)

general
, ,
#1

This is my solution: https://www.codechef.com/viewsolution/15898547

I am getting TLE as my code takes about 5 sec to execute. Could someone suggest me, on how could I optimize my approach (or the code) so as to make it fit in 2 sec ??

Thanks a lot! :slight_smile:

#2

Hey @arnavvarshney

You are getting a TLE because the complexity of your code is O(N^2). You could write a more optimized code with a complexity of O(N), i.e. with a single loop traversing the array instead of using two loops.

Hint: Since the question is asking about the length from each ‘x’ as start, you should traverse the array from the end, so that you can store the desired value for each index in an auxiliary array. Try using the length of alternate array traversed so far in one single iteration.

I can help you with the code as well, but it will be better for you to think of this approach once.

1 Like
#3

Your solution is of O(n^2) complexity you can optimize it in O(n).

Hint:Make a variable named count and perform count++ when alternative values appear, if alternative values are of same kind then take for loop from count-1 until count=0 and update array an repeat for further values.

Please first try yourself if you can’t come up with some solution then here is my solution: link text

1 Like
#4

Hey @therisingsun
I ain’t able to get it! Could you please help me with the code too??
Thanks a lot!

#5

Got it! Thanks a lot!

#6

Your welcome. keep coding.

1 Like
#7

You can have a look at the code for the approach which I was trying to tell you.

Feel free to comment in case of any clarifications.