I see the time complexity of the solution is mentioned as O(n). May be my understanding is wrong. But when i see a while loop inside the For Loop, i assume it is O(n2).
since there is possibility of looping multiple time when in the while loop. it is safe to assume the worst case.
This is Fatimah from Educative
It is generally the case that when nested loops are used, the time complexity is O(n^2). However, this is not always true. It really depends upon the algorithm. For this algorithm, the inner loop (while-loop) does not execute on each iteration of the outer loop. Each item is pushed and popped at-most one time from the stack. Therefore the worst-case complexity of the while-loop independently, in the whole program, is O(n). An easy way to confirm this is just by putting a print statement inside it and checking the output.
For the algorithms having the complexity is O(n^2), the inner loop iterated O(n) in one iteration of the outer loop. Whereas, here, it iterated O(n) in the whole program. I hope this explanation helps.
Best regards,
Fatimah Abdullah | Developer Advocate
Educative