'2025/03/14'에 해당되는 글 1건

Leetcode Problem:

• Zero Array Transformation II

Summary

• Given an integer array and a 2D array of queries, find the minimum possible non-negative value of k such that after processing the first k queries in sequence, the array becomes a Zero Array.

Approach

• This problem can be solved by using binary search to find the minimum possible value of k
• We start by initializing two pointers, l and r, to the start and end of the queries array respectively
• We then calculate the sum of the values to be decremented for each query and update the offset array accordingly
• If the array becomes a Zero Array after processing the current query, we update the answer and move the right pointer to the left
• If not, we move the left pointer to the right
• We repeat this process until we find the minimum possible value of k or until l is greater than r.

Complexity

• O(n log q) where n is the size of the nums array and q is the size of the queries array

Explanation

• The time complexity of this solution is O(n log q) because we are using binary search to find the minimum possible value of k
• In the worst case, we need to process each query in the queries array, which takes O(n) time
• We repeat this process log q times, where log q is the number of iterations of the binary search
• The space complexity is O(n) because we need to store the offset array, which has n elements.

Solution Code:

class Solution {
public:
    int offset[100002];
    int minZeroArray(vector& nums, vector>& queries) {
        int l = 0;
        int r = queries.size();
        int ans = 100001;
        while(l <= r){
            int mid = (l + r) / 2;
            for(int i = 0 ; i < nums.size(); i++){
                offset[i] = 0;
            }
            for(int i = 0; i < mid; i++){
                offset[queries[i][0]] += queries[i][2];
                offset[queries[i][1] + 1] -= queries[i][2];
            }
            for(int i = 1; i < nums.size(); i++){
                offset[i] += offset[i-1];
            }
            bool success = true;
            for(int i = 0 ; i < nums.size() ;i++){
                if((nums[i] - offset[i]) > 0){
                    success = false;
                    break;
                }
            }
            if(success){
                ans = mid;
                r = mid - 1;
            } else{
                l = mid + 1;
            }
        }
        if( ans == 100001) return -1;
        return ans;
    }
};