How to solve this partial order reduction in $O(n^2)$?

Question

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).

Answer 1

Your solution looks good to me, except that your lookup arrays are a bit handwavy: What happens if the set contains negative numbers? Or what if it contains an extremely large number ($\gg n^2$), so that the arrays would need to be massive?

To address this, I'd suggest creating just a single lookup table, that instead of mapping from values to indices, maps from indices in one sequence to indices in the other. Thus seq2[i] = seq1[translator[i]]. You can build that table in $\mathcal{O}\left(n^2\right)$ time using nested loops. You can then ignore seq1 and seq2 in all of your logic: the problem becomes, "find all pairs of indices (i, j) such that i < j, that translator[i] < translator[j], and that i < k < j precludes translator[i] < translator[k] < translator[j]" (which you can solve using basically the same approach as what you've written). The only time you'd refer to seq1 or seq2 again is when you're adding an entry to the result (since for that you want the actual values rather than the indices).

Answer 2

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 result

Essentially, 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.