# Minimum Reverse Operations
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-reverse-operations)
Canonical: https://scaleengineer.com/dsa/problems/minimum-reverse-operations
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Ordered Set
**Companies:** [Infosys](https://scaleengineer.com/companies/infosys)
---
## Problem
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 isthe **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**

# Approaches
## Naive Breadth-First Search (BFS)
This problem can be modeled as finding the shortest path from a source node `p` to all other nodes in an unweighted graph. The nodes of the graph are the indices `0, 1, ..., n-1`. An edge exists from index `u` to `v` if the `1` can be moved from `u` to `v` in a single reverse operation. Since each operation (edge) has a weight of 1, Breadth-First Search (BFS) is the perfect algorithm to find the minimum number of operations.

The naive approach involves a direct implementation of BFS. For each position visited, we generate all possible next positions by iterating through all valid subarrays of size `k` that contain the current position.
**Time:** O(N * K), where N is the number of elements and K is the subarray size. In the worst case, for each of the N nodes, we might iterate up to K times to find all its neighbors. Given N up to 10^5 and K up to N, this can be as slow as O(N^2). · **Space:** O(N), where N is the number of elements. This is for the queue, the `banned` set, the `visited` array, and the `answer` array.
**Pros:** Conceptually simple and easy to implement.; Correctly models the problem as a shortest path search.
**Cons:** The time complexity of O(N * K) is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error.
### Explanation
The core of this approach is a standard BFS algorithm. We start at position `p`. In each step of the BFS, we explore all reachable positions from the current one. A position `v` is reachable from `u` if there's a subarray of length `k` containing `u` which, when reversed, moves the `1` to `v`.

To find all neighbors of a node `u`, we must consider every possible subarray of length `k` that contains `u`. A subarray starting at index `j` has the range `[j, j + k - 1]`. For this subarray to contain `u`, we must have `j <= u < j + k`. Also, the subarray must be within the bounds of the main array, so `0 <= j` and `j + k - 1 < n`. Combining these, the starting index `j` can range from `max(0, u - k + 1)` to `min(n - k, u)`. For each valid `j`, the new position `v` is calculated by finding the symmetric position of `u` within the subarray `[j, j + k - 1]`, which is `v = j + (j + k - 1) - u`.

We use a queue to manage the nodes to visit, a `visited` array to avoid cycles and redundant computations, and an `answer` array to store the results.

```java
import java.util.*;

class Solution {
    public int[] minReverseOperations(int n, int p, int[] banned, int k) {
        int[] ans = new int[n];
        Arrays.fill(ans, -1);

        Set<Integer> bannedSet = new HashSet<>();
        for (int b : banned) {
            bannedSet.add(b);
        }

        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];

        if (!bannedSet.contains(p)) {
            ans[p] = 0;
            queue.offer(p);
            visited[p] = true;
        }

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            int dist = ans[curr];

            // Iterate through all possible start positions 'j' of the subarray
            int minJ = Math.max(0, curr - k + 1);
            int maxJ = Math.min(n - k, curr);

            for (int j = minJ; j <= maxJ; j++) {
                int nextPos = j + (j + k - 1) - curr;
                
                if (nextPos >= 0 && nextPos < n && !bannedSet.contains(nextPos) && !visited[nextPos]) {
                    visited[nextPos] = true;
                    ans[nextPos] = dist + 1;
                    queue.offer(nextPos);
                }
            }
        }
        return ans;
    }
}
```
### Algorithm
- Create a set for `banned` positions for quick O(1) lookups.
- Initialize an `answer` array of size `n` with `-1` and a `visited` array of size `n` with `false`.
- Create a queue for the BFS and add the starting position `p`.
- Set `answer[p] = 0` and `visited[p] = true`.
- While the queue is not empty:
  - Dequeue the current position, let's call it `u`, and get its distance `d = answer[u]`.
  - Determine the range of possible starting indices `j` for a `k`-sized subarray that includes `u`. This range is `[max(0, u - k + 1), min(n - k, u)]`.
  - Iterate through each possible `j` in this range.
  - For each `j`, calculate the next position `v` of the `1` after the reversal: `v = j + (j + k - 1) - u`.
  - If `v` is a valid index, not banned, and not yet visited:
    - Mark `v` as visited.
    - Set `answer[v] = d + 1`.
    - Enqueue `v`.
- After the BFS completes, the `answer` array contains the minimum operations for each position.

## Optimized BFS with TreeSet
The bottleneck in the naive BFS is the neighbor discovery step, which takes O(K) time for each node. We can optimize this by observing a key property: all positions reachable from a position `u` in one step lie within a contiguous range `[min_v, max_v]` and, more importantly, all share the same parity.

This observation allows us to maintain two separate sets of available (unvisited and not banned) indices: one for even indices and one for odd indices. By using an ordered set data structure like Java's `TreeSet`, we can efficiently query for all available indices within a specific range. This reduces the complexity of finding neighbors from O(K) to O(log N + M), where M is the number of neighbors found. Since each node is found as a neighbor only once during the entire BFS, the total time complexity is significantly improved.
**Time:** O(N log N). Initializing the `TreeSet`s takes O(N log N). Each of the N nodes is enqueued and processed once. For each node, we perform a range query on a `TreeSet`. Finding the start of the range takes O(log N). Each neighbor is found and removed once, costing O(log N) per neighbor. The total complexity of all `TreeSet` operations throughout the BFS is O(N log N). · **Space:** O(N), where N is the number of elements. The `TreeSet`s can store up to N elements in total. The queue, `banned` set, and `answer` array also contribute to this.
**Pros:** Highly efficient with a time complexity of O(N log N), which passes the given constraints.; Effectively utilizes data structures to optimize the neighbor-finding process in BFS.
**Cons:** More complex to implement due to the use of `TreeSet`s and the logic for calculating ranges and parities.
### Explanation
This approach enhances the standard BFS by using a more efficient data structure for tracking available nodes. Instead of a simple `visited` array, we use two `TreeSet`s to store unvisited, non-banned indices, partitioned by their parity (even or odd).

When processing a node `u` from the BFS queue, we first calculate the range of possible next positions. A move from `u` to `v` implies `u + v = 2*j + k - 1`. This means `v - u` has the same parity as `k - 1`. Consequently:
- If `k` is odd, `k-1` is even. `v` and `u` must have the same parity.
- If `k` is even, `k-1` is odd. `v` and `u` must have different parities.

This rule tells us which `TreeSet` (even or odd) to search for neighbors. We then calculate the minimum and maximum possible values for a neighbor `v` and use the `TreeSet.subSet()` method to get all available nodes in that range. This is very efficient. Each node found is a new node to visit. We add it to the queue and remove it from its `TreeSet` to mark it as visited. We collect all neighbors from the `subSet` view into a temporary list before modifying the `TreeSet` to avoid `ConcurrentModificationException`.

```java
import java.util.*;

class Solution {
    public int[] minReverseOperations(int n, int p, int[] banned, int k) {
        int[] ans = new int[n];
        Arrays.fill(ans, -1);

        Set<Integer> bannedSet = new HashSet<>();
        for (int b : banned) {
            bannedSet.add(b);
        }

        TreeSet<Integer> availableEven = new TreeSet<>();
        TreeSet<Integer> availableOdd = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            if (!bannedSet.contains(i)) {
                if (i % 2 == 0) {
                    availableEven.add(i);
                } else {
                    availableOdd.add(i);
                }
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        
        if (!bannedSet.contains(p)) {
            ans[p] = 0;
            queue.offer(p);
            if (p % 2 == 0) {
                availableEven.remove(p);
            } else {
                availableOdd.remove(p);
            }
        }

        while (!queue.isEmpty()) {
            int curr = queue.poll();
            int dist = ans[curr];

            int minJ = Math.max(0, curr - k + 1);
            int maxJ = Math.min(n - k, curr);

            int minNextPos = 2 * minJ + k - 1 - curr;
            int maxNextPos = 2 * maxJ + k - 1 - curr;

            TreeSet<Integer> targetSet = (k % 2 == 1) ? 
                (curr % 2 == 0 ? availableEven : availableOdd) :
                (curr % 2 == 0 ? availableOdd : availableEven);

            List<Integer> neighbors = new ArrayList<>();
            for (Integer nextPos : targetSet.subSet(minNextPos, true, maxNextPos, true)) {
                neighbors.add(nextPos);
            }

            for (Integer neighbor : neighbors) {
                ans[neighbor] = dist + 1;
                queue.offer(neighbor);
                targetSet.remove(neighbor);
            }
        }

        return ans;
    }
}
```
### Algorithm
- Initialize data structures: `answer` array, `banned` set, and a BFS queue.
- Create two `TreeSet`s (ordered sets), one for available even indices (`availableEven`) and one for available odd indices (`availableOdd`).
- Populate these `TreeSet`s with all indices from `0` to `n-1` that are not in the `banned` set.
- Start the BFS: add `p` to the queue, set `answer[p] = 0`, and remove `p` from its corresponding `TreeSet`.
- While the queue is not empty:
  - Dequeue the current position `u` and its distance `d`.
  - Calculate the range of possible next positions, `[min_v, max_v]`, based on the possible start indices `j` of the reversal subarray.
  - Determine the parity of the neighbors. If `k` is odd, neighbors have the same parity as `u`. If `k` is even, they have the opposite parity. Select the corresponding `TreeSet` to search.
  - Use the `TreeSet.subSet(min_v, true, max_v, true)` method to efficiently get an iterable view of all available neighbors within the calculated range.
  - Iterate through this view. For each neighbor `v` found:
    - Set `answer[v] = d + 1`.
    - Enqueue `v`.
    - Add `v` to a temporary list for removal.
  - After iterating, remove all found neighbors from the `TreeSet` to mark them as visited.

# Solutions
### Java

```java
class Solution {
public
  int[] minReverseOperations(int n, int p, int[] banned, int k) {
    int[] ans = new int[n];
    TreeSet<Integer>[] ts = new TreeSet[]{new TreeSet<>(), new TreeSet<>()};
    for (int i = 0; i < n; ++i) {
      ts[i % 2].add(i);
      ans[i] = i == p ? 0 : -1;
    }
    ts[p % 2].remove(p);
    for (int i : banned) {
      ts[i % 2].remove(i);
    }
    ts[0].add(n);
    ts[1].add(n);
    Deque<Integer> q = new ArrayDeque<>();
    q.offer(p);
    while (!q.isEmpty()) {
      int i = q.poll();
      int mi = Math.max(i - k + 1, k - i - 1);
      int mx = Math.min(i + k - 1, n * 2 - k - i - 1);
      var s = ts[mi % 2];
      for (int j = s.ceiling(mi); j <= mx; j = s.ceiling(mi)) {
        q.offer(j);
        ans[j] = ans[i] + 1;
        s.remove(j);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> minReverseOperations(int n, int p, vector<int> &banned, int k) {
    vector<int> ans(n, -1);
    ans[p] = 0;
    set<int> ts[2];
    for (int i = 0; i < n; ++i) {
      ts[i % 2].insert(i);
    }
    ts[p % 2].erase(p);
    for (int i : banned) {
      ts[i % 2].erase(i);
    }
    ts[0].insert(n);
    ts[1].insert(n);
    queue<int> q{{p}};
    while (!q.empty()) {
      int i = q.front();
      q.pop();
      int mi = max(i - k + 1, k - i - 1);
      int mx = min(i + k - 1, n * 2 - k - i - 1);
      auto &s = ts[mi % 2];
      auto it = s.lower_bound(mi);
      while (*it <= mx) {
        int j = *it;
        ans[j] = ans[i] + 1;
        q.push(j);
        it = s.erase(it);
      }
    }
    return ans;
  }
};

```

### Python

```python
from sortedcontainers import SortedSet class Solution : def minReverseOperations ( self , n : int , p : int , banned : List [ int ], k : int ) -> List [ int ]: ans = [ - 1 ] * n ans [ p ] = 0 ts = [ SortedSet () for _ in range ( 2 )] for i in range ( n ): ts [ i % 2 ]. add ( i ) ts [ p % 2 ]. remove ( p ) for i in banned : ts [ i % 2 ]. remove ( i ) ts [ 0 ]. add ( n ) ts [ 1 ]. add ( n ) q = deque ([ p ]) while q : i = q . popleft () mi = max ( i - k + 1 , k - i - 1 ) mx = min ( i + k - 1 , n * 2 - k - i - 1 ) s = ts [ mi % 2 ] j = s . bisect_left ( mi ) while s [ j ] <= mx : q . append ( s [ j ]) ans [ s [ j ]] = ans [ i ] + 1 s . remove ( s [ j ]) j = s . bisect_left ( mi ) return ans
```