You are given an integer array nums of length n.
A pair of indices (i, j) is called a shadow pair if all of the following conditions are satisfied:
0 <= i < j < nnums[i] < nums[j]k such that i < k < j and nums[i] < nums[k] < nums[j].Return the total number of shadow pairs.
Example 1:
Input: nums = [3,1,4,2,5]
Output: 5
Explanation:
(i, j) |
nums[i] |
nums[j] |
Shadow Pair |
|---|---|---|---|
| (0, 2) | 3 | 4 | nums[1] = 1 is not strictly between 3 and 4 |
| (1, 2) | 1 | 4 | No index k exists such that 1 < k < 2 |
| (1, 3) | 1 | 2 | nums[2] = 4 is not strictly between 1 and 2 |
| (2, 4) | 4 | 5 | nums[3] = 2 is not strictly between 4 and 5 |
| (3, 4) | 2 | 5 | No index k exists such that 3 < k < 4 |
Thus, the answer is 5.
Example 2:
Input: nums = [6,7,8,9]
Output: 3
Explanation:
(i, j) |
nums[i] |
nums[j] |
Shadow Pair |
|---|---|---|---|
| (0, 1) | 6 | 7 | No index k exists such that 0 < k < 1 |
| (1, 2) | 7 | 8 | No index k exists such that 1 < k < 2 |
| (2, 3) | 8 | 9 | No index k exists such that 2 < k < 3 |
Thus, the answer is 3.
Constraints:
3 <= n == nums.length <= 5 * 1041 <= nums[i] <= 109Loading editor...
[3,1,4,2,5]