# Maximize Subarrays After Removing One Conflicting Pair
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximize-subarrays-after-removing-one-conflicting-pair)
Canonical: https://scaleengineer.com/dsa/problems/maximize-subarrays-after-removing-one-conflicting-pair
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Segment Tree
---
## 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.

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

# Approaches
## Brute Force by Re-calculating for Each Removed Pair
This approach directly simulates the problem statement. It iterates through each conflicting pair, assumes it's the one to be removed, and then calculates the total number of valid subarrays for the remaining set of conflicting pairs. The maximum count found across all these simulations is the result.
**Time:** O(m * (n + m)). The outer loop runs `m` times. Inside the loop, creating the list of pairs takes `O(m)`, computing `end_points` takes `O(m)`, computing `limit` takes `O(n)`, and summing the counts takes `O(n)`. Thus, each iteration is `O(n+m)`. Since `m` can be up to `2n`, this is effectively O(n^2). · **Space:** O(n + m), where `n` is the number of elements and `m` is the number of conflicting pairs. This is for storing the temporary list of pairs and the `end_points` and `limit` arrays.
**Pros:** Conceptually straightforward and follows the problem statement directly.; Easier to implement correctly compared to more optimized solutions.
**Cons:** The time complexity of O(m * (n+m)) is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error.
### Explanation
The fundamental idea is to test every possible scenario. There are `m` (length of `conflictingPairs`) pairs, so there are `m` scenarios, one for each pair being removed.

For a given set of conflicting pairs, we can count the number of valid subarrays. A subarray `nums[i...j]` is valid if for every conflicting pair `(a, b)` in the set, the subarray does not contain both `a` and `b`. Let's assume `u = min(a,b)` and `v = max(a,b)`. The condition for a conflict is that the subarray starting at index `i` and ending at `j` must contain both `u` (at index `u-1`) and `v` (at index `v-1`), which means `i <= u-1` and `j >= v-1`.

To count valid subarrays, we can iterate through each possible starting index `i` from `0` to `n-1`. For each `i`, we need to find the maximum possible ending index `j` such that `nums[i...j]` is valid. This means for all remaining conflicting pairs `(u, v)`, it's not the case that `i <= u-1` and `j >= v-1`. This is equivalent to `j < v-1` for all pairs `(u,v)` where `u-1 >= i`. Therefore, for a fixed `i`, `j` must be less than `limit[i] = min({v-1 | (u,v) is a conflict, u-1 >= i})`. The number of valid subarrays starting at `i` is `limit[i] - i`.

The `limit` array can be computed in `O(n+m)` time. We first build an `end_points` array where `end_points[k]` stores the minimum `v-1` for all pairs starting at `k`. Then, `limit[i]` can be found with a backward pass: `limit[i] = min(limit[i+1], end_points[i])`.

