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.

Description Hints 3 Solution

3431. Minimum Unlocked Indices to Sort Nums

Medium57.6% acceptancePremium elsewhere, free here

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

Topics

Array Hash Table

Hints open one at a time

Hint 1

All positions between the first 2 and the last 1 should be unlocked.

Hint 2

All positions between the first 3 and the last 2 should be unlocked.

Hint 3

If the position of the first 3 is less than the position of the last 1, the answer is -1.

Still stuck?Read the written solution.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1,2,1,2,3,2]
[1,0,1,1,0,1]

Input

[1,2,1,1,3,2,2]
[1,0,1,1,0,1,0]

Input

[1,2,1,2,3,2,1]
[0,0,0,0,0,0,0]

Your code is saved on this device.Solution