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] <= 1Problem Overview: You are given an array nums where some indices may remain locked. Locked elements cannot move, while unlocked ones can be rearranged among themselves. The task is to determine the minimum number of indices you must unlock so the entire array can become sorted.
Approach 1: Brute Force Subset Search (Exponential Time)
Try every subset of indices to unlock and check if the array can be rearranged into sorted order using only those positions. For each subset, copy the array, allow swaps among chosen indices, and verify if it matches the sorted version. This requires iterating through 2^n possibilities and validating each candidate configuration. Time complexity is O(2^n * n log n) and space complexity is O(n). This approach mainly helps reason about the constraints but is impractical for real inputs.
Approach 2: Sorted Comparison + Hash Counting (O(n log n))
Create a sorted copy of nums. Any index i where nums[i] != sorted[i] cannot remain locked because the value at that position must change to achieve sorted order. Those indices must be unlocked. Iterate through the array and collect all mismatched positions. Since unlocked positions can be freely permuted, verify that the multiset of values at these positions can transform into the required values using a frequency map (Hash Table). Sorting takes O(n log n), while the comparison and hash counting take O(n). Space complexity is O(n).
The key insight: locked indices must already contain the correct value relative to the final sorted array. Any mismatch forces that index to be unlocked. Once those indices are unlocked, their values can be permuted to match the sorted target as long as their frequencies match.
This pattern appears frequently in Array problems that compare an original structure against its sorted form. A frequency map ensures the values in the mismatched region can be rearranged into the required target values.
Recommended for interviews: The sorted comparison plus hash counting approach is what interviewers expect. Mentioning the brute force subset idea shows you understand the search space, but the optimal solution demonstrates recognition of the invariant: locked indices must already match the sorted order. Using sorting and a hash map reduces the problem to a simple mismatch count with O(n log n) time.
According 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).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Search | O(2^n * n log n) | O(n) | Conceptual baseline to understand constraints or very small n |
| Sorted Comparison + Hash Counting | O(n log n) | O(n) | General case; efficient and straightforward for interview settings |
| Counting Optimization (Value Range Known) | O(n) | O(n) | When values are bounded so counting sort or frequency arrays replace sorting |
Practice Minimum Unlocked Indices to Sort Nums with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor