LeetCode 3356 (Daily Challenge - java)

https://leetcode.com/problems/zero-array-transformation-ii/?envType=daily-question&envId=2025-03-11

Description

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.

---

문제를 쉽게 설명하면 이렇게 말할 수 있다.

queries배열은 0 ~ n 까지 있는데
queries배열을 queries[0] ~ queries[n] 까지 순회하면서
num배열의 queries[k][0](leftIndex) ~ queries[k][1] (rightIndex) index포함 사이 모든 값을 queries[k][2](value) 만큼 빼준다. <<< 이떄 뺴는값은 value보다 작거나 같은 수 선택해서 뺄 수 있다.

이때 num배열의 모든 항목이 0이 되는 최소 k의 값을 구하라.

문제 접근 방식

value보다 작거나 같은 수를 선택해서 뺄 수 있다면
value(최대값) 만큼 빼고 처음으로 nums의 각 원소가 모두 0보다 작은 시점을 찾으면 되지 않을까?

1. 시간복잡도 생각 안하고 풀기

class Solution {
    public int minZeroArray(int[] nums, int[][] queries) {
        
        int n = nums.length;
        int[] copy = Arrays.copyOf(nums, n);

        if (allZero(copy)) {
            return 0;
        }

        for (int k = 0; k < queries.length; k++) {
            int l = queries[k][0];
            int r = queries[k][1];
            int val = queries[k][2];

            for (int i = l; i <= r; i++) {
                copy[i] -= val;
            }

            if (allZero(copy)) {
                return k + 1;
            }
        }

        return -1;
    }

    public boolean allZero(int[] nums) {
        for (int num : nums) {
            if (num > 0) {
                return false;
            }
        }
        return true;
    }
}

결과 : Time Limit Exceeded

2. 최적화를 해보자.

queries배열을 0~n 까지에서 최소로 비용이 드는 k를 찾는 과정은
다르게 생각하면 이분탐색으로 가능할거같다.

 while(l <= r){
            int mid = (l + r)/2 ;
            int[] arr = Arrays.copyOf(nums,n);
            boolean value = prefixSum(arr,queries,mid);
            // 0보다 큰거 있음
            if(!value){
                l = mid + 1;
            }else{
                r = mid - 1;
                result = mid;
            }
        }

그런데 이분탐색을 하면서 mid값에 대해 nums배열이 0보다 작은지 확인해야하는데
이 과정을 1번에서처럼 한다면 O(n^2)시간복잡도가 걸리게된다.
여기서 누적합 알고리즘을 생각할 수 있는데
queries배열이 다음과 같이 주어질 때
[1,3,2],[0,2,1]

0	1	2	3
	2	2	2
1	1	1
-------------
1	3	3	2

nums배열에는 최종 결과를 뺀 값을 비교해야한다. 여기서 index마다 더해주면 O(n^2)의 시간복잡도가 나오기떄문에 인덱스만 저장해볼것이다.

0	1	2	3	4
	2			-2
1			-1		
-------------------
누적합 시작
-------------------
1	3	3	2	0

이런식으로 누적합을 사용하면 O(n)으로도 충분히 가능하다

최종 코드

class Solution {
    public int minZeroArray(int[] nums, int[][] queries) {
        
        int n = nums.length;

        int l = 0;
        int r = queries.length;
        int result = -1;

        while(l <= r){
            int mid = (l + r)/2 ;
            int[] arr = Arrays.copyOf(nums,n);
            boolean value = prefixSum(arr,queries,mid);
            // 0보다 큰거 있음
            if(!value){
                l = mid + 1;
            }else{
                r = mid - 1;
                result = mid;
            }
        }

        return result;
    }

    public boolean prefixSum(int[] nums, int[][] queries, int mid){
        int[] sum = new int[nums.length + 1];
        int[] prefixSum = new int[nums.length + 1];
        for(int i=0; i< mid; i++){
            int l = queries[i][0];
            int r = queries[i][1];
            int value = queries[i][2];
            sum[l] += value;
            sum[r + 1] -= value;
        }

        for(int i =1; i< prefixSum.length; i++){
            prefixSum[i] = sum[i-1] + prefixSum[i-1];
        }


        for(int i =0 ; i< nums.length; i++){
            nums[i] -= prefixSum[i + 1];
        }

        return allZero(nums);
    }

    public boolean allZero(int[] nums) {
        for (int num : nums) {
            if (num > 0) {
                return false;
            }
        }
        return true;
    }
}

결과 : 통과 but 느림