Skip to content

3431. Minimum Unlocked Indices to Sort Nums

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  int minUnlockedIndices(vector<int>& nums, vector<int>& locked) {
    const auto first2It = ranges::find(nums, 2);
    const auto first3It = ranges::find(nums, 3);
    const auto last1It = ranges::find_last(nums, 1);
    const auto last2It = ranges::find_last(nums, 2);
    const int first2 =
        first2It == nums.cend() ? -1 : distance(nums.begin(), first2It);
    const int first3 =
        first3It == nums.cend() ? -1 : distance(nums.begin(), first3It);
    const int last1 = last1It.begin() == nums.cend()
                          ? -1
                          : distance(nums.begin(), last1It.begin());
    const int last2 = last2It.begin() == nums.cend()
                          ? -1
                          : distance(nums.begin(), last2It.begin());
    if (first3 != -1 && last1 != -1 && first3 < last1)
      return -1;

    int ans = 0;

    // Unlocked indices between 2 and 1.
    if (first2 != -1 && last1 != -1)
      for (int i = first2; i < last1; ++i)
        if (locked[i] == 1)
          ++ans;

    // Unlocked indices between 3 and 2.
    if (first3 != -1 && last2 != -1)
      for (int i = first3; i < last2; ++i)
        if (locked[i] == 1)
          ++ans;

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
  public int minUnlockedIndices(int[] nums, int[] locked) {
    final int first2 = findFirstIndex(nums, 2);
    final int first3 = findFirstIndex(nums, 3);
    final int last1 = findLastIndex(nums, 1);
    final int last2 = findLastIndex(nums, 2);
    if (first3 != -1 && last1 != -1 && first3 < last1)
      return -1;

    int ans = 0;

    // Unlocked indices between 2 and 1.
    if (first2 != -1 && last1 != -1)
      for (int i = first2; i < last1; ++i)
        if (locked[i] == 1)
          ++ans;

    // Unlocked indices between 3 and 2.
    if (first3 != -1 && last2 != -1)
      for (int i = first3; i < last2; i++)
        if (locked[i] == 1)
          ++ans;

    return ans;
  }

  private int findFirstIndex(int[] nums, int target) {
    for (int i = 0; i < nums.length; ++i)
      if (nums[i] == target)
        return i;
    return -1;
  }

  private int findLastIndex(int[] nums, int target) {
    for (int i = nums.length - 1; i >= 0; i--)
      if (nums[i] == target)
        return i;
    return -1;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def minUnlockedIndices(self, nums: list[int], locked: list[int]) -> int:
    first2 = next((i for i, x in enumerate(nums) if x == 2), -1)
    first3 = next((i for i, x in enumerate(nums) if x == 3), -1)
    last1 = next((i for i, x in reversed(list(enumerate(nums))) if x == 1), -1)
    last2 = next((i for i, x in reversed(list(enumerate(nums))) if x == 2), -1)
    if first3 != -1 and last1 != -1 and first3 < last1:
      return -1
    return (sum(locked[i] == 1 for i in range(first2, last1)
                if first2 != -1 and last1 != -1) +
            sum(locked[i] == 1 for i in range(first3, last2)
                if first3 != -1 and last2 != -1))