Triples Both Rankings Agree On

Hard

Two experts ranked the same n items, numbered 0 to n - 1, producing the rankings first and second (each is a permutation of 0 to n - 1, best item first). A triple of distinct items {x, y, z} is **agreed on** if both rankings put them in the same order: for example, x before y and y before z in first and in second alike. Return the number of agreed triples. Each set of three items is counted once. Trying every triple is O(n³), and n can be up to 10⁵.

Example 1

first=[1, 0, 2, 3], second=[0, 1, 2, 3] → 2

The triples (1, 2, 3) and (0, 2, 3) come in the same order in both rankings. Any triple holding both 0 and 1 fails, since those two are swapped.

Example 2

first=[0, 1, 2], second=[0, 1, 2] → 1

The rankings are identical, so the only triple qualifies.

Example 3

first=[3, 2, 1, 0], second=[0, 1, 2, 3] → 0

The second ranking is the first one reversed, so no triple keeps its order.

Constraints

3 ≤ n ≤ 10⁵
len(first) = len(second) = n
first and second are permutations of 0 to n - 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Binary Indexed Tree Segment Tree Array Binary Search Divide and Conquer Ordered Set Merge Sort

Similar problems

Smaller Values to the Right Hard Window Sums Within a Band Hard Pairs With a Steep Drop Hard Cost of Filling a Sorted Shelf Hard Pairs Within a Shifted Gap Hard

Input

first=[1, 0, 2, 3], second=[0, 1, 2, 3]

Expected

Run checks the first 3 tests in your browser. Submit checks all 103 tests on the server, hidden ones included.