Welcome to Subscribe On Youtube

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 $\mathit{\text{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 $\mathit{\text{nums}}$ a sortable array.

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

When the index $i$ is in the range $[\mathit{\text{first2}},\mathit{\text{last1}})$ or $[\mathit{\text{first3}},\mathit{\text{last2}})]$, the corresponding $\mathit{\text{locked}}[i]$ must be $0$, otherwise, we need one operation. Therefore, we only need to traverse the array $\mathit{\text{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 $\mathit{\text{nums}}$. The space complexity is $O(1)$.

• Java
• C++
• Python
• Go
• TypeScript

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

• 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)
          )
  
  

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

All Problems

All Solutions