CODEWITHSUNDEEP
python
Ryan
Ryan

Reputation: 10109

Getting Test Case Run time error

Im working on this question(not Homework) Given a list of unsorted integers,A = {a1, a2, ...,an) can you find the pair of elements that have the smallest absolute difference between them? If there are multiple pairs, find them all.

This is what i came up with:

num = int(input())
array = [int(x) for x in input().split()]
diff = []
for i in range(len(array)):
    for j in array:
        diff.append(array[i]- j)

total = []
for i in diff:
    if i > 0:
        total.append(i)

grail = min(total)
holy = []
for i in range(len(array)):
     for j in array:
        if ((array[i] - j) == grail):
            holy.append(array[i]) 
            holy.append(j)

final = sorted(holy)
for item in final:
    print(item, end = ' ')

This runs for few cases but gets runtime error on large inputs,any suggestion i might try?

Ex:

Input = [-20 -3916237 -357920 -3620601 7374819 -7330761 30 6246457 -6461594 266854 -520 -470 ]

Output = -520 -470 -20 30

Explanation = (-470) - (-520) = 30 - (-20) = 50, which is the smallest difference.

Thanks in advance

Upvotes: 0

Views: 36

Answers (1)

Supreet Sethi
Supreet Sethi

Reputation: 1806

I did not bother to check your code for correctness because the implementation has complexity of O(n^2)

for i in range(len(array)):
 for j in array:
    if ((array[i] - j) == grail):
        holy.append(array[i]) 
        holy.append(j)

The required answer needs to have preferable complexity of O(log n). For achieving that you need to sort the list upfront.

from unittest import TestCase
import unittest
from sys import maxsize
from itertools import tee

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)



def solution(n):
    n = sorted(n)
    pairs = []
    diff = maxsize
    for l, u in pairwise(n):
        if u - l <= diff:
            diff = u - l
            pairs.append((diff, (l,u)))
    pairs = sorted(pairs)
    least = pairs[0][0]
    return list(map(lambda x: x[1], filter(lambda x: x[0] == least, pairs)))

class TestLeastDiffrence(TestCase):
    def testSimple(self):
        n = [-20, -3916237, -357920, -3620601, 7374819, -7330761, 30, 6246457, -6461594, 266854, -520, -470]
        self.assertEqual(solution(n),[(-520, -470), (-20, 30)])

if __name__ == '__main__':
    unittest.main()

Upvotes: 2

Related Questions