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