Minimum Unlocked Indices to Sort Nums

Minimum Unlocked Indices to Sort Nums - Problem

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 (the left element is exactly 1 greater than the right)
locked[i] == 0 (index i is unlocked)

In one operation, you can unlock any index i by setting locked[i] = 0.

Return the minimum number of operations needed to make nums sortable. If it is not possible to make nums sortable, return -1.

Input & Output

Example 1 — Basic Case

$ Input: nums = [3,1,2,3], locked = [1,1,0,1]

› Output: 1

💡 Note: We need to swap 3 and 1 (since 3-1=2≠1, this is invalid). Actually, we can swap positions where difference is exactly 1. We need to unlock position 0 to swap 3→1, then 1→2. Total unlocks: 1.

Example 2 — Already Sorted

$ Input: nums = [1,2,3], locked = [1,1,1]

› Output: 0

💡 Note: Array is already sorted, no swaps needed, so no unlocks required.

Example 3 — Impossible Case

$ Input: nums = [3,1,1], locked = [0,0,0]

› Output: -1

💡 Note: We need to swap 3 and 1, but 3-1=2≠1, so the swap is not allowed even if unlocked. Cannot sort this array.

Constraints

2 ≤ nums.length ≤ 20
1 ≤ nums[i] ≤ 3
locked.length == nums.length
locked[i] is either 0 or 1

Visualization

Tap to expand

Asked in

G Google 25 M Microsoft 20

The key insight is that we can only swap adjacent elements where the left element is exactly 1 greater than the right element. The best approach uses greedy simulation of bubble sort, unlocking positions only when needed for required swaps. Time: O(n²), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Combinations	O(n × 2ⁿ)	O(n)	Try all possible combinations of unlocked positions until we find one that allows sorting
Greedy Simulation	O(n²)	O(n)	Simulate bubble sort and unlock positions only when needed for required swaps

Brute Force - Try All Combinations — Algorithm Steps

Generate all possible unlock combinations
For each combination, simulate bubble sort
Check if array becomes sorted
Return minimum unlocks needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Masks

Try all 2^n combinations of unlock positions

Test Sorting

For each combination, simulate bubble sort

Find Minimum

Return the combination with minimum unlocks

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int canSort(int* nums, int* locked, int n, int unlockMask, int* target) {
    int* tempNums = (int*)malloc(n * sizeof(int));
    int* tempLocked = (int*)malloc(n * sizeof(int));
    
    memcpy(tempNums, nums, n * sizeof(int));
    memcpy(tempLocked, locked, n * sizeof(int));
    
    // Apply unlock mask
    for (int i = 0; i < n; i++) {
        if (unlockMask & (1 << i)) {
            tempLocked[i] = 0;
        }
    }
    
    // Try to sort using bubble sort
    for (int pass = 0; pass < n; pass++) {
        int swapped = 0;
        for (int i = 0; i < n - 1; i++) {
            if (tempNums[i] > tempNums[i + 1] && tempNums[i] - tempNums[i + 1] == 1 && tempLocked[i] == 0) {
                int temp = tempNums[i];
                tempNums[i] = tempNums[i + 1];
                tempNums[i + 1] = temp;
                swapped = 1;
            }
        }
        if (!swapped) break;
    }
    
    int result = 1;
    for (int i = 0; i < n; i++) {
        if (tempNums[i] != target[i]) {
            result = 0;
            break;
        }
    }
    
    free(tempNums);
    free(tempLocked);
    return result;
}

int solution(int* nums, int* locked, int n) {
    int* target = (int*)malloc(n * sizeof(int));
    memcpy(target, nums, n * sizeof(int));
    
    // Sort target array
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (target[j] > target[j + 1]) {
                int temp = target[j];
                target[j] = target[j + 1];
                target[j + 1] = temp;
            }
        }
    }
    
    int minUnlocks = INT_MAX;
    
    // Try all possible unlock combinations
    for (int mask = 0; mask < (1 << n); mask++) {
        if (canSort(nums, locked, n, mask, target)) {
            int unlocks = __builtin_popcount(mask);
            if (unlocks < minUnlocks) {
                minUnlocks = unlocks;
            }
        }
    }
    
    free(target);
    return minUnlocks == INT_MAX ? -1 : minUnlocks;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse first array
    int nums[20];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    
    // Parse second array
    int locked[20];
    token = strtok(line + 1, ",]");
    int i = 0;
    while (token != NULL && i < n) {
        locked[i++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, locked, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2ⁿ)

2^n combinations to try, each taking O(n) time to verify sortability

✓ Linear Growth

Space Complexity

O(n)

Space for copying arrays and storing combinations

⚡ Linearithmic Space

21.3K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler