You are given an array nums consisting of integers between 1 and 3, and a binary array locked of the same size.
We consider nums sortable if it can be sorted using adjacent swaps, where a swap between two indices i and i + 1 is allowed if nums[i] - nums[i + 1] == 1 and locked[i] == 0.
In one operation, you can unlock any index i by setting locked[i] to 0.
Return the minimum number of operations needed to make nums sortable. If it is not possible to make nums sortable, return -1.
Example 1:
Input: nums = [1,2,1,2,3,2], locked = [1,0,1,1,0,1]
Output: 0
Explanation:
We can sort nums using the following swaps:
So, there is no need to unlock any index.
Example 2:
Input: nums = [1,2,1,1,3,2,2], locked = [1,0,1,1,0,1,0]
Output: 2
Explanation:
If we unlock indices 2 and 5, we can sort nums using the following swaps:
Example 3:
Input: nums = [1,2,1,2,3,2,1], locked = [0,0,0,0,0,0,0]
Output: -1
Explanation:
Even if all indices are unlocked, it can be shown that nums is not sortable.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 3locked.length == nums.length0 <= locked[i] <= 1According to the problem description, to make nums a sortable array, the position of the number 3 must be after the position of the number 1. If the position of the number 3 is before the position of the number 1, no matter how we swap, the number 3 cannot reach the position of the number 1, so it is impossible to make nums a sortable array.
We use first2 and first3 to represent the first occurrence positions of the numbers 2 and 3, and last1 and last2 to represent the last occurrence positions of the numbers 1 and 2.
When the index i is in the range [first2, last1) or [first3, last2)], the corresponding locked[i] must be 0, otherwise, we need one operation. Therefore, we only need to traverse the array locked and count the indices that do not meet the condition.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
Java
C++
Go
TypeScript
Practice Minimum Unlocked Indices to Sort Nums with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor