LeetCode Problem 3431

Difficulty: 🟡 Medium
Topics: Array, Hash Table

Solution

LeetCode 3431 - Minimum Unlocked Indices to Sort Nums

Problem Understanding

We are given two arrays of equal length:

• nums, where every value is either 1, 2, or 3
• locked, where each value is either 0 or 1

The array is considered sortable if we can repeatedly perform certain adjacent swaps until the array becomes sorted in nondecreasing order.

A swap between positions i and i + 1 is allowed only when:

• nums[i] - nums[i + 1] == 1
• locked[i] == 0

Because the values are limited to {1,2,3}, the only possible allowed swaps are:

• 2 1 -> 1 2
• 3 2 -> 2 3

Notice that 3 1 can never be swapped directly.

We may perform an operation that unlocks an index by setting locked[i] = 0. The goal is to determine the minimum number of indices that must be unlocked so that the array becomes sortable. If sorting is impossible even after unlocking every index, we return -1.

The constraints are large, up to 10^5 elements, so any solution that explores swap sequences explicitly will be far too slow. We need to discover structural properties of the allowed swaps and derive a linear-time solution.

Several edge cases are particularly important:

• Arrays that already satisfy the sorting requirements.
• Arrays containing a 3 before a 1.
• Arrays where sorting is theoretically possible, but some required swap locations are locked.
• Very small arrays, including length 1.
• Arrays where every index is already unlocked.

Approaches

Brute Force

A brute force approach would treat each array configuration as a state and explore all reachable states using BFS or DFS. For every state, we would try every allowed adjacent swap and continue until either the sorted array is reached or all possibilities are exhausted.

This approach is correct because it explicitly explores the entire reachable state space.

Unfortunately, the number of reachable states grows exponentially. Even for modest input sizes, state exploration becomes infeasible. Since n can be as large as 100000, this approach is completely impractical.

Key Observation

The crucial observation is that only two types of swaps are ever possible:

• 2 1 -> 1 2
• 3 2 -> 2 3

A 3 and a 1 can never swap with each other.

Therefore, the relative order between every 3 and every 1 is permanent.

If a 3 appears before a 1 in the original array, there is no sequence of legal swaps that can move that 1 ahead of that 3. Since every sorted array places all 1s before all 3s, such an input is impossible to sort.

This gives a simple necessary condition:

No 3 may appear before any later 1.

It turns out this condition is also sufficient when all indices are unlocked.

Next, we must determine which boundaries actually need to permit swaps.

Consider a boundary between positions i and i+1.

A 2 must cross that boundary if:

• there is a 2 somewhere on the left side, and
• there is a 1 somewhere on the right side.

Similarly, a 3 must cross that boundary if:

• there is a 3 somewhere on the left side, and
• there is a 2 somewhere on the right side.

If either situation occurs, then at some point a swap across boundary i is unavoidable. Therefore boundary i must be unlocked.

The minimum answer is simply the number of required boundaries that are currently locked.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores reachable swap states
Optimal	O(n)	O(n)	Finds required swap boundaries directly

Algorithm Walkthrough

1. First check whether sorting is fundamentally possible.

Scan the array from left to right. Once a 3 has been seen, any later 1 immediately proves the array can never be sorted. In that case return -1. 2. Precompute suffix information.

For every position i, store:

• whether there exists a 1 strictly to the right of i
• whether there exists a 2 strictly to the right of i

These arrays allow us to determine in O(1) time whether a future element requiring a crossing exists. 3. Scan boundaries from left to right.

Maintain:

• whether a 2 has appeared on the left side
• whether a 3 has appeared on the left side

4. For each boundary i between positions i and i+1, determine whether it is required.

The boundary is required if:

• a 2 exists on the left and a 1 exists on the right, or
• a 3 exists on the left and a 2 exists on the right

5. If a boundary is required and locked[i] == 1, then this boundary must be unlocked. Add one to the answer.
6. After processing all boundaries, return the total number of required unlocks.