Since we repeat this `O(n+m)` calculation for each of the `m` pairs to be removed, the total complexity is `O(m * (n+m))`.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int maximizeSubarrays(int n, int[][] conflictingPairs) {
        long maxSubarrays = 0;
        int m = conflictingPairs.length;
        if (m == 0) {
            return (int)((long)n * (n + 1) / 2);
        }

        for (int i = 0; i < m; i++) {
            // Step 2a: Create a list of pairs excluding the i-th pair
            List<int[]> currentPairs = new ArrayList<>();
            for (int j = 0; j < m; j++) {
                if (i == j) continue;
                currentPairs.add(conflictingPairs[j]);
            }

            // Step 2b: Compute limit array
            int[] endPoints = new int[n];
            Arrays.fill(endPoints, n);
            for (int[] pair : currentPairs) {
                int u = Math.min(pair[0], pair[1]);
                int v = Math.max(pair[0], pair[1]);
                endPoints[u - 1] = Math.min(endPoints[u - 1], v - 1);
            }

            int[] limit = new int[n];
            if (n > 0) {
                limit[n - 1] = endPoints[n - 1];
                for (int j = n - 2; j >= 0; j--) {
                    limit[j] = Math.min(limit[j + 1], endPoints[j]);
                }
            }

            // Step 2c: Calculate current count
            long currentCount = 0;
            for (int j = 0; j < n; j++) {
                currentCount += Math.max(0, limit[j] - j);
            }
            
            // Step 2d: Update max
            maxSubarrays = Math.max(maxSubarrays, currentCount);
        }

        return (int)maxSubarrays;
    }
}
```
### Algorithm
- Initialize `max_subarrays` to 0.
- Iterate through each pair `c_k` in `conflictingPairs` to select it for removal.
- In each iteration, create a temporary list of the other `m-1` conflicting pairs.
- For this temporary list, calculate the total number of valid subarrays:
  - Create an `end_points` array of size `n`, initialized to `n`. For each pair `(u, v)` (with `u < v`) in the temporary list, update `end_points[u-1] = min(end_points[u-1], v-1)`.
  - Compute a `limit` array of size `n`. `limit[i]` represents the maximum valid end index `j` for a subarray starting at `i`. This is calculated by iterating backwards: `limit[n-1] = end_points[n-1]` and `limit[i] = min(limit[i+1], end_points[i])`.
  - The number of valid subarrays for the current set of pairs is `sum_{i=0 to n-1} (limit[i] - i)`.
- Update `max_subarrays` with the maximum count found.
- Return `max_subarrays`.

## Optimized Approach with Pre-computation and Incremental Gain
This optimized approach avoids redundant calculations by pre-computing necessary information. It first calculates a baseline count of valid subarrays assuming no pairs are removed. Then, for each pair, it calculates the 'gain' in valid subarrays if that specific pair were to be removed. The gain is the number of subarrays that were previously invalid *only* because of this one pair. By using clever pre-computation, including prefix sums and maps, the gain for each pair can be found very quickly, leading to an efficient overall solution.
**Time:** O(n + m log m). Sorting pairs for each start point takes `O(m log d_max)` where `d_max` is max degree, worst case `O(m log m)`. Computing `ep`, `min`, and `base_count` takes `O(n)`. Building the maps and prefix sums takes `O(n)`. The final loop runs `m` times, with each iteration taking `O(log n)` for binary search. The dominant factor is typically the initial sorting of pairs. · **Space:** O(n + m). The adjacency list `adj` takes `O(m)` space. The `ep`, `min1`, `min2` arrays take `O(n)`. The maps for pre-computation store a total of `n` indices and `n` prefix sum values across all keys, so they also take `O(n)` space.
**Pros:** Highly efficient with a time complexity that passes the given constraints.; Reduces redundant work by calculating a base value and then an incremental gain.
**Cons:** Significantly more complex to understand and implement.; Requires careful handling of multiple data structures and pre-computation steps.
### Explanation
Instead of re-computing from scratch, we can express the answer as a base value plus an improvement. Let `C` be the full set of conflicting pairs and `c_k` be the pair we remove.
The number of valid subarrays for `C - {c_k}` is `count(C) + gain(c_k)`.

`count(C)` is the base number of valid subarrays. A subarray `nums[i...j]` is valid for `C` if `j < min1[i]`, where `min1[i]` is the minimum `v-1` over all pairs `(u,v) 
in C` with `u-1 >= i`. The base count is `sum_{i=0 to n-1} (min1[i] - i)`.

`gain(c_k)` is the number of subarrays that become valid after removing `c_k`. These are the subarrays `nums[i...j]` that contain `c_k` but no other pair from `C`. This happens if `c_k` was the 'tightest' constraint for some starting indices `i`. Let `min2[i]` be the second-smallest `v-1` for pairs `(u,v)` with `u-1 >= i`. If we remove `c_k = (u_k, v_k)`, the limit `min1[i]` becomes `min2[i]` if and only if `v_k-1` was equal to `min1[i]`. This can only occur for `i <= u_k-1`.

The gain from removing `c_k` is `sum_{i | i <= u_k-1 and v_k-1 == min1[i]} (min2[i] - min1[i])`.

To calculate this sum efficiently for every `k`, we pre-compute `min1` and `min2` arrays. Then, we group all indices `i` based on the value of `min1[i]`. For each value `Y`, we have a list of indices where `min1[i] == Y`. We also pre-compute prefix sums of `min2[i] - min1[i]` for each of these lists. When calculating the gain for `c_k = (u_k, v_k)`, we look up the list for `Y = v_k-1`, use binary search to find how many indices in that list are `<= u_k-1`, and use the prefix sum array to get the total gain in `O(log n)` time.

```java
import java.util.*;

