Photo by Chris Ried on Unsplash

LeetCode day316–3355

Everyday has one random leetcode quiz. Today’s quiz is 3355. Zero Array Transformation I

Description:

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

For each queries[i]:

• Select a subset of indices within the range [li, ri] in nums.
• Decrement the values at the selected indices by 1.

A Zero Array is an array where all elements are equal to 0.

Get Jimmy’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Return true if it is possible to transform nums into a Zero Array after processing all the queries sequentially, otherwise return false.

Example 1:

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

Output: true

Explanation:

For i = 0:
Select the subset of indices as [0, 2] and decrement the values at these indices by 1.
The array will become [0, 0, 0], which is a Zero Array.

Example 2:

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

Output: false

Explanation:

For i = 0:
Select the subset of indices as [1, 2, 3] and decrement the values at these indices by 1.
The array will become [4, 2, 1, 0].
For i = 1:
Select the subset of indices as [0, 1, 2] and decrement the values at these indices by 1.
The array will become [3, 1, 0, 0], which is not a Zero Array.

We use digits to record the change at each index. For every query in queries, the value increases by 1 from the start position to the end position.

Then, for each number in nums, if nums[i] - currentNum > 0, it means that forming a Zero Array is impossible, so return false. Otherwise, return true.

If nums length is n, the time complexity is O(n)

/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {boolean}
 */
var isZeroArray = function (nums, queries) {
    const digits = Array(nums.length).fill(0)
    queries.forEach(([start, end]) => {
        digits[start]++
        digits[end + 1]--
    })

    let currentNum = 0
    for (let i = 0; i < digits.length; i++) {
        currentNum += digits[i]

        if (nums[i] - currentNum > 0) {
            return false
        }
    }

    return true
};