Why it works

A boundary is required exactly when some element must cross it during any successful sorting process.

A 2 must cross every boundary that separates a left-side 2 from a right-side 1. Likewise, a 3 must cross every boundary that separates a left-side 3 from a right-side 2.

If such a boundary remains locked, the necessary movement cannot occur, making sorting impossible. Conversely, unlocking all required boundaries allows every needed 21 -> 12 and 32 -> 23 exchange to occur. Therefore the set of required boundaries is both necessary and sufficient, and counting currently locked required boundaries yields the minimum answer.

Python Solution

from typing import List

class Solution:
    def minUnlockedIndices(self, nums: List[int], locked: List[int]) -> int:
        n = len(nums)

        seen_three = False
        for value in nums:
            if value == 3:
                seen_three = True
            elif value == 1 and seen_three:
                return -1

        suffix_has_one = [False] * n
        suffix_has_two = [False] * n

        has_one = False
        has_two = False

        for i in range(n - 1, -1, -1):
            suffix_has_one[i] = has_one
            suffix_has_two[i] = has_two

            if nums[i] == 1:
                has_one = True
            elif nums[i] == 2:
                has_two = True

        left_has_two = False
        left_has_three = False
        answer = 0

        for i in range(n - 1):
            if nums[i] == 2:
                left_has_two = True
            elif nums[i] == 3:
                left_has_three = True

            required = (
                (left_has_two and suffix_has_one[i]) or
                (left_has_three and suffix_has_two[i])
            )

            if required and locked[i] == 1:
                answer += 1

        return answer

The implementation begins by checking the fundamental impossibility condition. Any occurrence of a 1 after a previously seen 3 immediately returns -1.

Next, two suffix arrays are constructed. For each position, they indicate whether a 1 or 2 exists somewhere strictly to its right. This allows constant-time evaluation of whether a future crossing is required.

The final scan maintains whether a 2 or 3 has appeared on the left side of the current boundary. Using the prefix and suffix information, the code determines whether the boundary is required. Every required boundary that is currently locked contributes one operation to the answer.

Go Solution

func minUnlockedIndices(nums []int, locked []int) int {
	n := len(nums)

	seenThree := false
	for _, v := range nums {
		if v == 3 {
			seenThree = true
		} else if v == 1 && seenThree {
			return -1
		}
	}

	suffixHasOne := make([]bool, n)
	suffixHasTwo := make([]bool, n)

	hasOne := false
	hasTwo := false

	for i := n - 1; i >= 0; i-- {
		suffixHasOne[i] = hasOne
		suffixHasTwo[i] = hasTwo

		if nums[i] == 1 {
			hasOne = true
		} else if nums[i] == 2 {
			hasTwo = true
		}
	}

	leftHasTwo := false
	leftHasThree := false
	answer := 0

	for i := 0; i < n-1; i++ {
		if nums[i] == 2 {
			leftHasTwo = true
		} else if nums[i] == 3 {
			leftHasThree = true
		}

		required := (leftHasTwo && suffixHasOne[i]) ||
			(leftHasThree && suffixHasTwo[i])

		if required && locked[i] == 1 {
			answer++
		}
	}

	return answer
}

The Go implementation follows exactly the same logic as the Python version. The only notable difference is the explicit allocation of boolean slices for suffix information. Integer overflow is not a concern because the answer is at most n.

Worked Examples

Example 1

Input

nums   = [1,2,1,2,3,2]
locked = [1,0,1,1,0,1]

First verify that no 3 appears before a later 1. The condition holds.

Suffix information:

i	suffix_has_one	suffix_has_two
0	True	True
1	True	True
2	False	True
3	False	True
4	False	True
5	False	False

Boundary scan:

Boundary	Required?	Locked?	Contribution
0	No	1	0
1	Yes	0	0
2	No	1	0
3	No	1	0
4	Yes	0	0

Answer = 0.

Example 2

Input

