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

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;
    }
};

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

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

3480. Maximize Subarrays After Removing One Conflicting Pair

Description

Solutions

Solution 1

All Problems

All Solutions

Welcome to Subscribe On Youtube

3480. Maximize Subarrays After Removing One Conflicting Pair

Description

Solutions

Solution 1

All Problems

All Solutions