📚 단일 패턴

3355. Zero Array Transformation I

Difference Array 누적 커버리지를 활용해 O(N)으로 판별하는 방법

Oct 17, 2025 — difference-array

문제 설명

LeetCode 3355. Zero Array Transformation I (opens in a new window)
주어진 배열에 queries 로 주어지는 [left, right] subset 에 대해서 decrement 하고 나머지 배열이 모두 0 이 되는지 판별하는 문제

풀이 아이디어

문제 그대로 풀이를 하면 O(N^2) 시간 복잡도를 가져서 시간 초과가 발생함.

var isZeroArray = function(nums, queries) {
    for (const [ left, right ] of queries) {
        for (let i = left; i <= right; i += 1) {
            if (nums[i] > 0) nums[i] -= 1;
        }
    }

    return nums.every((num) => num === 0);
};

second pass O(N) 으로 해결 가능할까 ?

해결 전략

Difference Array

풀이

먼저 difference array 를 계산
이후 원본을 순회하면서 각 값이 difference array 의 누적합을 감당할 수 있는지 체크
- 만약 감당할 수 없다면 false 를 반환
- 모든 값을 감당할 수 있다면 true 를 반환

구현

/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {boolean}
 */
var isZeroArray = function(nums, queries) {
    const N = nums.length;

    const diff = new Array(N + 1).fill(0);

    for (const [ left, right ] of queries) {
        diff[left] += 1;
        if (right + 1 < N) diff[right + 1] -= 1;
    }

    let pendingDecrements = 0;

    for (let i = 0; i < N; i += 1) {
        pendingDecrements += diff[i];
        if (pendingDecrements < nums[i]) return false;
    }
    return true;
};