Minimum Swaps to Avoid Forbidden Values
You are given two integer arrays, nums and forbidden, each of length n.
You may perform the following operation any number of times, including zero:
- Choose two distinct indices
iandj, and swapnums[i]withnums[j].
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.
Example 1
Input
nums = [1,2,3], forbidden = [3,2,1]Output
1Swapping indices 0 and 1 changes
nums to [2, 1, 3], so every value differs from its corresponding forbidden value.Example 2
Input
nums = [4,6,6,5], forbidden = [4,6,5,5]Output
2Swapping indices 0 and 2, then indices 1 and 3, produces
nums = [6, 5, 4, 6], where every value differs from its corresponding forbidden value.Constraints
- 1 <= n == nums.length == forbidden.length <= 10^5
- 1 <= nums[i], forbidden[i] <= 10^9