Skip to content

2612. Minimum Reverse Operations

  • Time: $O(n\log n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
    const unordered_set<int> bannedSet{banned.begin(), banned.end()};
    vector<int> ans(n, -1);
    // unseen[i] := the unseen numbers that % 2 == i
    vector<set<int>> unseen(2);

    for (int num = 0; num < n; ++num)
      if (num != p && !bannedSet.count(num))
        unseen[num & 1].insert(num);

    // Perform BFS from `p`.
    queue<int> q{{p}};
    ans[p] = 0;

    while (!q.empty()) {
      const int u = q.front();
      q.pop();
      const int lo = max(u - k + 1, k - 1 - u);
      const int hi = min(u + k - 1, n - 1 - (u - (n - k)));
      // Choose the correct set of numbers.
      set<int>& nums = unseen[lo & 1];
      for (auto it = nums.lower_bound(lo); it != nums.end() && *it <= hi;) {
        ans[*it] = ans[u] + 1;
        q.push(*it);
        it = nums.erase(it);
      }
    }

    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
class Solution {
  public int[] minReverseOperations(int n, int p, int[] banned, int k) {
    Set<Integer> bannedSet = Arrays.stream(banned).boxed().collect(Collectors.toSet());
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    // unseen[i] := the unseen numbers that % 2 == i
    TreeSet<Integer>[] unseen = new TreeSet[2];
    unseen[0] = new TreeSet<>();
    unseen[1] = new TreeSet<>();

    for (int num = 0; num < n; ++num)
      if (num != p && !bannedSet.contains(num))
        unseen[num & 1].add(num);

    // Perform BFS from `p`.
    Queue<Integer> q = new ArrayDeque<>(Arrays.asList(p));
    ans[p] = 0;

    while (!q.isEmpty()) {
      final int u = q.poll();
      final int lo = Math.max(u - k + 1, k - 1 - u);
      final int hi = Math.min(u + k - 1, n - 1 - (u - (n - k)));
      // Choose the correct set of numbers.
      TreeSet<Integer> nums = unseen[lo & 1];
      for (Integer num = nums.ceiling(lo); num != null && num <= hi;) {
        ans[num] = ans[u] + 1;
        q.offer(num);
        nums.remove(num);
        num = nums.higher(num);
      }
    }

    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
from sortedcontainers import SortedList


class Solution:
  def minReverseOperations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:
    bannedSet = set(banned)
    ans = [-1] * n
    # unseen[i] := the unseen numbers that % 2 == i
    unseen = [SortedList(), SortedList()]

    for num in range(n):
      if num != p and num not in bannedSet:
        unseen[num & 1].add(num)

    # Perform BFS from `p`.
    q = collections.deque([p])
    ans[p] = 0

    while q:
      u = q.popleft()
      lo = max(u - k + 1, k - 1 - u)
      hi = min(u + k - 1, n - 1 - (u - (n - k)))
      # Choose the correct set of numbers.
      nums = unseen[lo & 1]
      i = nums.bisect_left(lo)
      while i < len(nums) and nums[i] <= hi:
        num = nums[i]
        ans[num] = ans[u] + 1
        q.append(num)
        nums.pop(i)

    return ans