How could I optimize my approach (ALTARAY)

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!

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

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

Hey @therisingsun