Problem

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

1
2
3
4
5
6

Input: n = 4, conflictingPairs = [[2,3],[1,4]]
Output: 9
Explanation:
* Remove `[2, 3]` from `conflictingPairs`. Now, `conflictingPairs = [[1, 4]]`.
* There are 9 subarrays in `nums` where `[1, 4]` do not appear together. They are `[1]`, `[2]`, `[3]`, `[4]`, `[1, 2]`, `[2, 3]`, `[3, 4]`, `[1, 2, 3]` and `[2, 3, 4]`.
* The maximum number of subarrays we can achieve after removing one element from `conflictingPairs` is 9.

Example 2

1
2
3
4
5
6

Input: n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]
Output: 12
Explanation:
* Remove `[1, 2]` from `conflictingPairs`. Now, `conflictingPairs = [[2, 5], [3, 5]]`.
* There are 12 subarrays in `nums` where `[2, 5]` and `[3, 5]` do not appear together.
* The maximum number of subarrays we can achieve after removing one element from `conflictingPairs` is 12.

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]

Examples

Solution

Method 1 – Prefix Maximums and Greedy Split

Intuition

To maximize the number of subarrays, we want to remove the conflicting pair that blocks the most subarrays. For each pair, count the number of subarrays that would be invalid if that pair remains, and subtract from the total possible subarrays. The answer is the maximum over all possible removals.

Approach

  1. The total number of subarrays is n * (n + 1) // 2.
  2. For each conflicting pair [a, b], remove it and for the remaining pairs, mark the minimum and maximum positions for each value.
  3. For each subarray, check if it contains both elements of any remaining pair. To do this efficiently, for each pair, count the number of subarrays that contain both a and b:
    • For a pair at positions i and j (i < j), the number of subarrays containing both is (i + 1) * (n - j).
    • Sum this for all pairs.
  4. For each possible removal, compute the total valid subarrays and keep the maximum.
  5. Return the maximum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maxSubarrays(int n, vector<vector<int>>& pairs) {
        int total = n * (n + 1) / 2, ans = 0;
        for (int k = 0; k < pairs.size(); ++k) {
            vector<vector<int>> rem;
            for (int i = 0; i < pairs.size(); ++i) if (i != k) rem.push_back(pairs[i]);
            int bad = 0;
            for (auto& p : rem) {
                int a = p[0] - 1, b = p[1] - 1;
                if (a > b) swap(a, b);
                bad += (a + 1) * (n - b);
            }
            ans = max(ans, total - bad);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int maxSubarrays(int n, int[][] pairs) {
        int total = n * (n + 1) / 2, ans = 0;
        for (int k = 0; k < pairs.length; k++) {
            int bad = 0;
            for (int i = 0; i < pairs.length; i++) {
                if (i == k) continue;
                int a = pairs[i][0] - 1, b = pairs[i][1] - 1;
                if (a > b) { int t = a; a = b; b = t; }
                bad += (a + 1) * (n - b);
            }
            ans = Math.max(ans, total - bad);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def maxSubarrays(self, n: int, pairs: list[list[int]]) -> int:
        total = n * (n + 1) // 2
        ans = 0
        for k in range(len(pairs)):
            bad = 0
            for i, (a, b) in enumerate(pairs):
                if i == k:
                    continue
                a, b = a - 1, b - 1
                if a > b:
                    a, b = b, a
                bad += (a + 1) * (n - b)
            ans = max(ans, total - bad)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn max_subarrays(n: i32, pairs: Vec<Vec<i32>>) -> i32 {
        let total = n * (n + 1) / 2;
        let mut ans = 0;
        for k in 0..pairs.len() {
            let mut bad = 0;
            for (i, p) in pairs.iter().enumerate() {
                if i == k { continue; }
                let (mut a, mut b) = (p[0] - 1, p[1] - 1);
                if a > b { std::mem::swap(&mut a, &mut b); }
                bad += (a + 1) * (n - b);
            }
            ans = ans.max(total - bad);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    maxSubarrays(n: number, pairs: number[][]): number {
        const total = n * (n + 1) / 2;
        let ans = 0;
        for (let k = 0; k < pairs.length; k++) {
            let bad = 0;
            for (let i = 0; i < pairs.length; i++) {
                if (i === k) continue;
                let [a, b] = pairs[i].map(x => x - 1);
                if (a > b) [a, b] = [b, a];
                bad += (a + 1) * (n - b);
            }
            ans = Math.max(ans, total - bad);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(m^2) — where m is the number of conflicting pairs.
  • 🧺 Space complexity: O(1) — only a few variables are used.