0. 문제

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

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 vali.
The amount by which each 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 minimum possible non-negative value of k, such that after processing the first k queries in sequence, nums becomes a Zero Array. If no such k exists, return -1.

Example 1:

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

Output: 2

Explanation:
For i = 0 (l = 0, r = 2, val = 1):
Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.
The array will become [1, 0, 1].
For i = 1 (l = 0, r = 2, val = 1):
Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.
The array will become [0, 0, 0], which is a Zero Array. Therefore, the minimum value of k is 2.

Example 2:

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

Output: -1

Explanation:
For i = 0 (l = 1, r = 3, val = 2):
Decrement values at indices [1, 2, 3] by [2, 2, 1] respectively.
The array will become [4, 1, 0, 0].
For i = 1 (l = 0, r = 2, val = 1):
Decrement values at indices [0, 1, 2] by [1, 1, 0] respectively.
The array will become [3, 0, 0, 0], which is not a Zero Array.

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 5 * 105
• 1 <= queries.length <= 105
• queries[i].length == 3
• 0 <= li <= ri < nums.length
• 1 <= vali <= 5

1. 초기 코드

시간복잡도

$O(N+Q∗M)$

문제점

너무 많은 반복문 사용으로 인해, input이 커질 경우 시간복잡도로 인해 연산 시간이 많이 소요.

class Solution {
  public static boolean checkZeroArray(int[] nums) {
    for (int i: nums) {
      if (i > 0)
        return false;
    }
    return true;
  }

  public static int minZeroArray(int[] nums, int[][] queries) {
    int k = 0;

    for (int[] q: queries) {
      if (checkZeroArray(nums))
        break;
      for (int i = q[0]; i <= q[1]; i++) {
        if (nums[i] - q[2] >= 0)
          nums[i] -= q[2];
        else
          nums[i] = 0;
      }
      k++;
    }
    if (!checkZeroArray(nums))
      return -1;
    return k;
  }
}

2. 해결 방안

Difference Array (차분배열)의 활용

배열의 특정 범위를 수정하기기 위해서 반복문을 활용하면 O(N)의 시간이 소요되지만, 누적합을 활용하면 O(1) 시간만으로 해결 가능함.

1. nums = [0, 0, 0, 0, 0]가 있을 때, nums[1] ~ num[3]에 5씩 더하는 경우를 가정.

2. 차분배열, difference = [0, 0, 0, 0, 0, 0]를 생성. 이 때 차분배열의 크기는 수정하고자 하는 배열보다 크기가 1 커야함.

3. difference[1] = 5, difference[3+1] = -5

   • 수정하고자 하는 구간 [1, 3]에 대해서는 5를 더해야 하기 떄문에 difference[1] = 5이지만, 구간 [4:]에 대해서는 수정하지 않아야 하기 때문에 합을 상쇄하기 위해 difference[3+1] = -5를 적용.

4. 누적합 계산

nums[0] = difference[0] = 0
nums[1] = nums[0] + difference[1] = 0 + 5 = 5
nums[2] = nums[1] + difference[2] = 5 + 0 = 5
nums[3] = nums[2] + difference[3] = 5 + 0 = 5
nums[4] = nums[3] + difference[4] = 5 - 5 = 0
➡️ nums == [0, 5, 5, 5, 0]

초기화된 변수의 기본값

int[] arr = new int[3];
arr == [0, 0, 0];

정답 코드

class Solution {
    public int minZeroArray(int[] nums, int[][] queries) {
        int k = 0; // 쿼리 사용 횟수
        int sum = 0; // 부분합
        int n = nums.length;
        int[] differenceArray = new int[n + 1]; // 모든 원소의 값은 0으로 초기화.

        // nums의 각 원소를 순차적으로 검사하면서, 이를 0 이상으로 유지할 수 있는지 확인
        for (int index = 0; index < n; index++) {
            // sum + differenceArray[index] → 현재 nums[index]에 적용된 모든 업데이트의 합.
            while (sum + differenceArray[index] < nums[index]) {
                k++;

                // 모든 쿼리 적용 후에도 0이 되지 않은 경우
                if (k > queries.length) {
                    return -1;
                }

                // 구간 [left, right] 및 val 선언.
                int left = queries[k - 1][0];
                int right = queries[k - 1][1];
                int val = queries[k - 1][2];

                // index가 해당 쿼리의 구간 내에 있다면,
                if (right >= index) {
                    differenceArray[Math.max(left, index)] += val; // 구간 내에서 index를 포함한 이후 원소에 대해서만 업데이트 적용.
                    differenceArray[right + 1] -= val; // 구간을 벗어난 부분에 대한 업데이트 상쇄
                }
            }
            // 현재 index 기준으로 부분합(index에 대한 업데이트 총합) 최신화
            sum += differenceArray[index];
        }
        return k;
    }
}