Ad
  • Custom User Avatar

    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 index char_list[i:]) which means that your solution is closer to being O( n * n) because for each of the n elements in the for loop, you are then doing another approx ~ n operations each time you use the count 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.

  • Custom User Avatar

    The method .count is O(n) itself, so when it is inside a loop, that makes it O(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).

  • Custom User Avatar

    At each iteration, you search something in the whole list: your code isn't O(n), it is O(n²).

  • Custom User Avatar

    This comment is hidden because it contains spoiler information about the solution