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 6 Seq 2: 6 2 1 3 5 4
- 1 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).