Maximize Subarrays After Removing One Conflicting Pair - Solution & Explanation

Problem Overview: You are given n elements and a list of conflicting pairs (a, b). Any subarray containing both values of a conflicting pair is invalid. You may remove exactly one conflicting pair from the list. The task is to maximize the number of valid subarrays that remain.

Approach 1: Brute Force Pair Removal + Subarray Validation (O(n² * m) time, O(1) space)

Try removing each conflicting pair one at a time. For the remaining pairs, enumerate every possible subarray and check whether it contains both elements of any conflict. This requires scanning the subarray or tracking membership, making each validation expensive. The approach demonstrates the problem structure but becomes infeasible when n and the number of pairs grow. It mainly helps you reason about how conflicting pairs limit valid subarray boundaries.

Approach 2: Enumeration + Maintaining Minimum and Second Minimum Values (O(n + m) time, O(n) space)

The key observation: for a subarray ending at position r, the earliest valid start depends on the largest conflicting left endpoint among all pairs whose right endpoint is ≤ r. If the maximum left value is max1, any subarray must start after max1. That gives r - max1 valid subarrays ending at r.

Group conflicts by their right endpoint and iterate r from 1..n. While processing, maintain the largest and second-largest left endpoints seen so far. The largest value defines the current restriction for valid subarrays. The second-largest becomes relevant if the pair causing the largest restriction is removed.

For every index r, add r - max1 to the base answer. The improvement from removing the dominant pair equals max1 - max2, because the boundary shifts from max1 to max2. Accumulate this potential gain for the pair responsible for max1. After scanning the array, add the maximum gain to the base count.

This technique combines ideas from Array enumeration and prefix tracking similar to Prefix Sum style accumulation. The ordering of constraints acts like a simplified structure compared to a full Segment Tree, which would otherwise maintain range restrictions dynamically.

Recommended for interviews: The enumeration with maintained maximum and second maximum constraints is the expected solution. It reduces the problem to a linear scan and demonstrates strong reasoning about how conflicts restrict subarray boundaries. Mentioning the brute force idea first shows you understand the constraint interactions before optimizing.