[Leetcode] 3362. Zero Array Transformation III (retry V HARD)

https://leetcode.com/problems/zero-array-transformation-iii/description/?envType=daily-question&envId=2025-05-22

initial

class Solution {
    public int maxRemoval(int[] nums, int[][] queries) {

        Arrays.sort(queries, (a, b) -> {
            if (a[1] != b[1]) {
                return b[1] - a[1];
            } else {
                return a[0] - b[1];
            }
        });

        int ans = 0;
        int n = queries.length;

        for (int[] row : queries) {
            System.out.println(Arrays.toString(row));
            int start = row[0];
            int end = row[1];
            boolean check = false;
            boolean flag = false;

            for (int i = 0; i < nums.length; i++) {
                if (start <= i && i <= end) {
                    if (nums[i] != 0) check = true;
                    nums[i] = Math.max(0, nums[i] - 1);
                }
                if (nums[i] != 0) flag = true;
            }

            if (!check) {
                if (!flag) return n - ans;
                continue;
            }

            ans += 1;

            if (!flag) return n - ans;
        }

        return -1;
    }
}

my intial approach was to sort via the largest interval of range. But as u see i needed so many flags to counter edge cases. Still it didnt work cuz if we have

nums =
[0,0,1,1,0]
queries =
[[3,4],[0,2],[2,3]]

Use Testcase
Stdout
[3, 4]
[2, 3]
Output
1
Expected
2

the real reason why mine doesnt work is that I am not actually dealing with the demand for each index in the nums. I am just greedily applying the largest interval range onto the nums.

acc to gpt
You’re using a local greedy choice based on sorted query end, which does not guarantee a global optimal solution.

You’re not ensuring that each nums[i] meets its demand, just that you’re applying queries to some valid ranges without knowing which indices are most constrained.

So there is a limit to my sol.

sol

As mentioned, we need to consider the actual demand for each index. We build a pool of available queries in a heap pool that have starting index less than or equal to the current index cuz that query can affect the current index.

Notice that we are updating the query pool along the way. This is very efficient. Then, if the current accumulated frequency of quries is less than the value at that particular index, then we dont have enough quries. We need to pool one query from the heap pool of queries. But if max heap is empty or the max heap (which stores ending index) has a lower value than i, it means queries in pool cannot affect the index i. So we return -1.

Also line sweep is done here like not doing [1,1,1,1,0] but [1,0,0,0,0,-1] just marking start and end+1 index.

We minus end[i] at each i iteration to remove expired queries that do not affect our index i now.

ocmplexity

sort is q log q and n iteration so q log q +n time
n space