3356. Zero Array Transformation II Medium

1/**
2 * [3356] Zero Array Transformation II
3 *
4 * You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri, vali].
5 * Each queries[i] represents the following action on nums:
6 * 
7 * 	Decrement the value at each index in the range [li, ri] in nums by at most vali.
8 * 	The amount by which each value is decremented<!-- notionvc: b232c9d9-a32d-448c-85b8-b637de593c11 --> can be chosen independently for each index.
9 * 
10 * A Zero Array is an array with all its elements equal to 0.
11 * 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.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]</span>
16 * Output: <span class="example-io">2</span>
17 * Explanation:
18 * 
19 * 	For i = 0 (l = 0, r = 2, val = 1):
20 * 	
21 * 		Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.
22 * 		The array will become [1, 0, 1].
23 * 	
24 * 	
25 * 	For i = 1 (l = 0, r = 2, val = 1):
26 * 	
27 * 		Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.
28 * 		The array will become [0, 0, 0], which is a Zero Array. Therefore, the minimum value of k is 2.
29 * 	
30 * 	
31 * </div>
32 * <strong class="example">Example 2:
33 * <div class="example-block">
34 * Input: <span class="example-io">nums = [4,3,2,1], queries = [[1,3,2],[0,2,1]]</span>
35 * Output: <span class="example-io">-1</span>
36 * Explanation:
37 * 
38 * 	For i = 0 (l = 1, r = 3, val = 2):
39 * 	
40 * 		Decrement values at indices [1, 2, 3] by [2, 2, 1] respectively.
41 * 		The array will become [4, 1, 0, 0].
42 * 	
43 * 	
44 * 	For i = 1 (l = 0, r = 2, val<span style="font-size: 13.3333px;"> </span>= 1):
45 * 	
46 * 		Decrement values at indices [0, 1, 2] by [1, 1, 0] respectively.
47 * 		The array will become [3, 0, 0, 0], which is not a Zero Array.
48 * 	
49 * 	
50 * </div>
51 *  
52 * Constraints:
53 * 
54 * 	1 <= nums.length <= 10^5
55 * 	0 <= nums[i] <= 5 * 10^5
56 * 	1 <= queries.length <= 10^5
57 * 	queries[i].length == 3
58 * 	0 <= li <= ri < nums.length
59 * 	1 <= vali <= 5
60 * 
61 */
62pub struct Solution {}
63
64// problem: https://leetcode.com/problems/zero-array-transformation-ii/
65// discuss: https://leetcode.com/problems/zero-array-transformation-ii/discuss/?currentPage=1&orderBy=most_votes&query=
66
67// submission codes start here
68
69impl Solution {
70    pub fn min_zero_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
71        0
72    }
73}
74
75// submission codes end
76
77#[cfg(test)]
78mod tests {
79    use super::*;
80
81    #[test]
82    fn test_3356() {
83    }
84}
85