class Solution {
    public int maximizeSubarrays(int n, int[][] conflictingPairs) {
        int m = conflictingPairs.length;
        if (m == 0) {
            return (int)((long)n * (n + 1) / 2);
        }

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int[] p : conflictingPairs) {
            int u = Math.min(p[0], p[1]);
            int v = Math.max(p[0], p[1]);
            adj.get(u).add(v);
        }
        for (int i = 1; i <= n; i++) Collections.sort(adj.get(i));

        int[] ep1 = new int[n], ep2 = new int[n];
        Arrays.fill(ep1, n); Arrays.fill(ep2, n);
        for (int i = 1; i <= n; i++) {
            if (adj.get(i).size() > 0) ep1[i - 1] = adj.get(i).get(0) - 1;
            if (adj.get(i).size() > 1) ep2[i - 1] = adj.get(i).get(1) - 1;
        }

        int[] min1 = new int[n], min2 = new int[n];
        min1[n - 1] = ep1[n - 1];
        min2[n - 1] = ep2[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            int[] candidates = {min1[i + 1], min2[i + 1], ep1[i], ep2[i]};
            Arrays.sort(candidates);
            min1[i] = candidates[0];
            min2[i] = candidates[1];
        }

        long baseCount = 0;
        for (int i = 0; i < n; i++) baseCount += Math.max(0, min1[i] - i);

        Map<Integer, List<Integer>> valToIndices = new HashMap<>();
        Map<Integer, List<Long>> valToPrefixSums = new HashMap<>();
        for (int i = 0; i < n; i++) {
            valToIndices.computeIfAbsent(min1[i], k -> new ArrayList<>()).add(i);
        }

        for (Map.Entry<Integer, List<Integer>> entry : valToIndices.entrySet()) {
            int val = entry.getKey();
            List<Integer> indices = entry.getValue();
            List<Long> prefixSums = new ArrayList<>();
            long currentSum = 0;
            for (int idx : indices) {
                currentSum += (long)min2[idx] - min1[idx];
                prefixSums.add(currentSum);
            }
            valToPrefixSums.put(val, prefixSums);
        }

        long maxGain = 0;
        for (int[] p : conflictingPairs) {
            int u = Math.min(p[0], p[1]);
            int v = Math.max(p[0], p[1]);
            int y = v - 1;

            if (!valToIndices.containsKey(y)) continue;

            List<Integer> indices = valToIndices.get(y);
            int searchVal = u - 1;
            int low = 0, high = indices.size() - 1, p = -1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if (indices.get(mid) <= searchVal) {
                    p = mid;
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }

            if (p != -1) {
                maxGain = Math.max(maxGain, valToPrefixSums.get(y).get(p));
            }
        }

        return (int)(baseCount + maxGain);
    }
}
```
### Algorithm
- **Pre-computation:**
  - Normalize all pairs `(a,b)` to `(u,v)` where `u < v`. Group pairs by their starting point `u` and sort them by `v`.
  - For each starting index `i`, find `ep1[i]` and `ep2[i]`, the smallest and second-smallest `v-1` from pairs starting at `i+1`.
  - Compute `min1[i]` and `min2[i]` arrays. `min1[i]` is the smallest `v-1` among all pairs `(u,v)` with `u-1 >= i`, and `min2[i]` is the second smallest. These are computed in a single backward pass over `ep1` and `ep2`.
  - Calculate the `base_count` of valid subarrays with all pairs present: `sum_{i=0 to n-1} (min1[i] - i)`.
  - For efficiency, group indices `i` by the value of `min1[i]`. For each value group, create a prefix sum array of the potential gains `(min2[i] - min1[i])`.
- **Gain Calculation:**
  - Initialize `max_gain = 0`.
  - For each conflicting pair `c_k = (u_k, v_k)`:
    - The potential gain is non-zero only for indices `i <= u_k-1` where `min1[i] == v_k-1`.
    - Use the pre-computed map and prefix sums to find the total gain for this `c_k` in `O(log n)` time via binary search.
    - Update `max_gain = max(max_gain, current_gain)`.
- **Result:**
  - The final answer is `base_count + max_gain`.