3048. Earliest Second to Mark Indices I Medium

1/**
2 * [3048] Earliest Second to Mark Indices I
3 *
4 * You are given two 1-indexed integer arrays, nums and, changeIndices, having lengths n and m, respectively.
5 * Initially, all indices in nums are unmarked. Your task is to mark all indices in nums.
6 * In each second, s, in order from 1 to m (inclusive), you can perform one of the following operations:
7 * 
8 * 	Choose an index i in the range [1, n] and decrement nums[i] by 1.
9 * 	If nums[changeIndices[s]] is equal to 0, mark the index changeIndices[s].
10 * 	Do nothing.
11 * 
12 * Return an integer denoting the earliest second in the range [1, m] when all indices in nums can be marked by choosing operations optimally, or -1 if it is impossible.
13 *  
14 * <strong class="example">Example 1:
15 * 
16 * Input: nums = [2,2,0], changeIndices = [2,2,2,2,3,2,2,1]
17 * Output: 8
18 * Explanation: In this example, we have 8 seconds. The following operations can be performed to mark all indices:
19 * Second 1: Choose index 1 and decrement nums[1] by one. nums becomes [1,2,0].
20 * Second 2: Choose index 1 and decrement nums[1] by one. nums becomes [0,2,0].
21 * Second 3: Choose index 2 and decrement nums[2] by one. nums becomes [0,1,0].
22 * Second 4: Choose index 2 and decrement nums[2] by one. nums becomes [0,0,0].
23 * Second 5: Mark the index changeIndices[5], which is marking index 3, since nums[3] is equal to 0.
24 * Second 6: Mark the index changeIndices[6], which is marking index 2, since nums[2] is equal to 0.
25 * Second 7: Do nothing.
26 * Second 8: Mark the index changeIndices[8], which is marking index 1, since nums[1] is equal to 0.
27 * Now all indices have been marked.
28 * It can be shown that it is not possible to mark all indices earlier than the 8th second.
29 * Hence, the answer is 8.
30 * 
31 * <strong class="example">Example 2:
32 * 
33 * Input: nums = [1,3], changeIndices = [1,1,1,2,1,1,1]
34 * Output: 6
35 * Explanation: In this example, we have 7 seconds. The following operations can be performed to mark all indices:
36 * Second 1: Choose index 2 and decrement nums[2] by one. nums becomes [1,2].
37 * Second 2: Choose index 2 and decrement nums[2] by one. nums becomes [1,1].
38 * Second 3: Choose index 2 and decrement nums[2] by one. nums becomes [1,0].
39 * Second 4: Mark the index changeIndices[4], which is marking index 2, since nums[2] is equal to 0.
40 * Second 5: Choose index 1 and decrement nums[1] by one. nums becomes [0,0].
41 * Second 6: Mark the index changeIndices[6], which is marking index 1, since nums[1] is equal to 0.
42 * Now all indices have been marked.
43 * It can be shown that it is not possible to mark all indices earlier than the 6th second.
44 * Hence, the answer is 6.
45 * 
46 * <strong class="example">Example 3:
47 * 
48 * Input: nums = [0,1], changeIndices = [2,2,2]
49 * Output: -1
50 * Explanation: In this example, it is impossible to mark all indices because index 1 isn't in changeIndices.
51 * Hence, the answer is -1.
52 * 
53 *  
54 * Constraints:
55 * 
56 * 	1 <= n == nums.length <= 2000
57 * 	0 <= nums[i] <= 10^9
58 * 	1 <= m == changeIndices.length <= 2000
59 * 	1 <= changeIndices[i] <= n
60 * 
61 */
62pub struct Solution {}
63
64// problem: https://leetcode.com/problems/earliest-second-to-mark-indices-i/
65// discuss: https://leetcode.com/problems/earliest-second-to-mark-indices-i/discuss/?currentPage=1&orderBy=most_votes&query=
66
67// submission codes start here
68
69impl Solution {
70    pub fn earliest_second_to_mark_indices(nums: Vec<i32>, change_indices: 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_3048() {
83    }
84}
85