Welcome to Subscribe On Youtube

3356. Zero Array Transformation II

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.

 

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

Solutions

Solution 1

  • class Solution { private int n; private int[] nums; private int[][] queries; public int minZeroArray(int[] nums, int[][] queries) { this.nums = nums; this.queries = queries; n = nums.length; int m = queries.length; int l = 0, r = m + 1; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l > m ? -1 : l; } private boolean check(int k) { int[] d = new int[n + 1]; for (int i = 0; i < k; ++i) { int l = queries[i][0], r = queries[i][1], val = queries[i][2]; d[l] += val; d[r + 1] -= val; } for (int i = 0, s = 0; i < n; ++i) { s += d[i]; if (nums[i] > s) { return false; } } return true; } } 
  • class Solution { public: int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) { int n = nums.size(); int d[n + 1]; int m = queries.size(); int l = 0, r = m + 1; auto check = [&](int k) -> bool { memset(d, 0, sizeof(d)); for (int i = 0; i < k; ++i) { int l = queries[i][0], r = queries[i][1], val = queries[i][2]; d[l] += val; d[r + 1] -= val; } for (int i = 0, s = 0; i < n; ++i) { s += d[i]; if (nums[i] > s) { return false; } } return true; }; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l > m ? -1 : l; } }; 
  • class Solution: def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int: def check(k: int) -> bool: d = [0] * (len(nums) + 1) for l, r, val in queries[:k]: d[l] += val d[r + 1] -= val s = 0 for x, y in zip(nums, d): s += y if x > s: return False return True m = len(queries) l = bisect_left(range(m + 1), True, key=check) return -1 if l > m else l 
  • func minZeroArray(nums []int, queries [][]int) int { n, m := len(nums), len(queries) l := sort.Search(m+1, func(k int) bool { d := make([]int, n+1) for _, q := range queries[:k] { l, r, val := q[0], q[1], q[2] d[l] += val d[r+1] -= val } s := 0 for i, x := range nums { s += d[i] if x > s { return false } } return true }) if l > m { return -1 } return l } 
  • function minZeroArray(nums: number[], queries: number[][]): number { const [n, m] = [nums.length, queries.length]; const d: number[] = Array(n + 1); let [l, r] = [0, m + 1]; const check = (k: number): boolean => { d.fill(0); for (let i = 0; i < k; ++i) { const [l, r, val] = queries[i]; d[l] += val; d[r + 1] -= val; } for (let i = 0, s = 0; i < n; ++i) { s += d[i]; if (nums[i] > s) { return false; } } return true; }; while (l < r) { const mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l > m ? -1 : l; } 
  • impl Solution { pub fn min_zero_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 { let n = nums.len(); let m = queries.len(); let mut d: Vec<i64> = vec![0; n + 1]; let (mut l, mut r) = (0_usize, m + 1); let check = |k: usize, d: &mut Vec<i64>| -> bool { d.fill(0); for i in 0..k { let (l, r, val) = ( queries[i][0] as usize, queries[i][1] as usize, queries[i][2] as i64, ); d[l] += val; d[r + 1] -= val; } let mut s: i64 = 0; for i in 0..n { s += d[i]; if nums[i] as i64 > s { return false; } } true }; while l < r { let mid = (l + r) >> 1; if check(mid, &mut d) { r = mid; } else { l = mid + 1; } } if l > m { -1 } else { l as i32 } } }

All Problems

All Solutions