Loading collection data...
Collections are a way for you to organize kata so that you can create your own training routines. Every collection you create is public and automatically sharable with other warriors. After you have added a few kata to a collection you and others can train on the kata contained within the collection.
Get started now by creating a new collection.
Hi - to answer your question, even though you only have 1 "visible"
for
loop, you are actually performing a lot more "loops" inside your code:The
.count(".")
function, each time you call it, is looping through the entire list (or at least a significant fraction of the list => all the elements after indexchar_list[i:]
) which means that your solution is closer to beingO( n * n)
because for each of then
elements in thefor
loop, you are then doing anotherapprox ~ n
operations each time you use thecount
method.You're very close to a faster solution though, so I won't spoil too much - think about what you do and do not need to calculate at each step of your for loop.
The method
.count
is O(n) itself, so when it is inside a loop, that makes itO(n*n)
==O(n^2)
time complexity. The only subtle hint I could give is to avoid nested loops. Even if you loop the list 3 times, it can still be O(n).At each iteration, you search something in the whole list: your code isn't
O(n)
, it isO(n²)
.This comment is hidden because it contains spoiler information about the solution