3362. Zero Array Transformation III

UnknownView on LeetCode

Array Greedy Heap (Priority Queue)

Intuition

Count subarrays where both zero count and one count are divisible by k. Prefix sum modulo k tracking.

Algorithm

1Track (zeros%k, ones%k) at each prefix. Count pairs with same (zeros%k, ones%k) value.

Common Pitfalls

•State = (count_zeros%k, count_ones%k). Count pairs with matching states using hashmap.

3362.java

Java

import java.util.*;

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();
    }
}

Was this solution helpful?