3785. Minimum Swaps to Avoid Forbidden Values Hard

1/**
2 * [3785] Minimum Swaps to Avoid Forbidden Values
3 *
4 * You are given two integer arrays, nums and forbidden, each of length n.
5 * You may perform the following operation any number of times (including zero):
6 * 
7 * 	Choose two distinct indices i and j, and swap nums[i] with nums[j].
8 * 
9 * Return the minimum number of swaps required such that, for every index i, the value of nums[i] is not equal to forbidden[i]. If no amount of swaps can ensure that every index avoids its forbidden value, return -1.
10 *  
11 * <strong class="example">Example 1:
12 * <div class="example-block">
13 * Input: <span class="example-io">nums = [1,2,3], forbidden = [3,2,1]</span>
14 * Output: <span class="example-io">1</span>
15 * Explanation:
16 * One optimal set of swaps:
17 * 
18 * 	Select indices i = 0 and j = 1 in nums and swap them, resulting in nums = [2, 1, 3].
19 * 	After this swap, for every index i, nums[i] is not equal to forbidden[i].
20 * </div>
21 * <strong class="example">Example 2:
22 * <div class="example-block">
23 * Input: <span class="example-io">nums = [4,6,6,5], forbidden = [4,6,5,5]</span>
24 * Output: <span class="example-io">2</span>
25 * Explanation:
26 * One optimal set of swaps:
27 * 
28 * 	Select indices i = 0 and j = 2 in nums and swap them, resulting in nums = [6, 6, 4, 5].
29 * 	Select indices i = 1 and j = 3 in nums and swap them, resulting in nums = [6, 5, 4, 6].
30 * 	After these swaps, for every index i, nums[i] is not equal to forbidden[i].
31 * </div>
32 * <strong class="example">Example 3:
33 * <div class="example-block">
34 * Input: <span class="example-io">nums = [7,7], forbidden = [8,7]</span>
35 * Output: <span class="example-io">-1</span>
36 * Explanation:
37 * It is not possible to make nums[i] different from forbidden[i] for all indices.</div>
38 * <strong class="example">Example 4:
39 * <div class="example-block">
40 * Input: <span class="example-io">nums = [1,2], forbidden = [2,1]</span>
41 * Output: <span class="example-io">0</span>
42 * Explanation:
43 * No swaps are required because nums[i] is already different from forbidden[i] for all indices, so the answer is 0.
44 * </div>
45 *  
46 * Constraints:
47 * 
48 * 	1 <= n == nums.length == forbidden.length <= 10^5
49 * 	1 <= nums[i], forbidden[i] <= 10^9
50 * 
51 */
52pub struct Solution {}
53
54// problem: https://leetcode.com/problems/minimum-swaps-to-avoid-forbidden-values/
55// discuss: https://leetcode.com/problems/minimum-swaps-to-avoid-forbidden-values/discuss/?currentPage=1&orderBy=most_votes&query=
56
57// submission codes start here
58
59impl Solution {
60    pub fn min_swaps(nums: Vec<i32>, forbidden: Vec<i32>) -> i32 {
61        0
62    }
63}
64
65// submission codes end
66
67#[cfg(test)]
68mod tests {
69    use super::*;
70
71    #[test]
72    fn test_3785() {
73    }
74}
75