Count how many subarrays remain valid after removing exactly one conflicting pair from a list of forbidden pairs.
You are given an array of distinct integers and a list of conflicting pairs. A subarray is considered valid if it does not contain both elements of any conflicting pair.
You may choose at most one conflicting pair to remove from the list. After removing that one pair, determine the maximum possible number of valid subarrays in the array.
A subarray is any contiguous segment of the array. Two elements conflict if they appear together in one of the remaining pairs.
Input Format
- An integer array
numsof distinct values. - A list of pairs
pairs, where each pair[a, b]marks a conflict between valuesaandb. - You may remove at most one pair from
pairsbefore counting valid subarrays.
Output Format
Return the maximum number of valid subarrays obtainable after removing at most one conflicting pair.
Constraints
numscontains distinct integers.- Each conflict pair refers to values present in
nums. - Subarrays are contiguous.
- Choose at most one pair to remove.
- Exact official constraints are unknown from the source metadata.
Example 1
Input
nums = [1,2,3,4], pairs = [[2,4]]
Output
10
Explanation
Without removing anything, every subarray is valid except [2,3,4] and [1,2,3,4] if both 2 and 4 appear together. Removing the only conflicting pair makes all 10 subarrays valid.
Example 2
Input
nums = [1,2,3,4,5], pairs = [[2,5],[3,4]]
Output
13
Explanation
Removing [2,5] increases the number of valid subarrays, but [3,4] still blocks some segments. The best result is 13 valid subarrays.
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.