0

Problem : we have a sequence of numeric pairs like [(10, 20), (30, 10), (30, 40), (20, 10), (90, 80), (40, 30), (50, 60)] . Output : print the symmetric pairs in the sequence . ex (10, 20) (20, 10) (30, 40) (40, 30).

I am able to solve this using two for loops and searching each item in the sequence for the symmetric pair. But the complexity is O(n^2). Any other method or data structure to reduce the time complexity ?

user2088083
  • 53
  • 8

2 Answers2

2

Use hashing and you may be able to do O(N)

  • Loop over each pair (a,b)
    • Check if pair(b,a) is in set
    • If not add pair (a,b) to the set
    • If so add to solution
Sam Segers
  • 1,951
  • 2
  • 22
  • 28
2

python implementation

data = [(10, 20), (30, 10), (30, 40), (20, 10), (90, 80), (40, 30), (50, 60)]

output = {}

for (a, b) in data:
    v_min = min(a, b)
    v_max = max(a, b)

    if not output.has_key((v_min, v_max)):
        output[(v_min, v_max)] = 0

    output[(v_min, v_max)] += 1

pairs = filter(lambda (v, count): count >= 2, output.items())
print map(lambda ((a, b), count) : ((a, b), (b, a)), pairs)
  • Considering n as a very large number (number of pairs ) . Does the search in a dictionary will take time same as ~O(n) ? Which will again make a total complexity as n^2 – user2088083 Apr 09 '16 at 06:39
  • http://stackoverflow.com/questions/1963507/time-complexity-of-accessing-a-python-dict in worst case it is o(n) –  Apr 09 '16 at 09:23