Maximize subarrays after removing one conflicting pair

Array Segment Tree Enumeration Prefix Sum

64.7% acceptance

Mar 10, 2026

305

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn max_subarrays(n: i32, conflicting_pairs: Vec<Vec<i32>>) -> i64 {
    let n = n as usize;

    // Normalize: for each pair [a,b], ensure a < b (swap if needed).
    // Group left endpoints by their right endpoint b.
    let mut pair_at: Vec<Vec<usize>> = vec![vec![]; n + 1]; // pair_at[b] = [a, ...]
    for p in &conflicting_pairs {
      let (a, b) = (p[0] as usize, p[1] as usize);
      let (a, b) = if a < b { (a, b) } else { (b, a) };
      pair_at[b].push(a);
    }

    // O(n + m) sweep: for each r from 1..=n, maintain the top-2 maximum `a` values
    // seen so far (from all pairs with b <= r).
    //
    // Key insight:
    //   - base count at r  = r - top1_a   (valid subarrays [top1_a+1..r], [top1_a+2..r], …)
    //   - removing P1 (the pair achieving top1_a) gains (top1_a - top2_a) extra subarrays at r.
    //
    // So we accumulate bonus[P1] += top1_a - top2_a at each r, then the answer is
    // total_base + max(bonus[*]).
    //
    // When a new pair at r has a >= top1_a (tie), update top2_a = top1_a so removing P1
    // gives 0 gain (the tie-pair still dominates).

    // O(1) bonus tracking: since the dominant pair (p1) can only be displaced by a
    // strictly larger `a`, we finalize cur_bonus into max_bonus whenever p1 changes.
    let mut top1_a: usize = 0;
    let mut top2_a: usize = 0;
    let mut has_p1 = false;
    let mut cur_bonus = 0i64;
    let mut max_bonus = 0i64;
    let mut total_base = 0i64;

    for r in 1..=n {
      // Process all new pairs arriving at this right endpoint.
      for &a in &pair_at[r] {
        if a > top1_a {
          // New dominant pair: finalize the outgoing p1's accumulated bonus.
          if has_p1 {
            max_bonus = max_bonus.max(cur_bonus);
            cur_bonus = 0;
          }
          top2_a = top1_a;
          top1_a = a;
          has_p1 = true;
        } else if a >= top2_a {
          // Tie with top1_a sets top2_a = top1_a → future gain for p1 is 0.
          top2_a = a;
        }
      }
      // Count valid subarrays ending at r: l can be top1_a+1 .. r.
      total_base += (r - top1_a) as i64;
      // Accumulate gain from removing the current dominant pair at this r.
      if has_p1 {
        cur_bonus += (top1_a - top2_a) as i64;
      }
    }

    max_bonus = max_bonus.max(cur_bonus);
    total_base + max_bonus
  }
}