Maximize Subarrays After Removing One Conflicting Pair

Maximize Subarrays After Removing One Conflicting Pair - 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.

Input & Output

Example 1 — Basic Case

$ Input: n = 5, conflictingPairs = [[1,5], [2,3]]

› Output: 9

💡 Note: Remove [2,3] to get max subarrays. With only [1,5] remaining, we avoid subarrays containing both 1 and 5. Valid count: total 15 minus 1×1=1 invalid equals 14, but removing [1,5] gives 15-2×3=9.

Example 2 — Single Pair

$ Input: n = 4, conflictingPairs = [[2,4]]

› Output: 10

💡 Note: Only one pair to remove [2,4]. Total subarrays = 4×5/2 = 10. After removal, no constraints remain, so all 10 subarrays are valid.

Example 3 — Multiple Pairs

$ Input: n = 3, conflictingPairs = [[1,2], [2,3]]

› Output: 4

💡 Note: Remove [1,2] keeps [2,3]. Invalid subarrays contain both 2 and 3: positions 2×2=4, but total is only 6, so 6-2=4 valid. Remove [2,3] keeps [1,2]: 6-2=4 valid. Both give same result.

Constraints

2 ≤ n ≤ 10⁵
1 ≤ conflictingPairs.length ≤ 10⁵
conflictingPairs[i].length == 2
1 ≤ conflictingPairs[i][0], conflictingPairs[i][1] ≤ n
conflictingPairs[i][0] ≠ conflictingPairs[i][1]

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,3,4,5] with conflicting pairs [[1,5],[2,4]]

Process

Try removing each pair and count valid subarrays

Output

Maximum valid subarray count after optimal pair removal

Key Takeaway

🎯 Key Insight: Each conflicting pair restricts different subarrays - remove the most restrictive one

Asked in

G Google 25 M Microsoft 15 a Amazon 10

The key insight is that removing different conflicting pairs results in different numbers of valid subarrays. We can use mathematical formulas to count valid subarrays efficiently: total subarrays minus invalid ones. Best approach uses mathematical counting instead of enumeration. Time: O(k²n), Space: O(k)

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Formula Approach	O(k²n)	O(k)	Use math to count valid subarrays without enumeration
Brute Force Enumeration	O(n⁴)	O(1)	Try removing each pair and count all valid subarrays

Mathematical Formula Approach — Algorithm Steps

Calculate total possible subarrays: n(n+1)/2
For each pair removal, count invalid subarrays using math
Use inclusion-exclusion for overlapping constraints
Return maximum valid count

Visualization

Tap to expand

Step-by-Step Walkthrough

Total Count

Calculate total subarrays: n(n+1)/2

Invalid Count

Count subarrays violating remaining constraints

Valid Count

Valid = Total - Invalid

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int solution(int n, int conflictingPairs[][2], int pairCount) {
    int totalSubarrays = n * (n + 1) / 2;
    int maxValid = 0;
    
    for (int removeIdx = 0; removeIdx < pairCount; removeIdx++) {
        int invalidCount = 0;
        
        for (int k = 0; k < pairCount; k++) {
            if (k == removeIdx) continue;
            
            int a = min(conflictingPairs[k][0], conflictingPairs[k][1]);
            int b = max(conflictingPairs[k][0], conflictingPairs[k][1]);
            
            int leftChoices = a;
            int rightChoices = n - b + 1;
            invalidCount += leftChoices * rightChoices;
        }
        
        int validCount = totalSubarrays - invalidCount;
        if (validCount > maxValid) {
            maxValid = validCount;
        }
    }
    
    return maxValid;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    int conflictingPairs[100][2];
    int pairCount = 0;
    
    char* ptr = line + 1;
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            int a = 0, b = 0;
            while (*ptr >= '0' && *ptr <= '9') {
                a = a * 10 + (*ptr - '0');
                ptr++;
            }
            ptr++;
            while (*ptr >= '0' && *ptr <= '9') {
                b = b * 10 + (*ptr - '0');
                ptr++;
            }
            conflictingPairs[pairCount][0] = a;
            conflictingPairs[pairCount][1] = b;
            pairCount++;
            ptr++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(n, conflictingPairs, pairCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k²n)

O(k) pairs to try × O(k×n) to calculate invalid subarrays using inclusion-exclusion

✓ Linear Growth

Space Complexity

O(k)

Store remaining pairs and intermediate calculations

✓ Linear Space

27.7K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Formula Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler