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.

Examples

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]

Solution

Method 1 – Brute Force

This straightforward method involves iteratively removing each conflicting pair from the list and then calculating how many valid subarrays remain for each case. For every possible removal, you check the number of subarrays that do not contain both elements of any remaining conflicting pair. While simple to implement, this approach is highly inefficient and does not scale well for large inputs.

Method 2 – Prefix Maximums and Greedy Split

Intuition

This optimized strategy works in two main phases:

  1. First, calculate the number of valid subarrays that can be formed when all conflicting pairs are enforced.
  2. Then, determine which conflicting pair is the most restrictive—meaning, its removal would unlock the largest number of additional valid subarrays.

Approach

Step 1: For each position in the array, keep track of all conflicting pairs where that position is the right endpoint. This is done by building a right array, where right[r] contains all left endpoints that conflict with r.

Step 2: Maintain two variables, left[0] and left[1], representing the most and second-most restrictive left endpoints seen so far. Also, create a bonus array to record the potential gain in valid subarrays if a particular conflict is removed.

Step 3: Iterate through each position r in the array. For every left endpoint in right[r], update left to reflect the most restrictive endpoints. This helps determine the earliest start for a valid subarray ending at r.

Step 4: For each position r, the number of valid subarrays ending at r is r - left[0]. Add this to the running total. For the most restrictive left endpoint, update bonus[left[0]] by adding left[0] - left[1], which represents the extra subarrays gained if that conflict is removed.

Step 5: The final answer is the sum of the total valid subarrays and the maximum value in the bonus array, reflecting the best possible gain from removing a single conflicting pair.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    long long maxSubarrays(int n, vector<vector<int>>& conflictingPairs) {
        vector<vector<int>> right(n + 1);
        for (auto& p : conflictingPairs) {
            int a = p[0], b = p[1];
            right[max(a, b)].push_back(min(a, b));
        }
        long long ans = 0;
        vector<long long> bonus(n + 1, 0);
        vector<int> left = {0, 0};
        for (int r = 1; r <= n; ++r) {
            for (int l : right[r]) {
                vector<int> candidates = {left[0], left[1], l};
                sort(candidates.begin(), candidates.end(), greater<int>());
                left[0] = candidates[0];
                left[1] = candidates[1];
            }
            ans += r - left[0];
            bonus[left[0]] += left[0] - left[1];
        }
        return ans + *max_element(bonus.begin(), bonus.end());
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public long maxSubarrays(int n, int[][] conflictingPairs) {
        List<List<Integer>> right = new ArrayList<>();
        for (int i = 0; i <= n; i++) right.add(new ArrayList<>());
        for (int[] p : conflictingPairs) {
            int a = p[0], b = p[1];
            right.get(Math.max(a, b)).add(Math.min(a, b));
        }
        long ans = 0;
        long[] bonus = new long[n + 1];
        int[] left = {0, 0};
        for (int r = 1; r <= n; r++) {
            for (int l : right.get(r)) {
                int[] candidates = {left[0], left[1], l};
                Arrays.sort(candidates);
                left[0] = candidates[2];
                left[1] = candidates[1];
            }
            ans += r - left[0];
            bonus[left[0]] += left[0] - left[1];
        }
        long maxBonus = 0;
        for (long b : bonus) maxBonus = Math.max(maxBonus, b);
        return ans + maxBonus;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

from typing import List
class Solution:
    def maxSubarrays(self, n: int, conflictingPairs: List[List[int]]) -> int:
        right = [[] for _ in range(n+1)]
        for a, b in conflictingPairs:
            right[max(a, b)].append(min(a, b))
        ans = 0
        left = [0, 0]
        bonus = [0] * (n + 1)
        for r in range(1, n + 1):
            for l in right[r]:
                left = sorted([left[0], left[1], l], reverse=True)[:2]
            ans += r - left[0]
            bonus[left[0]] += left[0] - left[1]
        return ans + max(bonus)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn max_subarrays(n: i32, conflicting_pairs: Vec<Vec<i32>>) -> i64 {
        let n = n as usize;
        let mut right = vec![Vec::new(); n + 1];
        for p in &conflicting_pairs {
            let a = p[0] as usize;
            let b = p[1] as usize;
            right[a.max(b)].push(a.min(b));
        }
        let mut ans = 0i64;
        let mut left = [0usize, 0usize];
        let mut bonus = vec![0i64; n + 1];
        for r in 1..=n {
            for &l in &right[r] {
                let mut candidates = vec![left[0], left[1], l];
                candidates.sort_by(|a, b| b.cmp(a));
                left[0] = candidates[0];
                left[1] = candidates[1];
            }
            ans += (r - left[0]) as i64;
            bonus[left[0]] += (left[0] as i64 - left[1] as i64);
        }
        ans + *bonus.iter().max().unwrap()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    maxSubarrays(n: number, conflictingPairs: number[][]): bigint {
        const right: number[][] = Array.from({ length: n + 1 }, () => []);
        for (const [a, b] of conflictingPairs) {
            right[Math.max(a, b)].push(Math.min(a, b));
        }
        let ans = 0n;
        let left: [number, number] = [0, 0];
        const bonus: bigint[] = Array(n + 1).fill(0n);
        for (let r = 1; r <= n; r++) {
            for (const l of right[r]) {
                const candidates = [left[0], left[1], l].sort((a, b) => b - a);
                left = [candidates[0], candidates[1]];
            }
            ans += BigInt(r - left[0]);
            bonus[left[0]] += BigInt(left[0] - left[1]);
        }
        return ans + bonus.reduce((a, b) => a > b ? a : b, 0n);
    }
}

Complexity

⏰ Time complexity: O(n + m). The algorithm iterates through all positions from 1 to n, and each of the m conflicting pairs is processed only once, making it efficient and not O(n * m). 🧺 Space complexity: O(n). Space usage is linear due to the right and bonus arrays, each with up to about 2n elements.