Count the number of index triplets that are in the same relative order in two permutations.
You are given two arrays that contain the same distinct values, each appearing exactly once. Consider any triplet of values such that these three values appear in the same relative order in both arrays.
Count how many such triplets exist.
More concretely, if the positions of in the first array are increasing, then their positions in the second array must also be increasing. Your task is to return the total number of valid triplets.
Input Format
- Two integer arrays
nums1andnums2 - Each array contains the same set of distinct integers
- The arrays represent permutations of the same values
Output Format
- Return a single integer: the number of good triplets
Constraints
- is a reasonable interview-scale upper bound for this formulation
- Values are distinct within each array
- The two arrays contain the same elements
- Count can exceed 32-bit integer range, so use a 64-bit integer type
Example 1
Input
nums1 = [2,1,3,4] nums2 = [1,2,3,4]
Output
1
Explanation
Only the triplet (2, 3, 4) keeps the same relative order in both arrays.
Example 2
Input
nums1 = [4,0,1,3,2] nums2 = [4,1,0,2,3]
Output
4
Explanation
After converting nums1 into positions in nums2, the valid increasing triplets can be counted by choosing a middle element and combining valid smaller elements on the left with valid larger elements on the right.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.