I think the test cases are weak, the extra notes at the bottom of the description are not tested at all. (I passed without considering self loops)

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.

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).

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

The whole point is that failing an O(n) solution means micro-optimisations are required. I know my reduce is slower than my for .. of by a constant factor.

Iterating the input twice does not make a solution not O(n). Using reduce does not make a solution not O(n).

Requiring micro-optimisations is not the way to test performance. Any O(n) ( again, within reason wrt the constant factor ) should pass.

Thank you BenjaminZWhite for the detailed explanation, I now have all tests fully working with your comment but I guess I need to look into speeding up things.

Technically, the O(2n) notation is the same as O(n). Nonetheless, even if your algorithm is already O(n), it must be optimized further to iterate through the string only once.

has been approved

Nice, and thanks again/obrigado for the translation!

1. Function Name changed
2. Invalid Characters removed

Hi @Dmillenaar and welcome to Codewars;

Since you are new I just wanted to clarify something, in case that's what is causing the difference between your IDE and Codewars:

When you click "Test" on any kata, your code is tested against the (small, few in number) tests visible in the bottom right of the kata environment. In this kata, these are the SAMPLES that are approximately 6-7 in number, with small input strings. These are designed to be "easy" tests, to check your code logic etc.

When you click "Attempt" you will then encounter the full set of kata tests which can be very large.

If you are only copying the "small tests" into your IDE, then that is why you are timing out here and not in your IDE.

If you want to recreate the size of the full kata tests to see the performance of your code in your own IDE, then randomly generate a string of length 5000000 consisting of >, <, and . and see how long it takes on your PC.

@macambira Please see my Issue post, with 2x small issues with Python translation, raised above:

https://www.codewars.com/kata/6319dba6d6e2160015a842ed/discuss/python#631bcf7c0b9cb00120ed1543

Cheers and thanks for translating

2 small issues with Python translation:

1. function name should be in snake_case count_photos. Only 8 solutions in Python so far if you want to change this quickly.

2. some of the fixed tests have invalid characters, presumably from copy-pasting:

("'..<..<>>>><..>>><..><>.<>><><>>.<>>.><<<<>.<><.>>.>..>..>>.>><>><.><>.<<>.<.<.<.'", 720) # <--- "' at start and end of string

(".>><<>..>><>.<><<><<<>...<.<><.......>>><<>><>.>.<..<><<<.>.><.>.>.<>.><><..>.<>..>><>>.<<.<.>.<<><.>...<>..<>...<><.<<<')", 1748) # <----- ') at end of string

I will past a copy of a link to this post in a reply to the Python translator @macambira

that solution is not exactly O(2n). I tested it on my machine and compared to the optimal which requires 1 pass its around 7-8 times slower.