3355.zero-array-transformation-i.md

3355. Zero Array Transformation I

Line Sweep

• We create a difference array diff to store the changes of the array nums.
• For each query [l, r], we decrease diff[l] by 1 and increase diff[r + 1] by 1.
• Then we calculate prefix sum of the difference array, then apply the updates to the array nums.

fun isZeroArray(nums: IntArray, queries: Array<IntArray>): Boolean {
    val n = nums.size
    val diff = IntArray(n + 1)
    for ((l, r) in queries) {
        diff[l] -= 1
        diff[r + 1] += 1
    }
    var value = 0
    for (i in nums.indices) {
        value += diff[i]
        nums[i] += value
        if (nums[i] > 0) return false
    }
    return true
}

• Time complexity: O(n + q), where n is the length of the array nums and q is the number of queries.
• Space complexity: O(n).