# Bug in judge: TLE vs Accepted comparison

• Solution below is a correct n^2 without any obvious problems, it is rejected as TLE:

``````class Solution(object):
def numberOfBoomerangs(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
import collections
dist = collections.defaultdict(int)

count = 0
for i in xrange(len(points)):
(ax, ay) = points[i]
for ii in xrange(i+1, len(points)):
(bx, by) = points[ii]
d = (ax-bx)**2 + (ay-by)**2
A = (ax, ay, d)
B = (bx, by, d)
dist[A] += 1
dist[B] += 1

for n in dist.itervalues():
count+=n*(n-1)

return count
``````

The same solution, but reorganized so that the dict is emptied after each outer-loop iteration (I guess preventing the dict from growing too large?) and accumulating the count on each iteration, is accepted:

``````class Solution(object):
def numberOfBoomerangs(self, points):
"""
:type points: List[List[int]]
:rtype: int
"""
import collections
import itertools

count = 0
for i in xrange(len(points)):
dist = collections.defaultdict(int)
(ax, ay) = points[i]
for ii in xrange(len(points)):
(bx, by) = points[ii]
d = (ax-bx)**2 + (ay-by)**2
dist[d] += 1

for n in dist.itervalues():
count+=n*(n-1)

return count
``````

The 1st, TLE solution actually makes n fewer iterations than the Accepted, since the first has `n*(n-1) + n*(n-1) = 2n*(n-1) = 2n^2-2n` iterations, whereas the second one has `n^2 + n*(n-1) = 2n^2-n` iterations. Either way, the time complexity is the same and both should be accepted.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.