nums   = [1,2,1,1,3,2,2]
locked = [1,0,1,1,0,1,0]

No 3 appears before a later 1.

Required boundaries are:

• boundary 1
• boundary 2
• boundary 4
• boundary 5

Checking locks:

Boundary	Required?	Locked?
1	Yes	0
2	Yes	1
4	Yes	0
5	Yes	1

Two required boundaries are locked.

Answer = 2.

Example 3

Input

nums = [1,2,1,2,3,2,1]

Scanning left to right:

Position	Value	Seen 3?
0	1	No
1	2	No
2	1	No
3	2	No
4	3	Yes
5	2	Yes
6	1	Yes

A 1 appears after a previously seen 3.

Therefore sorting is impossible.

Answer = -1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Three linear scans of the array
Space	O(n)	Two suffix boolean arrays

The algorithm performs a constant amount of work per element. The suffix arrays require linear extra storage, resulting in O(n) space usage.

Test Cases

s = Solution()

assert s.minUnlockedIndices([1,2,1,2,3,2], [1,0,1,1,0,1]) == 0  # example 1
assert s.minUnlockedIndices([1,2,1,1,3,2,2], [1,0,1,1,0,1,0]) == 2  # example 2
assert s.minUnlockedIndices([1,2,1,2,3,2,1], [0,0,0,0,0,0,0]) == -1  # example 3

assert s.minUnlockedIndices([1], [1]) == 0  # single element
assert s.minUnlockedIndices([1,1,2,2,3,3], [1,1,1,1,1,1]) == 0  # already sorted

assert s.minUnlockedIndices([2,1], [0,1]) == 0  # required boundary already unlocked
assert s.minUnlockedIndices([2,1], [1,1]) == 1  # must unlock one boundary

assert s.minUnlockedIndices([3,1], [0,0]) == -1  # impossible due to 3 before 1
assert s.minUnlockedIndices([3,2,1], [0,0,0]) == -1  # still impossible

assert s.minUnlockedIndices([2,2,1,1], [1,1,1,1]) == 2  # both boundaries required
assert s.minUnlockedIndices([1,3,2,2], [1,1,1,1]) == 1  # only one required boundary

assert s.minUnlockedIndices([1,2,2,3], [1,1,1,1]) == 0  # no swaps needed
assert s.minUnlockedIndices([2,1,2,1,2], [1,1,1,1,1]) == 2  # multiple required crossings

Test Summary

Test	Why
Example 1	Validates zero additional unlocks
Example 2	Validates counting required locked boundaries
Example 3	Validates impossibility detection
Single element	Smallest input size
Already sorted	No swaps required
[2,1] unlocked	Basic sortable case
[2,1] locked	Smallest nontrivial unlock requirement
[3,1]	Fundamental impossibility
[3,2,1]	Impossible despite available swaps
[2,2,1,1]	Multiple required boundaries
[1,3,2,2]	Required 3-2 movement
Sorted with locks	Locks irrelevant when no movement needed
Alternating pattern	Repeated crossings across boundaries

Edge Cases

A 3 Appears Before a 1

This is the most important edge case. Since 3 and 1 can never swap directly, any occurrence of a 3 before a later 1 permanently violates the order required by the final sorted array. A solution that ignores this property may incorrectly assume enough unlocks can always fix the array. The implementation detects this during the initial scan and immediately returns -1.

Already Sorted Arrays

An array may already be sorted even when every boundary is locked. In this situation no swaps are required, so the answer must be 0. The boundary analysis naturally produces no required boundaries, resulting in the correct answer.

Required Boundary Already Unlocked

A boundary may be necessary for sorting, but locked[i] may already be 0. Such a boundary contributes no cost because it is already usable. The algorithm only increments the answer when a required boundary is currently locked.

Length One Arrays

When n = 1, there are no boundaries at all. The suffix arrays are still valid, the boundary loop executes zero times, and the answer correctly remains 0. This avoids special-case logic while handling the smallest input safely.