Problem Description

You have an array nums containing only integers 1, 2, and 3, along with a binary array locked of the same length. Each element in locked is either 0 or 1.

The goal is to determine if you can sort nums in ascending order using a specific type of swap operation. You can swap two adjacent elements at positions i and i + 1 only if:

• The difference between them equals 1: nums[i] - nums[i + 1] == 1
• The position i is unlocked: locked[i] == 0

This means you can only swap adjacent elements where the left element is exactly 1 greater than the right element, and the left position must be unlocked.

Initially, some positions may be locked (locked[i] == 1). In one operation, you can unlock any single position by changing its corresponding locked[i] from 1 to 0.

Your task is to find the minimum number of unlock operations needed to make it possible to sort nums using the allowed swaps. If it's impossible to sort the array regardless of how many positions you unlock, return -1.

For example, if nums = [2, 1, 3] and locked = [1, 0, 0], you would need to unlock position 0 to swap 2 and 1, making the array sortable with 1 operation.

Intuition

Let's think about what movements are possible with our swap rules. We can only swap adjacent elements when the left one is exactly 1 greater than the right one. This means:

• We can swap (2, 1) to get (1, 2)
• We can swap (3, 2) to get (2, 3)
• We cannot swap (3, 1) since the difference is 2, not 1

This constraint creates a critical insight: the number 3 can never "jump over" the number 1. If a 3 appears before a 1 in the array, there's no sequence of valid swaps that can move the 3 past the 1 to reach sorted order. This is our impossibility condition.

Now, assuming it's possible to sort (all 3s are after all 1s), which positions actually need to be unlocked?

Consider the sorted target: all 1s first, then all 2s, then all 3s. During the sorting process:

• Any 2 that appears before the last 1 will need to swap with 1s to move rightward
• Any 3 that appears before the last 2 will need to swap with 2s to move rightward

These swaps happen at specific positions. When a 2 needs to move past 1s, it will swap at positions between where the first 2 appears (first2) and where the last 1 appears (last1). Similarly, when a 3 needs to move past 2s, it will swap at positions between where the first 3 appears (first3) and where the last 2 appears (last2).

Therefore, any position in the ranges [first2, last1) or [first3, last2) must be unlocked for sorting to be possible. We simply count how many of these positions are currently locked (have locked[i] == 1) - that's our minimum number of unlock operations needed.

Solution Approach

The implementation follows directly from our intuition about which positions need to be unlocked.

First, we traverse the array once to find the critical positions:

• first2: the first occurrence of number 2 (initialized to n)
• first3: the first occurrence of number 3 (initialized to n)
• last1: the last occurrence of number 1 (initialized to -1)
• last2: the last occurrence of number 2 (initialized to -1)

for i, x in enumerate(nums):
    if x == 1:
        last1 = i
    elif x == 2:
        first2 = min(first2, i)
        last2 = i
    else:  # x == 3
        first3 = min(first3, i)

Next, we check the impossibility condition. If any 3 appears before the last 1, sorting is impossible:

if first3 < last1:
    return -1

Finally, we count how many positions need to be unlocked. A position i needs to be unlocked if:

• It's currently locked (locked[i] == 1), AND
• It falls within the critical ranges where swaps must occur:
  • [first2, last1): where 2s need to swap with 1s
  • [first3, last2): where 3s need to swap with 2s

return sum(
    st and (first2 <= i < last1 or first3 <= i < last2)
    for i, st in enumerate(locked)
)

The expression st and (condition) evaluates to True (counts as 1) only when both st (which is locked[i]) is 1 and the position i is in one of the critical ranges. This gives us the exact count of positions that are currently locked but need to be unlocked for sorting.

The time complexity is O(n) for the single pass through the array, and the space complexity is O(1) as we only use a few variables to track positions.

Example Walkthrough

Let's walk through an example with nums = [2, 3, 1, 2] and locked = [1, 1, 0, 0].

Step 1: Find critical positions

• Traverse the array:
  • i=0, nums[0]=2: first2 = 0
  • i=1, nums[1]=3: first3 = 1
  • i=2, nums[2]=1: last1 = 2
  • i=3, nums[3]=2: last2 = 3

