Skip to main content
Talentd

Minimum Unlocked Indices to Sort Nums - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash Table10 min read
Practice this problem

Problem Statement

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:

  • swap indices 1 with 2
  • swap indices 4 with 5

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:

  • swap indices 1 with 2
  • swap indices 2 with 3
  • swap indices 4 with 5
  • swap indices 5 with 6

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 <= 105
  • 1 <= nums[i] <= 3
  • locked.length == nums.length
  • 0 <= locked[i] <= 1

Approach Overview

Problem 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.

Solution

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subset SearchO(2^n * n log n)O(n)Conceptual baseline to understand constraints or very small n
Sorted Comparison + Hash CountingO(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

Frequently Asked Questions

Is Minimum Unlocked Indices to Sort Nums easy or hard?
The problem is classified as Medium because the implementation is straightforward once you recognize the sorted comparison trick. The challenge lies in realizing that locked indices must already match their sorted positions while the remaining indices can be freely permuted.
Minimum Unlocked Indices to Sort Nums Python/Java solution
Implementations in Python, Java, C++, Go, and TypeScript typically follow the same pattern: create a sorted copy of nums, scan for mismatches, and track value counts with a hash map. The final answer is the number of indices that must be unlocked to allow rearrangement.
How to solve Minimum Unlocked Indices to Sort Nums in O(n)?
If the value range is small or known beforehand, you can replace sorting with counting sort or a frequency array. Build frequency counts and simulate the sorted order while scanning the original array. This removes the O(n log n) sorting cost and reduces the runtime to O(n) with O(n) auxiliary space.
What is the best approach for Minimum Unlocked Indices to Sort Nums?
The most practical solution compares the array with its sorted version and identifies mismatched positions. Any index where nums[i] differs from the sorted value must be unlocked. A hash table verifies that values in those positions can be rearranged to match the target. This runs in O(n log n) time due to sorting and O(n) space.
Is Minimum Unlocked Indices to Sort Nums asked at Google/Amazon/Meta?
Problems involving partial constraints on rearranging arrays appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often test reasoning about fixed positions, permutations, and frequency balancing. The core skills involve array analysis and hash-based counting.
What data structure is used in Minimum Unlocked Indices to Sort Nums?
The main data structures are arrays and a hash table for frequency counting. Arrays help compare the original order with the sorted order, while the hash table ensures the values in mismatched indices can be rearranged to produce the required sorted configuration.
What is the time complexity of Minimum Unlocked Indices to Sort Nums?
The common optimal implementation runs in O(n log n) time because it sorts a copy of the array and then performs a linear scan to detect mismatches. Hash map checks for value frequencies take O(n). Space complexity is O(n) for the sorted array and frequency storage.

Ready to solve this problem?

Practice Minimum Unlocked Indices to Sort Nums with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays