Triplets in the Same Relative Order in Two Rankings
Two independent ranking systems each order the same set of items. Count the triplets of items that appear in the same relative order in both rankings — a measure of agreement.
Problem
Given two integer arrays nums1 and nums2 that are both permutations of 0..n-1, return the number of triplets of indices (positions of values) that are increasing in both permutations simultaneously. Formally, count value triples (x, y, z) that appear in the order x, y, z in nums1 and also in nums2.
Input
Two arrays nums1 and nums2, each a permutation of 0..n-1.
Output
An integer: the number of common increasing triplets.
Constraints
- 3 <= n <= 100000
- nums1 and nums2 are permutations of 0..n-1.
Examples
Example 1
Input
nums1 = [2,0,1,3], nums2 = [0,1,2,3]
Output
1
Only the triple (0,1,3) is in increasing order in both.
Example 2
Input
nums1 = [0,1,2,3,4], nums2 = [4,0,1,3,2]
Output
4
Four triples share the same relative order in both.