Photo by Chris Ried on Unsplash

LeetCode day318–3362

Everyday has one random leetcode quiz. Today’s quiz is 3362. Zero Array Transformation III

Description:

You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri].

Each queries[i] represents the following action on nums:

• Decrement the value at each index in the range [li, ri] in nums by at most 1.
• The amount by which the value is decremented can be chosen independently for each index.

A Zero Array is an array with all its elements equal to 0.

Return the maximum number of elements that can be removed from queries, such that nums can still be converted to a zero array using the remaining queries. If it is not possible to convert nums to a zero array, return -1.

Get Jimmy’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Example 1:

Input: nums = [2,0,2], queries = [[0,2],[0,2],[1,1]]

Output: 1

Explanation:

After removing queries[2], nums can still be converted to a zero array.

Using queries[0], decrement nums[0] and nums[2] by 1 and nums[1] by 0.
Using queries[1], decrement nums[0] and nums[2] by 1 and nums[1] by 0.

Example 2:

Input: nums = [1,1,1,1], queries = [[1,3],[0,2],[1,3],[1,2]]

Output: 2

Explanation:

We can remove queries[2] and queries[3].

Example 2:

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

Output: -1

Explanation:

nums cannot be converted to a zero array even after using all the queries.

We sort the queries by their start time.

For each index, check and execute the queries that start at that index.

If the current number of operations is less than the required number at that index, return -1. Otherwise, return the number of remaining queries as the answer.

If nums length is n, queries length is m, the time complexity is O(n+m×logm)

/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {number}
 */
var maxRemoval = function (nums, queries) {
    queries.sort((a, b) => a[0] - b[0])
    const heap = new MaxPriorityQueue()
    const ditgit = Array(nums.length + 1).fill(0)

    let operations = 0

    for (let i = 0, j = 0; i < nums.length; i++) {
        operations += ditgit[i]

        while (j < queries.length && queries[j][0] === i) {
            heap.push(queries[j][1])
            j++
        }
        
        while (operations < nums[i] && !heap.isEmpty() && heap.front() >= i) {
            operations += 1
            ditgit[heap.pop() + 1] -= 1
        }

        if (operations < nums[i]) {
            return -1
        }
    }

    return heap.size()
};