There are two orderings of numbers from the same set. Number $a$ is immediately before $b$ iff $a$ appears before $b$ in both sequences and there is no other number that appears between them in both sequences.So in this example:Seq 1: 1 2 3 4 5 6Seq 2: 6 2 1 3 5 41 is not immediately before 2 because they appear in opposite orders. 1 is not immediately before 4 because 3 appears between them in both sequences.2 is immediately before 3 and 3 is immediately before 4.The problem is to find all pairs $a$, $b$ such that $a$ is immediately before $b$ in $O(n^2)$ time. How can this be done?I understand that the naive solution can work in $O(n^3)$: For each pair in the first sequence ($n^2$ pairs) verify it using the second sequence ($O(n)$ time).
How to solve this partial order reduction in $O(n^2)$?
algorithms;partial order
I think I am able to solve it.First, have a lookup array for each sequence where array[element] = element's position in sequence [O(1)].Phrased another way, this algorithm will find all successors for each of the elements in the first sequence. Finding successors for each element will take O(n) time.For i in range(0,n):    initialize most_recent_successor to None    For j in range(i+1, n):        if pos. of seq_1[j] > pos. of most_recent_successor in both sequences:            advance j        else:            most_recent_successor = seq_1[j]            add (seq_1[i], seq_1[j]) to resultEssentially, if a valid pair (seq_1[i], seq_1[j]) exists, then any pair (seq_1[i], seq_1[k]) will not be valid if the position of seq_1[k] in comes after the position of seq_1[j] in both sequences.So, for the example in the question, (1, 3) is a valid pair. Therefore, (1,4) and (1, 5) are not valid pairs since 4 and 5 come after 3 in both sequences.Edit: Please look at ruakh's insightful answer on lookup arrays I used here.