971. Ordered in Both
Two judges each ranked the same n contestants, identified by the numbers 0 to n-1. Array a lists the contestants from the first judge's best to worst, and array b does the same for the second judge; both are permutations of 0..n-1.
A set of three different contestants is called ordered in both if, when you write its members down in the order the first judge ranks them, the second judge ranks them in that same order too (first member better than second, second better than third). Return the number of such sets as a 64-bit integer; it is 0 when n < 3. A set is counted once no matter how its members are listed.
Example 1
- Input:
- a = [1,3,2,0,4], b = [3,0,1,2,4]
- Output:
- 3
- Explanation:
A triple counts when its three members appear in the same relative order in both lists. Reading list a left to right, the qualifying triples are (1,2,4), (3,2,4), (3,0,4), so the answer is 3.
Example 2
- Input:
- a = [3,2,1,0], b = [2,3,1,0]
- Output:
- 2
- Explanation:
The only combinations of three that keep the same order in both lists are (3,1,0), (2,1,0); that gives 2.
Constraints
- 1 ≤ n = a.length = b.length ≤ 105
- a and b are permutations of 0..n-1
- The answer is at most n(n-1)(n-2)/6 < 1.7 * 1014, which fits a 64-bit integer
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 800 msC++ 200 msJava 400 msJavaScript 400 msTypeScript 400 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)