3362. Zero Array Transformation III Medium

1/**
2 * [3362] Zero Array Transformation III
3 *
4 * You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri].
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 1.
8 * 	The amount by which the value is decremented 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 maximum number of elements that can be removed from queries, such that nums can still be converted to a zero array using the remaining queries. If it is not possible to convert nums to a zero array, 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],[0,2],[1,1]]</span>
16 * Output: <span class="example-io">1</span>
17 * Explanation:
18 * After removing queries[2], nums can still be converted to a zero array.
19 * 
20 * 	Using queries[0], decrement nums[0] and nums[2] by 1 and nums[1] by 0.
21 * 	Using queries[1], decrement nums[0] and nums[2] by 1 and nums[1] by 0.
22 * </div>
23 * <strong class="example">Example 2:
24 * <div class="example-block">
25 * Input: <span class="example-io">nums = [1,1,1,1], queries = [[1,3],[0,2],[1,3],[1,2]]</span>
26 * Output: <span class="example-io">2</span>
27 * Explanation:
28 * We can remove queries[2] and queries[3].
29 * </div>
30 * <strong class="example">Example 3:
31 * <div class="example-block">
32 * Input: <span class="example-io">nums = [1,2,3,4], queries = [[0,3]]</span>
33 * Output: <span class="example-io">-1</span>
34 * Explanation:
35 * nums cannot be converted to a zero array even after using all the queries.
36 * </div>
37 *  
38 * Constraints:
39 * 
40 * 	1 <= nums.length <= 10^5
41 * 	0 <= nums[i] <= 10^5
42 * 	1 <= queries.length <= 10^5
43 * 	queries[i].length == 2
44 * 	0 <= li <= ri < nums.length
45 * 
46 */
47pub struct Solution {}
48
49// problem: https://leetcode.com/problems/zero-array-transformation-iii/
50// discuss: https://leetcode.com/problems/zero-array-transformation-iii/discuss/?currentPage=1&orderBy=most_votes&query=
51
52// submission codes start here
53
54impl Solution {
55    pub fn max_removal(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
56        0
57    }
58}
59
60// submission codes end
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn test_3362() {
68    }
69}
70