LeetCode in Kotlin

3355. Zero Array Transformation I

Medium

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.

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

A subset of an array is a selection of elements (possibly none) of the array.

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.

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105
• 1 <= queries.length <= 105
• queries[i].length == 2
• 0 <= li <= ri < nums.length

Solution

class Solution {
    fun isZeroArray(nums: IntArray, queries: Array<IntArray>): Boolean {
        val n = nums.size
        var sum = 0
        for (num in nums) {
            sum += num
        }
        if (sum == 0) {
            return true
        }
        val diff = IntArray(n + 1)
        for (q in queries) {
            val low = q[0]
            val high = q[1]
            diff[low] -= 1
            if (high + 1 < n) {
                diff[high + 1] += 1
            }
        }
        for (i in 0..<n) {
            if (i > 0) {
                diff[i] += diff[i - 1]
            }
            nums[i] += diff[i]
            sum += diff[i]
            if (nums[i] > 0) {
                return false
            }
        }
        return sum <= 0
    }
}

This site is open source. Improve this page.