3480. Maximize Subarrays After Removing One Conflicting Pair

Time: O(n + m)

Space: O(n)

Approach

For each conflicting pair track contribution; try removing each pair and maximize total subarrays.

Key Techniques

Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.

Segment Tree

Segment trees support range queries (sum, min, max, GCD) and point updates in O(log n). Build in O(n) by filling leaves, then propagating upward. Lazy propagation enables range updates in O(log n) as well. Use for competitive programming range-query problems.

3480.cs

// Approach: For each conflicting pair track contribution; try removing each pair and maximize total subarrays.
// Time: O(n + m) Space: O(n)

public class Solution
{
    public long MaxSubarrays(int n, int[][] conflictingPairs)
    {
        long validSubarrays = 0;
        int maxLeft = 0;
        int secondMaxLeft = 0;
        // gains[i] := the number of additional valid subarrays we can gain if the
        // restriction at index `i` is removed
        long[] gains = new long[n + 1];
        // conflicts[r] := left endpoints that conflict with subarrays ending in r
        List<int>[] conflicts = new List<int>[n + 1];

        for (int i = 0; i <= n; ++i)
            conflicts[i] = new List<int>();

        foreach (var pair in conflictingPairs)
        {
            int a = pair[0];
            int b = pair[1];
            conflicts[Math.Max(a, b)].Add(Math.Min(a, b));
        }

        for (int right = 1; right <= n; ++right)
        {
            foreach (int left in conflicts[right])
            {
                if (left > maxLeft)
                {
                    secondMaxLeft = maxLeft;
                    maxLeft = left;
                }
                else if (left > secondMaxLeft)
                    secondMaxLeft = left;
            }
            // Subarrays [maxLeft + 1..right],
            //           [maxLeft + 2..right],
            //           ...
            //           [right..right] are valid.
            validSubarrays += right - maxLeft;
            // If we remove `maxLeft` (the most restrictive conflict), we gain
            // `maxLeft - secondMaxLeft` new subarrays:
            // [secondMaxLeft + 1..right],
            // [secondMaxLeft + 2..right],
            // ...
            // [maxLeft..right].
            gains[maxLeft] += maxLeft - secondMaxLeft;
        }

        return validSubarrays + gains.Max();
    }
}

Was this solution helpful?