2025-07-26 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's July LeetCoding Challenge with cpp.

July LeetCoding Challenge 26

Description

Maximize Subarrays After Removing One Conflicting Pair

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]

Solution

class Solution {
public:
  long long maxSubarrays(int n, vector<vector<int>>& conflictingPairs) {
    vector<int> bMin(n + 1, INT_MAX);
    vector<int> bSecondMin(n + 1, INT_MAX);

    for(const auto &p : conflictingPairs) {
      int a = min(p[0], p[1]);
      int b = max(p[0], p[1]);
      if(bMin[a] > b) {
        bSecondMin[a] = bMin[a];
        bMin[a] = b;
      } else if(bSecondMin[a] > b) {
        bSecondMin[a] = b;
      }
    }

    long long answer = 0;
    int indexBMin = n;
    int bSecondMinVal = INT_MAX;
    vector<long long> deleteCount(n + 1, 0);
    for(int i = n; i >= 1; --i) {
      if(bMin[indexBMin] > bMin[i]) {
        bSecondMinVal = min(bSecondMinVal, bMin[indexBMin]);
        indexBMin = i;
      } else {
        bSecondMinVal = min(bSecondMinVal, bMin[i]);
      }

      answer += min(bMin[indexBMin], n + 1) - i;
      deleteCount[indexBMin] += min({bSecondMinVal, bSecondMin[indexBMin], n + 1}) - min(bMin[indexBMin], n + 1);
    }

    return answer += *max_element(deleteCount.begin(), deleteCount.end());
  }
};

// Accepted
// 642/642 cases passed (57 ms)
// Your runtime beats 89.83 % of cpp submissions
// Your memory usage beats 83.05 % of cpp submissions (266.8 MB)
Algorithm