We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize Subarrays After Removing One Conflicting Pair

Number: 3789

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given an integer n, we have an array nums = [1, 2, …, n] and a list of conflicting pairs. Each pair [a, b] (with a ≠ b) is “conflicting” in the sense that in any subarray the two numbers a and b must not both appear. Before counting, you are allowed to remove exactly one conflicting pair from the list. After that, count the number of non‐empty subarrays of nums that do not contain both numbers from any remaining conflicting pair. Return the maximum possible count achievable by removing exactly one conflicting pair.

For example, if n=4 with conflictingPairs = [[2,3],[1,4]]: • Removing [2,3] leaves [[1,4]]. In nums = [1,2,3,4] every subarray that “covers” the interval [1,4] (i.e. with start ≤ 1 and end ≥ 4) is invalid. The valid subarrays turn out to be 9 in total. • Removing [1,4] gives a different (smaller) total. Thus the answer is 9.

Key Insights

  • Because nums is fixed and sorted (1 to n), any conflicting pair [a, b] (we define L = min(a, b) and R = max(a, b)) “forces” subarrays that “cover” the interval [L, R] to be invalid.
  • For a fixed starting index i, only those forbidden intervals with L ≥ i matter. In particular, a subarray starting at i is valid only if its ending index j is less than min{R among all intervals with L ≥ i}.
  • Hence, if we denote f(i) = min(n+1, min_{forbidden interval with L ≥ i} R), the number of valid subarrays starting at i is (f(i) – i) (because j can go from i to f(i)–1).
  • If we remove a particular conflict [L₀, R₀] and that conflict contributed as the “tightest” (i.e. minimal R) constraint for some starting positions i (necessarily with i ≤ L₀), then for those i the allowed j gets “lifted” to the second‐smallest R. In other words, the gain (delta) at index i is (secondR(i) – R₀).
  • Thus the overall valid subarray count after removing a candidate conflict x is “base_total” (when all conflicts are present) plus the sum of deltas over those indices where x was the one imposing the minimum constraint.
  • A dynamic programming (or sweep‐line) “backward” scan from i = n down to 1 can be used to compute, for every i, the two smallest R‐values among all conflicts with L ≥ i; the first gives f(i) and the second will be used if the “active” conflict is removed.
  • Then, for each candidate conflict, accumulate its contribution “delta” (only at positions i where it was the minimizer) and take the maximum overall removal option.

Space and Time Complexity

Time Complexity: O(n) overall (each index is processed once; note that the total number of conflict pairs is at most 2n and they are distributed by their L–values). Space Complexity: O(n) (to store the dp arrays and an auxiliary structure for conflict–pair intervals).

Solution

We first pre–process the conflictingPairs. For each conflicting pair [a,b] we define L = min(a,b) and R = max(a,b). For each start index i (from 1 to n) we record all conflict intervals that “start” at i (i.e. those with L = i) along with an id for the pair. Then we define dp[i] for i = 1 to n+1 as a tuple (first_val, first_id, second_val, second_id) representing the smallest and second–smallest R value among all conflicts with L ≥ i, along with which conflict (by id) gave that R. For i = n+1 we set dp[n+1] = (n+1, –1, n+1, –1) as no conflict exists. For i from n down to 1 we “merge” any conflict that starts at i with the answer from dp[i+1] (which covers conflicts starting at i+1, i+2, …). Because the number of conflicts starting at each index is small (and the total is ≤2n), we can simply merge (at most three candidates) and keep the two smallest based on R (using candidate id as a tie breaker if needed). Once computed the dp, the base valid subarray count (when no pair is removed) is base_total = sum_{i=1}^{n} (dp[i].first_val – i) since a subarray [i,j] is valid if j < dp[i].first_val. Next, for each index i we check if the chosen “first” conflict came from candidate x (i.e. dp[i].first_id != –1). If so, if that conflict were removed then at index i the allowed ending index would use dp[i].second_val instead. Thus, the gain is (dp[i].second_val – dp[i].first_val). For each candidate conflict x we sum these gains over all indices i where it was the minimizer. Finally our answer is the maximum over candidates of (base_total + delta[x]). Code for this approach is provided in several languages below.

Code Solutions

# Python solution
def maximizeSubarrays(n, conflictingPairs):
    # Preprocess: store intervals by their L = min(a, b) and R = max(a, b)
    # Also assign a unique id for each conflict.
    intervals_by_start = [[] for _ in range(n+1)]
    candidates = []  # store tuple (L, R) for candidate id
    for cid, pair in enumerate(conflictingPairs):
        a, b = pair
        L, R = (a, b) if a < b else (b, a)
        candidates.append((L, R))
        intervals_by_start[L].append((R, cid))  # conflict starts at L
    
    # dp[i] = (first_val, first_id, second_val, second_id)
    # represents the smallest and second smallest R among conflicts with L >= i.
    dp = [None]*(n+2)
    # Base case: no conflict for i = n+1, so fallback R = n+1.
    dp[n+1] = (n+1, -1, n+1, -1)
    
    # Process from i = n down to 1.
    for i in range(n, 0, -1):
        # candidates from intervals starting exactly at i:
        curr = []
        for (R, cid) in intervals_by_start[i]:
            curr.append((R, cid))
        # also include the two candidates from dp[i+1]
        # dp[i+1] is a tuple: (first, first_id, second, second_id)
        first_val, first_id, second_val, second_id = dp[i+1]
        curr.append((first_val, first_id))
        curr.append((second_val, second_id))
        # sort by R; tie-break using candidate id.
        curr.sort(key=lambda x: (x[0], x[1]))
        # pick the smallest and second smallest; if not enough, use fallback n+1.
        best = curr[0] if curr else (n+1, -1)
        second = curr[1] if len(curr) > 1 else (n+1, -1)
        dp[i] = (best[0], best[1], second[0], second[1])
    
    # Compute the base valid subarray count:
    # For starting index i, valid j are in [i, dp[i].first_val - 1].
    base_total = 0
    for i in range(1, n+1):
        base_total += dp[i][0] - i  # dp[i].first_val - i
    
    # For each candidate, sum the delta gains from indices where it was the minimizer.
    candidate_delta = [0]*len(candidates)
    for i in range(1, n+1):
        first_val, first_id, second_val, _ = dp[i]
        if first_id != -1:
            # If the candidate conflict provided the minimum R at i,
            # then if it is removed, the allowed j would be second_val - 1.
            # Thus gain at i is (second_val - first_val).
            candidate_delta[first_id] += (second_val - first_val)
    
    # Our answer for candidate x is base_total + candidate_delta[x].
    best_answer = 0
    for cid in range(len(candidates)):
        best_answer = max(best_answer, base_total + candidate_delta[cid])
    
    return best_answer

# Example usage:
#print(maximizeSubarrays(4, [[2,3],[1,4]]))  # Expected output: 9
#print(maximizeSubarrays(5, [[1,2],[2,5],[3,5]]))  # Expected output: 12
← Back to All Questions