O(n^2) code getting accepted for n=10^6

help
1

problem link: CodeChef: Practical coding for everyone
Solution link: CodeChef: Practical coding for everyone

this code is getting accepted despite having (n^2) complexity in the worst case
as it has outer "for " loop which will run n times and inside it a " while " loop which can also run for n times in worst case.

if i am wrong in calculating time complexity,please let me know…

2

No this is O(2n) because maximum comparisons are 2n.

In O(n^2) for each iteration you have n iteration again.

But here it’s 2 pointer approach
Here outside: for (n iterations)
Here inside: While (something depending “start” variable )
since : 0<=start<=n
Also start will go from 0 to n once in execution of whole program

So test-case for worst case scenario
I/P: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcd
(distinct -> abcd)

So when i=last index (n-1), start =0
so to find start will go from 0 to n-3

So O(n-3) + O(n) = O(2*n) = O(n)

5 Likes
3

Thanks man, i understood now. :innocent: