DDSA Solutions

3362. Zero Array Transformation III

UnknownView on LeetCode
ArrayGreedyHeap (Priority Queue)

Problem Overview

Count subarrays where both zero count and one count are divisible by k.

Intuition

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

Algorithm

  1. 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?

Related Problems