Maximum Unique Segment MAXSEGM

https://www.codechef.com/viewsolution/14359135
passes all tests
but-https://www.codechef.com/viewsolution/14359120
shows TLE. I don’t understand why? the only difference is x is set in first case and list in second one.

I am no python user, but from the little crumps and pieces by which i know this language, i think this will satisfy you-

The major advantage of using a set, as opposed to a list, is that it has a highly optimized method for checking whether a speci?c element is contained in the set. This is based on a data structure known as a hash table.

Source- http://www.geeksforgeeks.org/sets-in-python/

The difference lies in the way of searching.

You are using the in operator to search whether c[j] is in x or not. The time complexity of in operator depends entirely on the container being used.

  1. For set its O(1) on average.
  2. For list its O(N) on average.

Therefore, the solution using a set gets AC while the one using a list gets TLE.

You can refer to the following link for the time complexities of various operations in python.

https://wiki.python.org/moin/TimeComplexity

1 Like