2612. Minimum Reverse Operations LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2612. Minimum Reverse Operations LeetCode Solution with the best time and space complexity. The solution to Minimum Reverse Operations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Reverse Operations solution in C++
Minimum Reverse Operations solution in Java
Minimum Reverse Operations solution in Python
Additional Resources

2612. Minimum Reverse Operations LeetCode Solution image

Problem Statement of Minimum Reverse Operations

You are given an integer n and an integer p representing an array arr of length n where all elements are set to 0’s, except position p which is set to 1. You are also given an integer array banned containing restricted positions. Perform the following operation on arr:

Reverse a subarray with size k if the single 1 is not set to a position in banned.

Return an integer array answer with n results where the ith result is the minimum number of operations needed to bring the single 1 to position i in arr, or -1 if it is impossible.

Example 1:

Input: n = 4, p = 0, banned = [1,2], k = 4
Output: [0,-1,-1,1]
Explanation:

Initially 1 is placed at position 0 so the number of operations we need for position 0 is 0.
We can never place 1 on the banned positions, so the answer for positions 1 and 2 is -1.
Perform the operation of size 4 to reverse the whole array.
After a single operation 1 is at position 3 so the answer for position 3 is 1.

Example 2:

Input: n = 5, p = 0, banned = [2,4], k = 3
Output: [0,-1,-1,-1,-1]
Explanation:

Initially 1 is placed at position 0 so the number of operations we need for position 0 is 0.
We cannot perform the operation on the subarray positions [0, 2] because position 2 is in banned.
Because 1 cannot be set at position 2, it is impossible to set 1 at other positions in more operations.

Example 3:

Input: n = 4, p = 2, banned = [0,1,3], k = 1
Output: [-1,-1,0,-1]
Explanation:
Perform operations of size 1 and 1 never changes its position.

Constraints:

1 <= n <= 105
0 <= p <= n – 1
0 <= banned.length <= n – 1
0 <= banned[i] <= n – 1
1 <= k <= n
banned[i] != p
all values in banned are unique

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

2612. Minimum Reverse Operations LeetCode Solution in C++

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.contains(num))
        unseen[num % 2].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 % 2];
      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;
  }
};
/* code provided by PROGIEZ */

2612. Minimum Reverse Operations LeetCode Solution in Java

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 % 2].add(num);

    // Perform BFS from `p`.
    Queue<Integer> q = new ArrayDeque<>(List.of(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 % 2];
      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;
  }
}
// code provided by PROGIEZ

2612. Minimum Reverse Operations LeetCode Solution in Python

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 % 2].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 % 2]
      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
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents