LeetCode Solutions Blog

Minimum Reverse Operations

Number: 2726

Difficulty: Hard

Paid? No

Problem Description

Given an array of length n where every position is 0 except one position p which is 1, you are allowed to perform a reversal operation on any contiguous subarray of fixed length k as long as the subarray does not contain any banned indices. When you reverse the subarray, the lone 1 will move to a new position determined by the reversal. The goal is to determine, for every index in the array, the minimum number of operations needed to get the 1 there (or –1 if it is impossible).

Key Insights

The reversal operation with fixed size k implies that if the current index is i and you reverse a subarray covering i, then the new index j of the 1 is computed by the formula: j = 2*s + k - 1 - i, where s is the starting position of the subarray.
For a valid reversal, the starting index s must satisfy: max(0, i - k + 1) ≤ s ≤ min(i, n - k).
Thus, from index i, the 1 can move to any index j in the range: [2 * max(0, i - k + 1) + k - 1 - i, 2 * min(i, n - k) + k - 1 - i].
An important observation is that the parity (odd or even) of the new position j is fixed given i and k (j = k - 1 - i (mod 2)). This helps group indices and efficiently query candidates.
We can use a Breadth First Search (BFS) starting at position p, and maintain two ordered sets (or sorted lists) for unvisited indices (grouped by parity) so that we can quickly remove and iterate over all indices within a queried interval.

Space and Time Complexity

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

Solution

We solve the problem using a BFS traversal where each state is the current position of the 1. For each state (or index) i, we compute the valid range of destination indices j that can be reached by any reversal operation. The transformation is based on choosing a valid subarray starting index s and the formula: j = 2*s + k - 1 - i. Because s moves within a continuous range, the set of reachable j's forms a continuous interval. Moreover, since j is computed as (k - 1 - i) plus an even number, only one parity (even or odd) is possible.
To efficiently find all reachable positions in an interval with the fixed parity, we keep two ordered sets (or sorted collections) for even and odd indices that are allowed (i.e. not banned and not already visited). We then perform BFS from the starting index p, removing and marking the reachable nodes as visited, and updating their distance (number of operations). This yields the minimum number of operations needed for each index.

Code Solutions

from collections import deque
import bisect

# We simulate an ordered set using a sorted list.
class SortedList:
    def __init__(self):
        self.list = []
    def add(self, value):
        bisect.insort(self.list, value)
    def remove(self, value):
        index = bisect.bisect_left(self.list, value)
        if index < len(self.list) and self.list[index] == value:
            self.list.pop(index)
    # returns indices in the sorted list that lie in [low, high]
    def query(self, low, high):
        l = bisect.bisect_left(self.list, low)
        r = bisect.bisect_right(self.list, high)
        # return a copy of the found segment
        return self.list[l:r]
    # remove all values in sorted order between low and high
    def remove_range(self, low, high):
        l = bisect.bisect_left(self.list, low)
        r = bisect.bisect_right(self.list, high)
        res = self.list[l:r]
        self.list[l:r] = []   # remove them
        return res

def minReverseOperations(n, p, banned, k):
    # initialize answer array with -1, except start position p has 0 operations
    ans = [-1] * n
    ans[p] = 0

    bannedSet = set(banned)
    
    # Two SortedLists for indices that are allowed (i.e. not banned and not visited) grouped by parity
    evenList = SortedList()
    oddList = SortedList()
    
    for i in range(n):
        if i in bannedSet or i == p:
            continue
        if i % 2 == 0:
            evenList.add(i)
        else:
            oddList.add(i)
            
    q = deque([p])
    
    while q:
        cur = q.popleft()
        cur_steps = ans[cur]
        
        # Compute the allowed range of starting indices s for the reversal subarray which covers index cur:
        s_min = max(0, cur - k + 1)
        s_max = min(cur, n - k)
        # then, the new index after reversal is: j = 2*s + k - 1 - cur.
        # minimal possible j
        j_low = 2 * s_min + k - 1 - cur
        # maximum possible j
        j_high = 2 * s_max + k - 1 - cur
        
        # The new index j will have the parity of (k - 1 - cur) mod 2.
        target_parity = (k - 1 - cur) & 1

        if target_parity == 0:
            candidates = evenList.remove_range(j_low, j_high)
        else:
            candidates = oddList.remove_range(j_low, j_high)
        
        for new_idx in candidates:
            if ans[new_idx] == -1:  # not visited yet
                ans[new_idx] = cur_steps + 1
                q.append(new_idx)
    
    return ans

# Example Usage:
print(minReverseOperations(4, 0, [1,2], 4))  # Expected Output: [0,-1,-1,1]
print(minReverseOperations(5, 0, [2,4], 3))  # Expected Output: [0,-1,-1,-1,-1]
print(minReverseOperations(4, 2, [0,1,3], 1))  # Expected Output: [-1,-1,0,-1]