[LeetCode] 3356. Zero Array Transformation II

Problem

https://leetcode.com/problems/zero-array-transformation-ii/description

Leetcode - Zero Array Transformation

Type - Binary Search, Parametric Search, Line Sweeping

Difficulty - Medium

Approach & Solution

We can solve it with binary search and line sweeping. In common, two approach uses diff array to accumulate changes. If diff[i] = 3, actual data for num[i] is num[i] - 3. Given l, r, val in queries, update diff like:

• diff[l] += val

• diff[r+1] += val

Binary Search: starting from lo = 0, hi = k. If k(mid) is available to set 0-array, reduce right side and try the number with less than k to minimize the answer, otherwise, reduce left side and try to larger k.

Line Sweeping: set pointer k to track the amount of used queries. slide k to right while current nums[i] is positive.

** data structure and variables**:

• diff: diff[i] stores how much subtracted from nums[i].

Binary Search:

1. set l := 0, r := queries.length.

2. follow these steps while l <= r:

   1. set mid := (l+r)/2

   2. if setting with first k queries is able,

      • set ans = k and r = mid-1 to try less than k.

   3. otherwise,

      • set l = mid+1 to try greater than k

Line Sweeping:

1. set k = 0, sum = 0

2. follow these steps while i = {0 .. n}:

   1. follow these steps while sum + diff[i] < nums[i]:

      1. increment k by 1. return -1 if k is greater than queries.length.

      2. update diff[i] from queries[k].

   2. accumulate diff[i] to sum.

3. It it valid. so return k.

Complexity

Time Complexity:

• Binary Search: O((n+q) * log(q)) - Validation takes n+q with validating log(q) times.

• Line Sweeping: O(n + q) - we iterate nums and queries once.

Space Complexity: O(n) - diff array stores n+1 cells.

Code (C++ | Go)

C++ code is Binary Search code, while golang code uses line sweeping.

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();

class Solution {
public:
    bool check(int k, vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> diff(n+1);
        for(int i = 0; i < k; i++) {
            diff[queries[i][0]] -= queries[i][2];
            diff[queries[i][1]+1] += queries[i][2];
        }

        int d = 0;
        for(int i = 0; i < n; i++) {
            d += diff[i];
            int x = nums[i] + d;
            if(x > 0) return false;
        }
        return true;
    }
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int l = 0;
        int r = queries.size();

        int ans = -1;
        while(l <= r) {
            int mid = (l+r)/2;
            if(check(mid, nums, queries)) {
                ans = mid;
                r = mid-1;
            } else {
                l = mid+1;
            }
        }
        return ans;
    }
};

func minZeroArray(nums []int, queries [][]int) int {
    diff := make([]int, len(nums)+1)
    k := 0
    sum := 0
    for i := 0; i < len(nums); i++ {
        for sum + diff[i] < nums[i] {
            k++

            if k > len(queries) {
                return -1
            }

            l, r, v := queries[k-1][0], queries[k-1][1], queries[k-1][2]
            if r >= i {
                diff[max(l, i)] += v
                diff[r+1] -= v
            }
        }
        sum += diff[i]
    }

    return k
}