Maximize Subarrays After Removing One Conflicting Pair

• 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.

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)).

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4 5class Solution {6    public int maximizeSubarrays(int n, int[][] conflictingPairs) {7        long maxSubarrays = 0;8        int m = conflictingPairs.length;9        if (m == 0) {10            return (int)((long)n * (n + 1) / 2);11        }12 13        for (int i = 0; i < m; i++) {14            // Step 2a: Create a list of pairs excluding the i-th pair15            List<int[]> currentPairs = new ArrayList<>();16            for (int j = 0; j < m; j++) {17                if (i == j) continue;18                currentPairs.add(conflictingPairs[j]);19            }20 21            // Step 2b: Compute limit array22            int[] endPoints = new int[n];23            Arrays.fill(endPoints, n);24            for (int[] pair : currentPairs) {25                int u = Math.min(pair[0], pair[1]);26                int v = Math.max(pair[0], pair[1]);27                endPoints[u - 1] = Math.min(endPoints[u - 1], v - 1);28            }29 30            int[] limit = new int[n];31            if (n > 0) {32                limit[n - 1] = endPoints[n - 1];33                for (int j = n - 2; j >= 0; j--) {34                    limit[j] = Math.min(limit[j + 1], endPoints[j]);35                }36            }37 38            // Step 2c: Calculate current count39            long currentCount = 0;40            for (int j = 0; j < n; j++) {41                currentCount += Math.max(0, limit[j] - j);42            }43            44            // Step 2d: Update max45            maxSubarrays = Math.max(maxSubarrays, currentCount);46        }47 48        return (int)maxSubarrays;49    }50}

• 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.

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.

1import java.util.*;2 3class Solution {4    public int maximizeSubarrays(int n, int[][] conflictingPairs) {5        int m = conflictingPairs.length;6        if (m == 0) {7            return (int)((long)n * (n + 1) / 2);8        }9 10        List<List<Integer>> adj = new ArrayList<>();11        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());12        for (int[] p : conflictingPairs) {13            int u = Math.min(p[0], p[1]);14            int v = Math.max(p[0], p[1]);15            adj.get(u).add(v);16        }17        for (int i = 1; i <= n; i++) Collections.sort(adj.get(i));18 19        int[] ep1 = new int[n], ep2 = new int[n];20        Arrays.fill(ep1, n); Arrays.fill(ep2, n);21        for (int i = 1; i <= n; i++) {22            if (adj.get(i).size() > 0) ep1[i - 1] = adj.get(i).get(0) - 1;23            if (adj.get(i).size() > 1) ep2[i - 1] = adj.get(i).get(1) - 1;24        }25 26        int[] min1 = new int[n], min2 = new int[n];27        min1[n - 1] = ep1[n - 1];28        min2[n - 1] = ep2[n - 1];29        for (int i = n - 2; i >= 0; i--) {30            int[] candidates = {min1[i + 1], min2[i + 1], ep1[i], ep2[i]};31            Arrays.sort(candidates);32            min1[i] = candidates[0];33            min2[i] = candidates[1];34        }35 36        long baseCount = 0;37        for (int i = 0; i < n; i++) baseCount += Math.max(0, min1[i] - i);38 39        Map<Integer, List<Integer>> valToIndices = new HashMap<>();40        Map<Integer, List<Long>> valToPrefixSums = new HashMap<>();41        for (int i = 0; i < n; i++) {42            valToIndices.computeIfAbsent(min1[i], k -> new ArrayList<>()).add(i);43        }44 45        for (Map.Entry<Integer, List<Integer>> entry : valToIndices.entrySet()) {46            int val = entry.getKey();47            List<Integer> indices = entry.getValue();48            List<Long> prefixSums = new ArrayList<>();49            long currentSum = 0;50            for (int idx : indices) {51                currentSum += (long)min2[idx] - min1[idx];52                prefixSums.add(currentSum);53            }54            valToPrefixSums.put(val, prefixSums);55        }56 57        long maxGain = 0;58        for (int[] p : conflictingPairs) {59            int u = Math.min(p[0], p[1]);60            int v = Math.max(p[0], p[1]);61            int y = v - 1;62 63            if (!valToIndices.containsKey(y)) continue;64 65            List<Integer> indices = valToIndices.get(y);66            int searchVal = u - 1;67            int low = 0, high = indices.size() - 1, p = -1;68            while (low <= high) {69                int mid = low + (high - low) / 2;70                if (indices.get(mid) <= searchVal) {71                    p = mid;72                    low = mid + 1;73                } else {74                    high = mid - 1;75                }76            }77 78            if (p != -1) {79                maxGain = Math.max(maxGain, valToPrefixSums.get(y).get(p));80            }81        }82 83        return (int)(baseCount + maxGain);84    }85}