Maximize Subarrays After Removing One Conflicting Pair
You are given an integer n which represents an array nums containing the numbers from 1 to n in order. Additionally, you are given a 2D array conflictingPairs, where conflictingPairs[i] = [a, b] indicates that a and b form a conflicting pair.
Remove exactly one element from conflictingPairs. Afterward, count the number of non-empty subarrays of nums which do not contain both a and b for any remaining conflicting pair [a, b].
Return the maximum number of subarrays possible after removing exactly one conflicting pair.
Example 1
Input
n = 4, conflictingPairs = [[2,3],[1,4]]Output
9Removing
[2, 3] leaves only [1, 4], and there are 9 subarrays that do not contain both 1 and 4.Example 2
Input
n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]Output
12Removing
[1, 2] leaves [[2, 5], [3, 5]], and there are 12 subarrays that do not contain both endpoints of any remaining conflicting pair.Constraints
- 2 <= n <= 10^5
- 1 <= conflictingPairs.length <= 2 * n
- conflictingPairs[i].length == 2
- 1 <= conflictingPairs[i][j] <= n
- conflictingPairs[i][0] != conflictingPairs[i][1]