3480. Maximize Subarrays After Removing One Conflicting Pair

Description

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: 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:

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⁵
1 <= conflictingPairs.length <= 2 * n
conflictingPairs[i].length == 2
1 <= conflictingPairs[i][j] <= n
conflictingPairs[i][0] != conflictingPairs[i][1]

Solutions

Solution 1: Enumeration + Maintaining Minimum and Second Minimum Values

Thinking

A valid subarray cannot contain both ends of any conflicting pair. We delete exactly one pair and want as many valid subarrays as possible. The scan must be linear.

With no deletion, a left end \(a\) cannot reach the smallest conflicting right end \(b_1\) seen from \(a\) rightward. It contributes \(b_1-a\).

Deleting the pair that created \(b_1\) replaces it by the second smallest \(b_2\) and adds \(b_2-b_1\). Those extras are grouped by \(b_1\); we add the best extra to the no-deletion total.

We store all conflicting pairs \((a, b)\) (assuming \(a < b\)) in a list \(g\), where \(g[a]\) represents the set of all numbers \(b\) that conflict with \(a\).

If no deletion occurs, we can enumerate each subarray's left endpoint \(a\) in reverse order. The upper bound of its right endpoint is the minimum value \(b_1\) among all \(g[x \geq a]\) (excluding \(b_1\)), and the contribution to the answer is \(b_1 - a\).

If we delete a conflicting pair containing \(b_1\), then the new \(b_1\) becomes the second minimum value \(b_2\) among all \(g[x \geq a]\), and its additional contribution to the answer is \(b_2 - b_1\). We use an array \(\text{cnt}\) to record the additional contribution for each \(b_1\).

The final answer is the sum of all \(b_1 - a\) contributions plus the maximum value of \(\text{cnt}[b_1]\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the number of conflicting pairs.

Python3JavaC++GoTypeScriptRust

class Solution:
    def maxSubarrays(self, n: int, conflictingPairs: List[List[int]]) -> int:
        g = [[] for _ in range(n + 1)]
        for a, b in conflictingPairs:
            if a > b:
                a, b = b, a
            g[a].append(b)
        cnt = [0] * (n + 2)
        ans = add = 0
        b1 = b2 = n + 1
        for a in range(n, 0, -1):
            for b in g[a]:
                if b < b1:
                    b2, b1 = b1, b
                elif b < b2:
                    b2 = b
            ans += b1 - a
            cnt[b1] += b2 - b1
            add = max(add, cnt[b1])
        ans += add
        return ans

class Solution {
    public long maxSubarrays(int n, int[][] conflictingPairs) {
        List<Integer>[] g = new List[n + 1];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (int[] pair : conflictingPairs) {
            int a = pair[0], b = pair[1];
            if (a > b) {
                int c = a;
                a = b;
                b = c;
            }
            g[a].add(b);
        }
        long[] cnt = new long[n + 2];
        long ans = 0, add = 0;
        int b1 = n + 1, b2 = n + 1;
        for (int a = n; a > 0; --a) {
            for (int b : g[a]) {
                if (b < b1) {
                    b2 = b1;
                    b1 = b;
                } else if (b < b2) {
                    b2 = b;
                }
            }
            ans += b1 - a;
            cnt[b1] += b2 - b1;
            add = Math.max(add, cnt[b1]);
        }
        ans += add;
        return ans;
    }
}

class Solution {
public:
    long long maxSubarrays(int n, vector<vector<int>>& conflictingPairs) {
        vector<vector<int>> g(n + 1);
        for (auto& pair : conflictingPairs) {
            int a = pair[0], b = pair[1];
            if (a > b) {
                swap(a, b);
            }
            g[a].push_back(b);
        }

        vector<long long> cnt(n + 2, 0);
        long long ans = 0, add = 0;
        int b1 = n + 1, b2 = n + 1;

        for (int a = n; a > 0; --a) {
            for (int b : g[a]) {
                if (b < b1) {
                    b2 = b1;
                    b1 = b;
                } else if (b < b2) {
                    b2 = b;
                }
            }
            ans += b1 - a;
            cnt[b1] += b2 - b1;
            add = max(add, cnt[b1]);
        }

        ans += add;
        return ans;
    }
};

func maxSubarrays(n int, conflictingPairs [][]int) (ans int64) {
    g := make([][]int, n+1)
    for _, pair := range conflictingPairs {
        a, b := pair[0], pair[1]
        if a > b {
            a, b = b, a
        }
        g[a] = append(g[a], b)
    }

    cnt := make([]int64, n+2)
    var add int64
    b1, b2 := n+1, n+1

    for a := n; a > 0; a-- {
        for _, b := range g[a] {
            if b < b1 {
                b2 = b1
                b1 = b
            } else if b < b2 {
                b2 = b
            }
        }
        ans += int64(b1 - a)
        cnt[b1] += int64(b2 - b1)
        if cnt[b1] > add {
            add = cnt[b1]
        }
    }

    ans += add
    return ans
}

function maxSubarrays(n: number, conflictingPairs: number[][]): number {
    const g: number[][] = Array.from({ length: n + 1 }, () => []);
    for (let [a, b] of conflictingPairs) {
        if (a > b) {
            [a, b] = [b, a];
        }
        g[a].push(b);
    }

    const cnt: number[] = Array(n + 2).fill(0);
    let ans = 0,
        add = 0;
    let b1 = n + 1,
        b2 = n + 1;

    for (let a = n; a > 0; a--) {
        for (const b of g[a]) {
            if (b < b1) {
                b2 = b1;
                b1 = b;
            } else if (b < b2) {
                b2 = b;
            }
        }
        ans += b1 - a;
        cnt[b1] += b2 - b1;
        add = Math.max(add, cnt[b1]);
    }

    ans += add;
    return ans;
}

impl Solution {
    pub fn max_subarrays(n: i32, conflicting_pairs: Vec<Vec<i32>>) -> i64 {
        let mut g: Vec<Vec<i32>> = vec![vec![]; (n + 1) as usize];
        for pair in conflicting_pairs {
            let mut a = pair[0];
            let mut b = pair[1];
            if a > b {
                std::mem::swap(&mut a, &mut b);
            }
            g[a as usize].push(b);
        }

        let mut cnt: Vec<i64> = vec![0; (n + 2) as usize];
        let mut ans = 0i64;
        let mut add = 0i64;
        let mut b1 = n + 1;
        let mut b2 = n + 1;

        for a in (1..=n).rev() {
            for &b in &g[a as usize] {
                if b < b1 {
                    b2 = b1;
                    b1 = b;
                } else if b < b2 {
                    b2 = b;
                }
            }
            ans += (b1 - a) as i64;
            cnt[b1 as usize] += (b2 - b1) as i64;
            add = std::cmp::max(add, cnt[b1 as usize]);
        }

        ans += add;
        ans
    }
}

3480. Maximize Subarrays After Removing One Conflicting Pair

Description

Solutions

Solution 1: Enumeration + Maintaining Minimum and Second Minimum Values

Comments