Step 2: Check impossibility

• Is first3 < last1? Is 1 < 2? Yes!
• Since 3 appears at position 1 before the last 1 at position 2, it's impossible to sort.
• Return -1

Let's try another example where sorting is possible: nums = [2, 1, 2, 3] and locked = [1, 0, 1, 0].

Step 1: Find critical positions

• i=0, nums[0]=2: first2 = 0
• i=1, nums[1]=1: last1 = 1
• i=2, nums[2]=2: last2 = 2
• i=3, nums[3]=3: first3 = 3

Step 2: Check impossibility

• Is first3 < last1? Is 3 < 1? No, so sorting is possible.

Step 3: Identify critical ranges

• Range where 2s swap with 1s: [first2, last1) = [0, 1)
• Range where 3s swap with 2s: [first3, last2) = [3, 2) (empty range since 3 > 2)

Step 4: Count locked positions in critical ranges

• Position 0: locked[0] = 1, in range [0, 1)? Yes → needs unlocking
• Position 1: locked[1] = 0, already unlocked
• Position 2: locked[2] = 1, in critical ranges? No
• Position 3: locked[3] = 0, already unlocked

Result: We need to unlock 1 position (position 0).

To verify: After unlocking position 0, we can swap positions 0 and 1 (since nums[0] - nums[1] = 2 - 1 = 1), getting [1, 2, 2, 3] which is sorted!

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array nums. The algorithm makes a single pass through the nums array in the first loop to find the positions of first occurrence of 2 and 3, and last occurrences of 1 and 2. Then it makes another single pass through the locked array (which has the same length n) in the sum comprehension. Both operations are linear, resulting in O(n) + O(n) = O(n) total time complexity.

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store the variables n, first2, first3, last1, and last2, regardless of the input size. The loop variables i and x also use constant space. No additional data structures that scale with input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Swap Condition Direction

Pitfall: A common mistake is misinterpreting which element can swap with which. The condition nums[i] - nums[i + 1] == 1 means we can only swap when the left element is exactly 1 greater than the right element (e.g., [2,1] can swap to become [1,2], but [1,2] cannot swap back).

Why this matters: This directional constraint means:

• 1s can only move right (by being swapped over)
• 3s can only move left (by being swapped over)
• 2s can move both directions depending on their neighbor

Solution: Always remember the swap is "bubble down" - larger values bubble down to the left when possible.

2. Incorrect Range Boundaries

Pitfall: Using inclusive ranges instead of exclusive for the upper bounds. The code uses [first2, last1) and [first3, last2) - note the exclusive upper bounds.

Why this happens: The position at last1 itself doesn't need to be unlocked because we're swapping element at position i with i+1. When a 1 is at position last1, we need to unlock positions before it to allow 2s to swap past it.

Solution: Remember that unlocking position i allows swapping elements at positions i and i+1. So to move element at position j, you need positions [start, j) to be unlockable.

3. Not Handling Edge Cases with No Occurrences

Pitfall: If there are no 2s or no 1s in the array, the initial values (first2 = n, last1 = -1) create an empty range [n, -1) which could cause issues if not handled properly.

Why it works correctly: The range check first2 <= i < last1 naturally returns False for all i when first2 > last1, so no positions are counted. This is the correct behavior since no swaps are needed.

Solution: The initialization values are carefully chosen:

• first2 = n and first3 = n: Ensures empty ranges if these values don't exist
• last1 = -1 and last2 = -1: Ensures empty ranges if these values don't exist

4. Forgetting the Impossibility Check

Pitfall: Focusing only on counting locked positions without checking if sorting is even possible. If any 3 appears before the last 1, no amount of unlocking can make the array sortable.

Example: nums = [3, 2, 1], regardless of locked status, this cannot be sorted because 3 needs to move right but can only swap leftward with 2s.

Solution: Always perform the impossibility check if first3 < last1: return -1 before counting unlocks. This saves unnecessary computation and correctly identifies unsolvable cases.