Given two arrays:
2 5 6 4 3 7 1
5 1 6 2 3 7 4
count the number elements x, y that satisfy the condition that x is before y in both arrays.
Progress so far:
Sort the arrays by their indexes. For the example this would be:
object: 1 2 3 4 5 6 7
indexes in the first array: 6 0 4 3 1 2 5
indexes in the secnod array: 1 3 4 6 0 2 5
and compare each tuple with another. If the tuple a has either both indexes lower or higher than of the tuple b, increment the number of elements that satisfy the condition.
This has the time complexity of (N^2)/2, so O(N^2), which is too slow. I understand that there can be no better worst-case scenario complexity, but I'm mostly interested in the average result. So: is there a better way/algorithm?
I thought of using transitive properties (if both (x,y) and (y,z) satisfy the condition, then (x,z) satisfies it as well), but with no luck.
Test cases
For arrays:
2 5 6 4 3 7 1
5 1 6 2 3 7 4
The pairs that satisfy the condition are:
(5,1) (2,3) (2,4) (2,7) (5,3) (6,3) (3,7) (5,4) (6,4) (5,6) (5,7) (6,7)
For arrays:
1 2 3 4 5 6 7
1 2 3 4 5 6 7
The pairs that satisfy the condition are:
(1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (2,3) (2,4) (2,5) (2,6) (2,7) (3,4) (3,5) (3,6) (3,7) (4,5) (4,6) (4,7) (5,6) (5,7) (6,7)
I very much enjoyed thinking about this problem. It does feel like a CS homework problem, so I'll try to touch on the concepts without solving everything.
The Beach Boys principle
A term my calculus teacher used and actually a very applicable problem solving technique. Basically, if you have a tough problem, say "wouldn't it be nice if...", and see if there is something that would make things easier. If there is, see if you can make that so.
In this case, wouldn't it be nice if the top array was ordered and just [1, 2, 3 ...]? That would make solving this problem so much easier as it turns a two array problem into a one array problem.
Well, it can be so! You can map any one of these problems into one that has an ordered first array.
The first example that you listed:
2 5 6 4 3 7 1
5 1 6 2 3 7 4
I argue that the problem above is equivalent to the problem below:
1 2 3 4 5 6 7
2 7 3 1 5 6 4
Mappings
I just do a simple cipher substitution of 2->1 5->2 6->3 4->4 3->5 7->6 1->7 (Why this particular mapping?). This leaves the underlying structure of the problem the same. You can then solve this and then undo your mapping.
You will find that this technique of mapping one problem into a simpler problem comes up often in computer science, especially in your algorithms and computability classes.
You now have a single array problem to find all pairs:
2 7 3 1 5 6 4
The time complexity of this I leave an an exercise to the reader.
P.S. Don't forget the time complexity of undoing your mapping. Sometimes you'll solve a problem thinking it's going to be easy to find out that constructing and deconstructing your mapping is extremely expensive and you have to go back to the drawing board.