CODEWITHSUNDEEP
algorithmsearch
user2088083
user2088083

Reputation: 53

Reduce Time complexity of a search to less than n^2

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 ?

Upvotes: 0

Views: 201

Answers (2)

user3278460
user3278460

Reputation:

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)

Upvotes: 2

Sam Segers
Sam Segers

Reputation: 1951

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

Upvotes: 2

Related Questions