3431. Minimum Unlocked Indices to Sort Nums 🔒

Description

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

Solutions

Solution 1: Brain Teaser

According to the problem description, to make $\textit{nums}$ a sortable array, the position of the number $3$ must be after the position of the number $1$. If the position of the number $3$ is before the position of the number $1$, no matter how we swap, the number $3$ cannot reach the position of the number $1$, so it is impossible to make $\textit{nums}$ a sortable array.

We use $\textit{first2}$ and $\textit{first3}$ to represent the first occurrence positions of the numbers $2$ and $3$, and $\textit{last1}$ and $\textit{last2}$ to represent the last occurrence positions of the numbers $1$ and $2$.

When the index $i$ is in the range $[\textit{first2}, \textit{last1})$ or $[\textit{first3}, \textit{last2})]$, the corresponding $\textit{locked}[i]$ must be $0$, otherwise, we need one operation. Therefore, we only need to traverse the array $\textit{locked}$ and count the indices that do not meet the condition.

The time complexity is $O(n)$, where $n$ is the length of the array $\textit{nums}$. The space complexity is $O(1)$.

Python3JavaC++GoTypeScript

class Solution:
    def minUnlockedIndices(self, nums: List[int], locked: List[int]) -> int:
        n = len(nums)
        first2 = first3 = n
        last1 = last2 = -1
        for i, x in enumerate(nums):
            if x == 1:
                last1 = i
            elif x == 2:
                first2 = min(first2, i)
                last2 = i
            else:
                first3 = min(first3, i)
        if first3 < last1:
            return -1
        return sum(
            st and (first2 <= i < last1 or first3 <= i < last2)
            for i, st in enumerate(locked)
        )

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 {
                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;
    }
}

class Solution {
public:
    int minUnlockedIndices(vector<int>& nums, vector<int>& locked) {
        int n = nums.size();
        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 = min(first2, i);
                last2 = i;
            } else {
                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;
    }
};

func minUnlockedIndices(nums []int, locked []int) (ans int) {
    n := len(nums)
    first2, first3 := n, n
    last1, last2 := -1, -1
    for i, x := range nums {
        if x == 1 {
            last1 = i
        } else if x == 2 {
            if i < first2 {
                first2 = i
            }
            last2 = i
        } else {
            if i < first3 {
                first3 = i
            }
        }
    }
    if first3 < last1 {
        return -1
    }
    for i, st := range locked {
        if st == 1 && ((first2 <= i && i < last1) || (first3 <= i && i < last2)) {
            ans++
        }
    }
    return ans
}

function minUnlockedIndices(nums: number[], locked: number[]): number {
    const n = nums.length;
    let [first2, first3] = [n, n];
    let [last1, last2] = [-1, -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 {
            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;
}

Comments