CODEWITHSUNDEEP
javapythoncalgorithmtime-complexity
Novice123
Novice123

Reputation: 45

Finding the correct path in O(n) time

Consider there is a path from source to destination but is jumbled up.

For example

A B      E F
B C      A B
C D  ->  D E
D E      C D
E F      B C

Assuming there are no cycles, Given the Jumbled path can we get back the original path in O(n) time.

Upvotes: 3

Views: 106

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58231

The start of the path is the element that appears as the first thing in a pair, but not the second. Build a map from start to next node in the path, and iterate through it.

Each of the three steps is O(n), giving an O(n) overall solution.

Here's some example code in Python 2.7:

import sys

follow = dict(line.strip().split() for line in sys.stdin)
x = set(follow).difference(follow.itervalues()).pop()
while x:
    print x
    x = follow.get(x)

Example run:

$ echo -e "E F\nA B\nD E\nC D\nB C" | python follow.py 
A
B
C
D
E
F

Upvotes: 1

Related Questions