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

Examples

Example 1:

1
2

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

1
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

1
2

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.

Solution

Method 1 – Position Constraints and Range Traversal

Intuition

To make the array sortable, every number must be able to reach its correct position using allowed swaps. If a ‘3’ appears before the last ‘1’, it is impossible to sort the array, as swaps cannot move ‘3’ past ‘1’. We track the first and last positions of each number and check for locked indices in critical ranges. Any locked index in these ranges must be unlocked to allow sorting.

Approach

  1. Find the first occurrence of ‘2’ and ‘3’, and the last occurrence of ‘1’ and ‘2’.
  2. If the first ‘3’ is before the last ‘1’, sorting is impossible; return -1.
  3. For each index, if it is locked and falls within [first2, last1) or [first3, last2), increment the unlock count.
  4. Return the total unlocks needed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int minUnlockedIndices(vector<int>& nums, vector<int>& locked) {
        int n = nums.size();
        int first2 = n, first3 = n, last1 = -1, last2 = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) last1 = i;
            else if (nums[i] == 2) {
                first2 = min(first2, i);
                last2 = i;
            } else if (nums[i] == 3) {
                first3 = min(first3, i);
            }
        }
        if (first3 < last1) return -1;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (locked[i] == 1 && ((first2 <= i && i < last1) || (first3 <= i && i < last2))) {
                ans++;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public int minUnlockedIndices(int[] nums, int[] locked) {
        int n = nums.length;
        int first2 = n, first3 = n;
        int last1 = -1, last2 = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) last1 = i;
            else if (nums[i] == 2) {
                first2 = Math.min(first2, i);
                last2 = i;
            } else if (nums[i] == 3) {
                first3 = Math.min(first3, i);
            }
        }
        if (first3 < last1) return -1;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            if (locked[i] == 1 && ((first2 <= i && i < last1) || (first3 <= i && i < last2))) {
                ans++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def minUnlockedIndices(self, nums: list[int], locked: list[int]) -> int:
        n = len(nums)
        first2, first3 = n, n
        last1, last2 = -1, -1
        for i, x in enumerate(nums):
            if x == 1:
                last1 = i
            elif x == 2:
                first2 = min(first2, i)
                last2 = i
            elif x == 3:
                first3 = min(first3, i)
        if first3 < last1:
            return -1
        ans = 0
        for i in range(n):
            if locked[i] == 1 and ((first2 <= i < last1) or (first3 <= i < last2)):
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    fun minUnlockedIndices(nums: IntArray, locked: IntArray): Int {
        val n = nums.size
        var first2 = n
        var first3 = n
        var last1 = -1
        var last2 = -1
        for (i in 0 until n) {
            when (nums[i]) {
                1 -> last1 = i
                2 -> {
                    first2 = minOf(first2, i)
                    last2 = i
                }
                3 -> first3 = minOf(first3, i)
            }
        }
        if (first3 < last1) return -1
        var ans = 0
        for (i in 0 until n) {
            if (locked[i] == 1 && ((first2 <= i && i < last1) || (first3 <= i && i < last2))) {
                ans++
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

impl Solution {
    pub fn min_unlocked_indices(nums: Vec<i32>, locked: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut first2 = n as i32;
        let mut first3 = n as i32;
        let mut last1 = -1;
        let mut last2 = -1;
        for (i, &x) in nums.iter().enumerate() {
            if x == 1 {
                last1 = i as i32;
            } else if x == 2 {
                first2 = first2.min(i as i32);
                last2 = i as i32;
            } else if x == 3 {
                first3 = first3.min(i as i32);
            }
        }
        if first3 < last1 {
            return -1;
        }
        let mut ans = 0;
        for i in 0..n {
            if locked[i] == 1 && ((first2 <= i as i32 && i as i32 < last1) || (first3 <= i as i32 && i as i32 < last2)) {
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    minUnlockedIndices(nums: number[], locked: number[]): number {
        const n = nums.length;
        let first2 = n, first3 = n, last1 = -1, last2 = -1;
        for (let i = 0; i < n; ++i) {
            if (nums[i] === 1) last1 = i;
            else if (nums[i] === 2) {
                first2 = Math.min(first2, i);
                last2 = i;
            } else if (nums[i] === 3) {
                first3 = Math.min(first3, i);
            }
        }
        if (first3 < last1) return -1;
        let ans = 0;
        for (let i = 0; i < n; ++i) {
            if (locked[i] === 1 && ((first2 <= i && i < last1) || (first3 <= i && i < last2))) {
                ans++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) – Single pass to find positions and another to count unlocks.
  • 🧺 Space complexity: O(1) – Only a few variables for positions and counters.