Tap here to switch tabs
Problem
Submissions

Problem: Maximize Subarrays After Removing One Conflicting Pair

Maximize Subarrays After Removing One Conflicting Pair asks for the maximum number of contiguous subarrays in one-to-n that avoid both values of every remaining pair, after removing at most one pair.

Statement

You are given an integer n representing an array containing the sequence of integers from 11 to n in increasing order.

You are also given a 22D integer array conflictingPairs, where each conflictingPairs[i] = [a, b] represents a pair of conflicting numbers.

A contiguous subarray is considered valid if it does not contain both elements of any conflicting pair present in conflictingPairs.

You may remove at most one conflicting pair from conflictingPairs.

Return the maximum possible number of valid subarrays after removing at most one conflicting pair.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • 1≤1 \leq conflictingPairs.length ≤2imes\leq 2 imes n

  • conflictingPairs[i].length =2= 2

  • 1≤1 \leq conflictingPairs[i][j] ≤\leq n

  • conflictingPairs[i][0] ≠\neq conflictingPairs[i][1]

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Maximize Subarrays After Removing One Conflicting Pair

Maximize Subarrays After Removing One Conflicting Pair asks for the maximum number of contiguous subarrays in one-to-n that avoid both values of every remaining pair, after removing at most one pair.

Statement

You are given an integer n representing an array containing the sequence of integers from 11 to n in increasing order.

You are also given a 22D integer array conflictingPairs, where each conflictingPairs[i] = [a, b] represents a pair of conflicting numbers.

A contiguous subarray is considered valid if it does not contain both elements of any conflicting pair present in conflictingPairs.

You may remove at most one conflicting pair from conflictingPairs.

Return the maximum possible number of valid subarrays after removing at most one conflicting pair.

Constraints:

  • 2≤2 \leq n ≤105\leq 10^5

  • 1≤1 \leq conflictingPairs.length ≤2imes\leq 2 imes n

  • conflictingPairs[i].length =2= 2

  • 1≤1 \leq conflictingPairs[i][j] ≤\leq n

  • conflictingPairs[i][0] ≠\neq conflictingPairs[i][1]