Skip to content

3362. Zero Array Transformation III 👍

  • Time: $O(n + q\log q)$
  • Space: $O(q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
    int queryIndex = 0;
    priority_queue<int> available;                        // available `r`s
    priority_queue<int, vector<int>, greater<>> running;  // running `r`s

    ranges::sort(queries);

    for (int i = 0; i < nums.size(); ++i) {
      while (queryIndex < queries.size() && queries[queryIndex][0] <= i)
        available.push(queries[queryIndex++][1]);
      while (!running.empty() && running.top() < i)
        running.pop();
      while (nums[i] > running.size()) {
        if (available.empty() || available.top() < i)
          return -1;
        running.push(available.top()), available.pop();
      }
    }

    return available.size();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int maxRemoval(int[] nums, int[][] queries) {
    int queryIndex = 0;
    Queue<Integer> available = new PriorityQueue<>(Collections.reverseOrder()); // available `r`s
    Queue<Integer> running = new PriorityQueue<>();                             // running `r`s

    Arrays.sort(queries, Comparator.comparingInt((int[] query) -> query[0]));

    for (int i = 0; i < nums.length; ++i) {
      while (queryIndex < queries.length && queries[queryIndex][0] <= i)
        available.offer(queries[queryIndex++][1]);
      while (!running.isEmpty() && running.peek() < i)
        running.poll();
      while (nums[i] > running.size()) {
        if (available.isEmpty() || available.peek() < i)
          return -1;
        running.offer(available.poll());
      }
    }

    return available.size();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
from sortedcontainers import SortedList


class Solution:
  def maxRemoval(self, nums: list[int], queries: list[list[int]]) -> int:
    q = collections.deque(sorted(queries))
    available = SortedList()  # available `r`s
    running = SortedList()  # running `r`s

    for i, num in enumerate(nums):
      while q and q[0][0] <= i:
        available.add(q.popleft()[1])
      while running and running[0] < i:
        running.pop(0)
      while num > len(running):
        if not available or available[-1] < i:
          return -1
        running.add(available.pop())

    return len(available)