CODEWITHSUNDEEP
pythonpython-3.x
Lucas Motta
Lucas Motta

Reputation: 21

Python time limit exceeded

i'm newbie in programming and my teacher asked the class to make a feel exercises in the judge system URI

When I tried to do this exercise the URI system said that my code exceeded the limit time, and ran in 2 seconds. My code was:

cont=0
cont_register=int(input())
coords=[]
for i in range(cont_register):
    coords.append(input())
for i in range(0, cont_register):
    if coords.count(coords[i])>1:
        cont=1
        break
    else:
        cont=cont
print(cont)

The output is always right, but I want to know if there are forms to optimize the running time, because the cont_register is a number between 2 and 500.000

Upvotes: 2

Views: 13405

Answers (3)

zipa
zipa

Reputation: 27879

Try using collections.Counter:

from collections import Counter

cont_register=int(input())

coords=[]

for i in range(cont_register):
    coords.append(raw_input())

coords=Counter(coords)

print(int(coords.most_common(1)[0][1] > 1))

If you can check the input as it comes, this is the fastest option:

cont_register=int(input())
seen = set()
cont = 0
for i in range(cont_register):
    new = input()
    if new in seen:
        cont = 1
        break
    else:
        seen.add(new)
print(cont)

Upvotes: 2

xrisk
xrisk

Reputation: 3898

A straightforward way to do this is to use a nested list (also known as a 2D array in C/C++/etc) to mark quadrants that have already been visited.

You traverse through the entries in the input one by one, and check if they have already been visited. If so, you set the answer to be 1 and stop processing further input. Otherwise, you set the corresponding entry in the seen list to True, to indicate that that particular (X, Y) quadrant has already been visited.

This means that you need to traverse the list at most once, which is about as efficient as you get.

Note that X and Y are constrained to be below 500 and hence those are the limits for the list you need to worry about.

seen = [[False] * 501] * 501 
answer = 0
n = int(input())
for i in range(n):
    x, y = [int(_) for _ in input().split(' ')]
    if seen[x][y]:
        answer = 1
        break
    seen[x][y] = True
print(answer)

However, note that this solution is not exactly Pythonic, but is the rough equivalent of what one would do in C or C++ without resorting to the standard library.

Upvotes: 0

Nasif Imtiaz Ohi
Nasif Imtiaz Ohi

Reputation: 1713

the coords.count in your loop is another search through the whole list and thus making the runtime O(n^2). You can make use of the dictionary instead which implements a hash table and makes the search a lot faster and do the duplicate checking at the same time you are taking the inputs (with the already taken inputs!).

This code runs with python3. I couldn't check with the URI judge, as I don't find any submission link on the page. However, it should run within the limit.

cont=0
cont_register=int(input())
coords={}
for i in range(0,cont_register):
    inp=input()
    if inp not in coords.keys():
        coords[inp]=1
    else:
        cont=1
        break #if you don't want to continue taking inputs
print(cont)

Upvotes: 0

Related Questions