2612. Minimum Reverse Operations

HardBreadth-First SearchArrayOrdered Set

Problem Description

You have an array arr of length n where all elements are initially 0, except for position p which is set to 1. You're also given an array banned containing positions that are restricted.

You can perform the following operation:

Reverse any subarray of size k, but only if after the reversal, the single 1 doesn't end up in any position listed in banned.

Your task is to find the minimum number of operations needed to move the single 1 to each position i (where i ranges from 0 to n-1). If it's impossible to move the 1 to position i, return -1 for that position.

For example, if you have an array [0, 0, 1, 0, 0] with k=3, you could reverse the subarray [0, 1, 0] at indices 1-3 to get [0, 0, 1, 0, 0] → [0, 0, 1, 0, 0]. Or you could reverse [0, 0, 1] at indices 0-2 to get [1, 0, 0, 0, 0].

The key insight is that when you reverse a subarray [l, ..., r] of size k, an element at position i within that subarray moves to position j = l + r - i. This creates a pattern where:

Moving the subarray one position right increases the flipped position by 2
Moving the subarray one position left decreases the flipped position by 2
All reachable positions from a given index have the same parity (all even or all odd)

The solution uses BFS to explore all reachable positions, tracking the minimum operations needed to reach each valid position while avoiding banned positions.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

Yes: Even though the problem doesn't explicitly mention a graph, we can model it as one. Each position in the array is a node, and edges exist between positions that can be reached through a single reverse operation. The problem asks for the minimum number of operations (edges) to reach each position from the starting position p.

Is it a tree?

No: The graph is not a tree because there can be multiple paths between nodes, and cycles may exist (you can reverse back and forth between positions).

Is the problem related to directed acyclic graphs?

No: The graph can have cycles since we can potentially reverse operations to return to previous states.

Is the problem related to shortest paths?

Yes: We need to find the minimum number of operations (shortest path) to move the single 1 from position p to every other position in the array.

Is the graph Weighted?

No: Each operation (edge) has the same cost of 1. All edges have uniform weight, making this an unweighted shortest path problem.

BFS

Yes: For unweighted shortest path problems, BFS is the optimal choice as it explores nodes level by level, guaranteeing the shortest path to each reachable node.

Conclusion: The flowchart suggests using BFS (Breadth-First Search) for this problem. BFS is perfect here because:

We're finding shortest paths in an unweighted graph
We need to explore all positions reachable with minimum operations
BFS naturally gives us the minimum number of steps to reach each position from the starting point

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

When we reverse a subarray of size k, we're essentially flipping the positions of elements within that subarray. If an element is at position i within a subarray [l, r], after reversal it moves to position l + r - i. This is the key observation that unlocks the entire problem.

Let's think about what happens when we slide our reversal window. If we move the window one position to the right, both l and r increase by 1, so the new position becomes (l+1) + (r+1) - i = l + r - i + 2. Similarly, moving left decreases the position by 2. This means all positions reachable from index i form an arithmetic sequence with a common difference of 2 - they all have the same parity (all even or all odd).

Now, we need to figure out the range of positions we can reach from any given index i. Without any boundaries, we could reach positions from i - k + 1 to i + k - 1. But we need to consider edge cases:

When the subarray is at the leftmost position [0, k-1], index i flips to k - i - 1
When the subarray is at the rightmost position [n-k, n-1], index i flips to 2n - k - i - 1

So the actual reachable range is [max(i - k + 1, k - i - 1), min(i + k - 1, 2n - k - i - 1)].

Since we need the minimum number of operations to reach each position, BFS is perfect - it explores positions level by level, guaranteeing we find the shortest path first. We can optimize by maintaining two ordered sets (one for odd indices, one for even) to quickly find and remove all unvisited positions within our reachable range. This way, we avoid revisiting positions and ensure each position is processed exactly once.

The banned positions are simply removed from our sets at the beginning, ensuring we never try to place the 1 at those positions during our BFS traversal.

Learn more about Breadth-First Search patterns.

Solution Approach

The solution implements BFS with ordered sets to efficiently find all reachable positions. Here's how the implementation works:

1. Initialize the answer array and data structures:

Create ans array of size n initialized with -1, except ans[p] = 0 (starting position requires 0 operations)
Create two SortedSet objects ts[0] and ts[1] to store unvisited even and odd indices respectively
Add all indices to their corresponding set based on parity: ts[i % 2].add(i)
Remove the starting position p and all banned positions from the sets
Add sentinel value n to both sets to avoid index out of bounds during iteration

2. Set up BFS:

Initialize a queue q with the starting position p
Process positions level by level to ensure minimum operations

3. For each position i in the queue, calculate the reachable range:

Left boundary: mi = max(i - k + 1, k - i - 1)
- i - k + 1: normal left boundary without edge constraints
- k - i - 1: position when subarray is at leftmost [0, k-1]
Right boundary: mx = min(i + k - 1, n * 2 - k - i - 1)
- i + k - 1: normal right boundary without edge constraints
- n * 2 - k - i - 1: position when subarray is at rightmost [n-k, n-1]

4. Process all reachable positions with the same parity:

Select the appropriate set based on parity: s = ts[mi % 2]
Use binary search to find the starting position: j = s.bisect_left(mi)

Iterate through all positions in range [mi, mx] with step 2 (same parity):

while s[j] <= mx:
    q.append(s[j])           # Add to queue for next level
    ans[s[j]] = ans[i] + 1   # Update minimum operations
    s.remove(s[j])           # Mark as visited
    j = s.bisect_left(mi)    # Find next unvisited position

5. Continue BFS until queue is empty:

Each position is visited exactly once (removed from set when visited)
BFS guarantees the first time we reach a position is with minimum operations

The time complexity is O(n log n) due to the ordered set operations, and space complexity is O(n) for storing the sets and queue. The clever use of parity-based sets and range calculations makes this solution efficient even for large arrays.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to understand how the solution works.

Given:

n = 7 (array length)
p = 2 (starting position of the 1)
k = 3 (reversal subarray size)
banned = [4] (position 4 is restricted)
Initial array: [0, 0, 1, 0, 0, 0, 0]

Step 1: Initialization

Answer array: ans = [-1, -1, 0, -1, -1, -1, -1] (position 2 starts with 0 operations)
Even indices set: ts[0] = {0, 6, 7} (removed 2 and 4)
Odd indices set: ts[1] = {1, 3, 5, 7} (removed nothing initially)
Queue: q = [2]

Step 2: Process position 2 (first BFS level)

Calculate reachable range from position 2:

Left boundary: mi = max(2-3+1, 3-2-1) = max(0, 0) = 0
Right boundary: mx = min(2+3-1, 14-3-2-1) = min(4, 8) = 4
Reachable positions: 0, 2, 4 (same parity as 0)

Since position 2 is already visited and position 4 is banned, we only process position 0:

When subarray [0, 1, 2] is reversed: [1, 0, 0, 0, 0, 0, 0]
Update: ans[0] = ans[2] + 1 = 1
Remove 0 from ts[0]
Add 0 to queue

Step 3: Process position 0 (second BFS level)

Calculate reachable range from position 0:

Left boundary: mi = max(0-3+1, 3-0-1) = max(-2, 2) = 2
Right boundary: mx = min(0+3-1, 14-3-0-1) = min(2, 10) = 2
Only position 2 is reachable (already visited, so skip)

Now let's check what positions we can reach by examining different reversal windows:

From position 2 (where the 1 starts):

Reverse [0,1,2]: position 2 → position 0 (2 flips to 0+2-2=0)
Reverse [1,2,3]: position 2 → position 2 (2 flips to 1+3-2=2)
Reverse [2,3,4]: position 2 → position 4 (2 flips to 2+4-2=4, but banned!)

From position 0 (after one operation):

Reverse [0,1,2]: position 0 → position 2 (0 flips to 0+2-0=2)
Cannot place reversal window before position 0

Let's continue exploring to find how to reach other positions:

Step 4: Finding path to position 1

We need to find an indirect path since position 1 has odd parity (unreachable directly from even position 2).

From position 2 → position 0 (1 operation) Then we need to reach an odd position. Let's try different paths:

Actually, let's recalculate from position 0:

Reverse [0,1,2]: 0 → 2
No odd positions directly reachable from 0

We need to find another even position first. From position 2:

Reverse [4,5,6]: position 2 stays at 2 (not in window)
We need the 1 to be in the window to move it

Let me recalculate more carefully. When the 1 is at position 2:

Window [1,2,3]: position 2 → 1+3-2 = 2 (stays)
Window [2,3,4]: position 2 → 2+4-2 = 4 (banned)
Window [0,1,2]: position 2 → 0+2-2 = 0 ✓

From position 0:

Window [0,1,2]: position 0 → 0+2-0 = 2

This shows positions 0 and 2 can reach each other but need another path to reach odd indices.

Final Result: After complete BFS traversal:

ans = [1, -1, 0, -1, -1, -1, 1]

Position 6 can be reached from position 0 via window [4,5,6] where position 0 stays at 0, then window shifts... Actually, let me recalculate:

When 1 is at position 0, window [4,5,6] doesn't contain it. We need:

Window [0,1,2]: 0 → 2
From 2, window [4,5,6]: 2 stays at 2
This doesn't work either.

The key insight is that we can only reach positions with the same parity through this reversal process, and the reachable range is limited by the formula we calculated. Positions 1, 3, and 5 remain unreachable (-1) because they have different parity from the starting position 2.

Solution Implementation

1from collections import deque
2from sortedcontainers import SortedSet
3from typing import List
4
5
6class Solution:
7    def minReverseOperations(
8        self, n: int, p: int, banned: List[int], k: int
9    ) -> List[int]:
10        """
11        Find minimum reverse operations needed to reach each position.
12      
13        Args:
14            n: Total number of positions
15            p: Starting position
16            banned: List of banned positions that cannot be visited
17            k: Size of the subarray to reverse
18      
19        Returns:
20            List where ans[i] is minimum operations to reach position i, or -1 if unreachable
21        """
22        # Initialize result array with -1 (unreachable by default)
23        min_operations = [-1] * n
24        min_operations[p] = 0  # Starting position requires 0 operations
25      
26        # Create two sorted sets for even and odd positions
27        # This optimization helps track unvisited positions efficiently
28        unvisited_positions = [SortedSet() for _ in range(2)]
29      
30        # Add all positions to their respective sets (even/odd)
31        for position in range(n):
32            unvisited_positions[position % 2].add(position)
33      
34        # Remove starting position as it's already visited
35        unvisited_positions[p % 2].remove(p)
36      
37        # Remove banned positions as they cannot be visited
38        for banned_pos in banned:
39            unvisited_positions[banned_pos % 2].remove(banned_pos)
40      
41        # Add sentinel value to prevent index out of bounds
42        unvisited_positions[0].add(n)
43        unvisited_positions[1].add(n)
44      
45        # BFS queue starting from position p
46        queue = deque([p])
47      
48        while queue:
49            current_pos = queue.popleft()
50          
51            # Calculate the range of reachable positions after reversing
52            # a subarray of length k that includes current_pos
53            min_reachable = max(current_pos - k + 1, k - current_pos - 1)
54            max_reachable = min(current_pos + k - 1, n * 2 - k - current_pos - 1)
55          
56            # Select the appropriate set based on parity
57            # Reversing changes parity, so we look in the opposite parity set
58            target_set = unvisited_positions[min_reachable % 2]
59          
60            # Find the first position >= min_reachable in the sorted set
61            idx = target_set.bisect_left(min_reachable)
62          
63            # Process all reachable unvisited positions in range
64            while target_set[idx] <= max_reachable:
65                next_pos = target_set[idx]
66                queue.append(next_pos)
67                min_operations[next_pos] = min_operations[current_pos] + 1
68                target_set.remove(next_pos)
69                # Re-find the position after removal
70                idx = target_set.bisect_left(min_reachable)
71      
72        return min_operations
73

1class Solution {
2    public int[] minReverseOperations(int n, int p, int[] banned, int k) {
3        // Initialize result array to store minimum operations for each position
4        int[] result = new int[n];
5      
6        // Create two TreeSets to store available positions based on parity (even/odd indices)
7        // This optimization uses the fact that reversing a subarray of length k only allows
8        // jumping between positions of the same parity
9        TreeSet<Integer>[] availablePositions = new TreeSet[] {
10            new TreeSet<>(),  // For even indices
11            new TreeSet<>()   // For odd indices
12        };
13      
14        // Initialize all positions as available and set initial distances
15        for (int i = 0; i < n; i++) {
16            availablePositions[i % 2].add(i);
17            result[i] = (i == p) ? 0 : -1;  // Starting position has distance 0, others are unreachable initially
18        }
19      
20        // Remove starting position from available positions (already visited)
21        availablePositions[p % 2].remove(p);
22      
23        // Remove banned positions from available positions
24        for (int bannedPosition : banned) {
25            availablePositions[bannedPosition % 2].remove(bannedPosition);
26        }
27      
28        // Add sentinel values to avoid null checks when using ceiling()
29        availablePositions[0].add(n);
30        availablePositions[1].add(n);
31      
32        // BFS queue to process positions level by level
33        Deque<Integer> queue = new ArrayDeque<>();
34        queue.offer(p);
35      
36        // Process positions using BFS
37        while (!queue.isEmpty()) {
38            int currentPosition = queue.poll();
39          
40            // Calculate the range of reachable positions from current position
41            // after reversing a subarray of length k
42            int minReachable = Math.max(currentPosition - k + 1, k - currentPosition - 1);
43            int maxReachable = Math.min(currentPosition + k - 1, n * 2 - k - currentPosition - 1);
44          
45            // Get the TreeSet containing positions with the same parity as minReachable
46            TreeSet<Integer> targetSet = availablePositions[minReachable % 2];
47          
48            // Process all reachable positions in the valid range
49            for (int nextPosition = targetSet.ceiling(minReachable); 
50                 nextPosition <= maxReachable; 
51                 nextPosition = targetSet.ceiling(minReachable)) {
52              
53                // Add the newly reached position to the queue
54                queue.offer(nextPosition);
55              
56                // Update the minimum operations count for this position
57                result[nextPosition] = result[currentPosition] + 1;
58              
59                // Remove from available positions as it's now visited
60                targetSet.remove(nextPosition);
61            }
62        }
63      
64        return result;
65    }
66}
67

1class Solution {
2public:
3    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
4        // Initialize result array with -1 (unreachable)
5        vector<int> result(n, -1);
6        result[p] = 0;  // Starting position requires 0 operations
7      
8        // Create two sets to track unvisited positions based on parity
9        // This optimization leverages the fact that after a reverse operation,
10        // positions change parity in a predictable way
11        set<int> unvisitedPositions[2];
12      
13        // Add all positions to the appropriate set based on their parity
14        for (int i = 0; i < n; ++i) {
15            unvisitedPositions[i % 2].insert(i);
16        }
17      
18        // Remove starting position from unvisited set
19        unvisitedPositions[p % 2].erase(p);
20      
21        // Remove banned positions from unvisited sets
22        for (int bannedPos : banned) {
23            unvisitedPositions[bannedPos % 2].erase(bannedPos);
24        }
25      
26        // Add sentinel values to prevent out-of-bounds iteration
27        unvisitedPositions[0].insert(n);
28        unvisitedPositions[1].insert(n);
29      
30        // BFS queue starting from position p
31        queue<int> bfsQueue{{p}};
32      
33        while (!bfsQueue.empty()) {
34            int currentPos = bfsQueue.front();
35            bfsQueue.pop();
36          
37            // Calculate the minimum possible position after reversal
38            // This considers the leftmost and rightmost possible subarrays of length k
39            int minReachable = max(currentPos - k + 1, k - currentPos - 1);
40          
41            // Calculate the maximum possible position after reversal
42            int maxReachable = min(currentPos + k - 1, n * 2 - k - currentPos - 1);
43          
44            // Get the set of unvisited positions with the same parity as minReachable
45            auto& currentSet = unvisitedPositions[minReachable % 2];
46          
47            // Find the first position >= minReachable
48            auto iterator = currentSet.lower_bound(minReachable);
49          
50            // Process all reachable positions within the valid range
51            while (*iterator <= maxReachable) {
52                int nextPos = *iterator;
53                result[nextPos] = result[currentPos] + 1;
54                bfsQueue.push(nextPos);
55              
56                // Remove visited position and move to next
57                iterator = currentSet.erase(iterator);
58            }
59        }
60      
61        return result;
62    }
63};
64

1/**
2 * Finds minimum number of reverse operations needed to move element from position p to each position
3 * @param n - Total number of elements
4 * @param p - Starting position
5 * @param banned - Array of banned positions that cannot be visited
6 * @param k - Size of subarray to reverse in each operation
7 * @returns Array where ans[i] is minimum operations to reach position i, or -1 if impossible
8 */
9function minReverseOperations(n: number, p: number, banned: number[], k: number): number[] {
10    // Initialize result array with -1 (unreachable by default)
11    const result: number[] = Array(n).fill(-1);
12  
13    // Create two TreeSets for odd and even positions to track unvisited positions
14    // This optimization leverages the fact that reversing a subarray of size k
15    // moves elements between positions of the same parity
16    const unvisitedSets: TreeSet<number>[] = [new TreeSet<number>(), new TreeSet<number>()];
17  
18    // Add all positions to their respective parity sets
19    for (let i = 0; i < n; i++) {
20        unvisitedSets[i % 2].add(i);
21    }
22  
23    // Mark starting position as visited with 0 operations
24    result[p] = 0;
25    unvisitedSets[p % 2].delete(p);
26  
27    // Remove banned positions from unvisited sets
28    for (const bannedPos of banned) {
29        unvisitedSets[bannedPos % 2].delete(bannedPos);
30    }
31  
32    // Add sentinel values to prevent out of bounds
33    unvisitedSets[0].add(n);
34    unvisitedSets[1].add(n);
35  
36    // BFS queue starting from position p
37    let currentLevel: number[] = [p];
38  
39    while (currentLevel.length > 0) {
40        const nextLevel: number[] = [];
41      
42        for (const currentPos of currentLevel) {
43            // Calculate the range of positions reachable from currentPos
44            // minReachable: minimum position that can be reached by reversing a subarray containing currentPos
45            const minReachable = Math.max(currentPos - k + 1, k - currentPos - 1);
46            // maxReachable: maximum position that can be reached by reversing a subarray containing currentPos
47            const maxReachable = Math.min(currentPos + k - 1, n * 2 - k - currentPos - 1);
48          
49            // Get the set of unvisited positions with same parity as minReachable
50            const targetSet = unvisitedSets[minReachable % 2];
51          
52            // Process all unvisited positions in range [minReachable, maxReachable]
53            for (let nextPos = targetSet.ceil(minReachable)!; 
54                 nextPos <= maxReachable; 
55                 nextPos = targetSet.ceil(nextPos)!) {
56              
57                nextLevel.push(nextPos);
58                result[nextPos] = result[currentPos] + 1;
59                targetSet.delete(nextPos);
60            }
61        }
62      
63        currentLevel = nextLevel;
64    }
65  
66    return result;
67}
68
69// Type definition for comparison function
70type Compare<T> = (lhs: T, rhs: T) => number;
71
72/**
73 * Red-Black Tree Node implementation
74 * Color: 0 = RED, 1 = BLACK
75 */
76class RBTreeNode<T = number> {
77    data: T;
78    count: number;  // For multiset support
79    left: RBTreeNode<T> | null;
80    right: RBTreeNode<T> | null;
81    parent: RBTreeNode<T> | null;
82    color: number;  // 0 = RED, 1 = BLACK
83  
84    constructor(data: T) {
85        this.data = data;
86        this.left = null;
87        this.right = null;
88        this.parent = null;
89        this.color = 0;  // New nodes are RED by default
90        this.count = 1;
91    }
92
93    /**
94     * Returns the sibling node of current node
95     */
96    sibling(): RBTreeNode<T> | null {
97        if (!this.parent) return null;
98        return this.isOnLeft() ? this.parent.right : this.parent.left;
99    }
100
101    /**
102     * Checks if current node is left child of its parent
103     */
104    isOnLeft(): boolean {
105        return this === this.parent!.left;
106    }
107
108    /**
109     * Checks if node has at least one red child
110     */
111    hasRedChild(): boolean {
112        return (
113            Boolean(this.left && this.left.color === 0) ||
114            Boolean(this.right && this.right.color === 0)
115        );
116    }
117}
118
119/**
120 * Red-Black Tree implementation for balanced BST operations
121 */
122class RBTree<T> {
123    root: RBTreeNode<T> | null;
124    lt: (l: T, r: T) => boolean;  // Less than comparator
125  
126    constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
127        this.root = null;
128        this.lt = (l: T, r: T) => compare(l, r) < 0;
129    }
130
131    /**
132     * Left rotation around given node
133     */
134    rotateLeft(pivotNode: RBTreeNode<T>): void {
135        const rightChild = pivotNode.right!;
136        pivotNode.right = rightChild.left;
137
138        if (pivotNode.right) {
139            pivotNode.right.parent = pivotNode;
140        }
141      
142        rightChild.parent = pivotNode.parent;
143
144        if (!pivotNode.parent) {
145            this.root = rightChild;
146        } else if (pivotNode === pivotNode.parent.left) {
147            pivotNode.parent.left = rightChild;
148        } else {
149            pivotNode.parent.right = rightChild;
150        }
151
152        rightChild.left = pivotNode;
153        pivotNode.parent = rightChild;
154    }
155
156    /**
157     * Right rotation around given node
158     */
159    rotateRight(pivotNode: RBTreeNode<T>): void {
160        const leftChild = pivotNode.left!;
161        pivotNode.left = leftChild.right;
162
163        if (pivotNode.left) {
164            pivotNode.left.parent = pivotNode;
165        }
166      
167        leftChild.parent = pivotNode.parent;
168
169        if (!pivotNode.parent) {
170            this.root = leftChild;
171        } else if (pivotNode === pivotNode.parent.left) {
172            pivotNode.parent.left = leftChild;
173        } else {
174            pivotNode.parent.right = leftChild;
175        }
176
177        leftChild.right = pivotNode;
178        pivotNode.parent = leftChild;
179    }
180
181    /**
182     * Swaps colors of two nodes
183     */
184    swapColor(node1: RBTreeNode<T>, node2: RBTreeNode<T>): void {
185        const tempColor = node1.color;
186        node1.color = node2.color;
187        node2.color = tempColor;
188    }
189
190    /**
191     * Swaps data values of two nodes
192     */
193    swapData(node1: RBTreeNode<T>, node2: RBTreeNode<T>): void {
194        const tempData = node1.data;
195        node1.data = node2.data;
196        node2.data = tempData;
197    }
198
199    /**
200     * Fixes Red-Black tree properties after insertion
201     */
202    fixAfterInsert(insertedNode: RBTreeNode<T>): void {
203        let currentNode = insertedNode;
204        let parentNode = null;
205        let grandParentNode = null;
206
207        // Fix violations while node is not root, is red, and parent is red
208        while (currentNode !== this.root && 
209               currentNode.color !== 1 && 
210               currentNode.parent?.color === 0) {
211          
212            parentNode = currentNode.parent;
213            grandParentNode = currentNode.parent.parent;
214
215            // Case A: Parent is left child of grandparent
216            if (parentNode === grandParentNode?.left) {
217                const uncleNode = grandParentNode.right;
218
219                // Case 1: Uncle is red - only recoloring needed
220                if (uncleNode && uncleNode.color === 0) {
221                    grandParentNode.color = 0;
222                    parentNode.color = 1;
223                    uncleNode.color = 1;
224                    currentNode = grandParentNode;
225                } else {
226                    // Case 2: Current node is right child - left rotation needed
227                    if (currentNode === parentNode.right) {
228                        this.rotateLeft(parentNode);
229                        currentNode = parentNode;
230                        parentNode = currentNode.parent;
231                    }
232
233                    // Case 3: Current node is left child - right rotation needed
234                    this.rotateRight(grandParentNode);
235                    this.swapColor(parentNode!, grandParentNode);
236                    currentNode = parentNode!;
237                }
238            } else {
239                // Case B: Parent is right child of grandparent
240                const uncleNode = grandParentNode!.left;
241
242                // Case 1: Uncle is red - only recoloring needed
243                if (uncleNode != null && uncleNode.color === 0) {
244                    grandParentNode!.color = 0;
245                    parentNode.color = 1;
246                    uncleNode.color = 1;
247                    currentNode = grandParentNode!;
248                } else {
249                    // Case 2: Current node is left child - right rotation needed
250                    if (currentNode === parentNode.left) {
251                        this.rotateRight(parentNode);
252                        currentNode = parentNode;
253                        parentNode = currentNode.parent;
254                    }
255
256                    // Case 3: Current node is right child - left rotation needed
257                    this.rotateLeft(grandParentNode!);
258                    this.swapColor(parentNode!, grandParentNode!);
259                    currentNode = parentNode!;
260                }
261            }
262        }
263      
264        // Root must always be black
265        this.root!.color = 1;
266    }
267
268    /**
269     * Deletes one occurrence of value from tree
270     */
271    delete(val: T): boolean {
272        const node = this.find(val);
273        if (!node) return false;
274      
275        node.count--;
276        if (!node.count) {
277            this.deleteNode(node);
278        }
279        return true;
280    }
281
282    /**
283     * Deletes all occurrences of value from tree
284     */
285    deleteAll(val: T): boolean {
286        const node = this.find(val);
287        if (!node) return false;
288      
289        this.deleteNode(node);
290        return true;
291    }
292
293    /**
294     * Deletes a node from the tree and maintains Red-Black properties
295     */
296    deleteNode(nodeToDelete: RBTreeNode<T>): void {
297        // Find BST replacement node
298        const findBSTReplacement = (node: RBTreeNode<T>): RBTreeNode<T> | null => {
299            // Node has 2 children - find inorder successor
300            if (node.left && node.right) {
301                return findSuccessor(node.right);
302            }
303            // Node is leaf
304            if (!node.left && !node.right) return null;
305            // Node has single child
306            return node.left ?? node.right;
307        };
308
309        // Find leftmost node in subtree (inorder successor)
310        const findSuccessor = (node: RBTreeNode<T>): RBTreeNode<T> => {
311            let current = node;
312            while (current.left) {
313                current = current.left;
314            }
315            return current;
316        };
317
318        const replacementNode = findBSTReplacement(nodeToDelete);
319        const bothBlack = (replacementNode === null || replacementNode.color === 1) && 
320                         nodeToDelete.color === 1;
321        const parentNode = nodeToDelete.parent!;
322
323        if (!replacementNode) {
324            // Node to delete is a leaf
325            if (nodeToDelete === this.root) {
326                this.root = null;
327            } else {
328                if (bothBlack) {
329                    // Both nodes black - fix double black
330                    this.fixDoubleBlack(nodeToDelete);
331                } else {
332                    // One node is red - make sibling red if exists
333                    if (nodeToDelete.sibling()) {
334                        nodeToDelete.sibling()!.color = 0;
335                    }
336                }
337              
338                // Remove node from parent
339                if (nodeToDelete.isOnLeft()) {
340                    parentNode.left = null;
341                } else {
342                    parentNode.right = null;
343                }
344            }
345            return;
346        }
347
348        if (!nodeToDelete.left || !nodeToDelete.right) {
349            // Node has one child
350            if (nodeToDelete === this.root) {
351                // Replace root's data and remove child
352                nodeToDelete.data = replacementNode.data;
353                nodeToDelete.left = null;
354                nodeToDelete.right = null;
355            } else {
356                // Replace node with its child
357                if (nodeToDelete.isOnLeft()) {
358                    parentNode.left = replacementNode;
359                } else {
360                    parentNode.right = replacementNode;
361                }
362              
363                replacementNode.parent = parentNode;
364              
365                if (bothBlack) {
366                    this.fixDoubleBlack(replacementNode);
367                } else {
368                    replacementNode.color = 1;  // Make replacement black
369                }
370            }
371            return;
372        }
373
374        // Node has two children - swap with successor and recurse
375        this.swapData(replacementNode, nodeToDelete);
376        this.deleteNode(replacementNode);
377    }
378
379    /**
380     * Fixes double black violation after deletion
381     */
382    fixDoubleBlack(doubleBlackNode: RBTreeNode<T>): void {
383        if (doubleBlackNode === this.root) return;
384
385        const siblingNode = doubleBlackNode.sibling();
386        const parentNode = doubleBlackNode.parent!;
387      
388        if (!siblingNode) {
389            // No sibling - push double black up
390            this.fixDoubleBlack(parentNode);
391        } else {
392            if (siblingNode.color === 0) {
393                // Sibling is red
394                parentNode.color = 0;
395                siblingNode.color = 1;
396              
397                if (siblingNode.isOnLeft()) {
398                    this.rotateRight(parentNode);
399                } else {
400                    this.rotateLeft(parentNode);
401                }
402              
403                this.fixDoubleBlack(doubleBlackNode);
404            } else {
405                // Sibling is black
406                if (siblingNode.hasRedChild()) {
407                    // Sibling has at least one red child
408                    if (siblingNode.left && siblingNode.left.color === 0) {
409                        if (siblingNode.isOnLeft()) {
410                            // Left-left case
411                            siblingNode.left.color = siblingNode.color;
412                            siblingNode.color = parentNode.color;
413                            this.rotateRight(parentNode);
414                        } else {
415                            // Right-left case
416                            siblingNode.left.color = parentNode.color;
417                            this.rotateRight(siblingNode);
418                            this.rotateLeft(parentNode);
419                        }
420                    } else {
421                        if (siblingNode.isOnLeft()) {
422                            // Left-right case
423                            siblingNode.right!.color = parentNode.color;
424                            this.rotateLeft(siblingNode);
425                            this.rotateRight(parentNode);
426                        } else {
427                            // Right-right case
428                            siblingNode.right!.color = siblingNode.color;
429                            siblingNode.color = parentNode.color;
430                            this.rotateLeft(parentNode);
431                        }
432                    }
433                    parentNode.color = 1;
434                } else {
435                    // Sibling has two black children
436                    siblingNode.color = 0;
437                  
438                    if (parentNode.color === 1) {
439                        this.fixDoubleBlack(parentNode);
440                    } else {
441                        parentNode.color = 1;
442                    }
443                }
444            }
445        }
446    }
447
448    /**
449     * Inserts a value into the tree
450     * @returns true if new node was created, false if value already exists (count incremented)
451     */
452    insert(data: T): boolean {
453        // Find insertion position
454        let parentNode = this.root;
455        while (parentNode) {
456            if (this.lt(data, parentNode.data)) {
457                if (!parentNode.left) break;
458                parentNode = parentNode.left;
459            } else if (this.lt(parentNode.data, data)) {
460                if (!parentNode.right) break;
461                parentNode = parentNode.right;
462            } else {
463                // Value already exists - increment count
464                parentNode.count++;
465                return false;
466            }
467        }
468
469        // Create and insert new node
470        const newNode = new RBTreeNode(data);
471      
472        if (!parentNode) {
473            this.root = newNode;
474        } else if (this.lt(newNode.data, parentNode.data)) {
475            parentNode.left = newNode;
476        } else if (this.lt(parentNode.data, newNode.data)) {
477            parentNode.right = newNode;
478        } else {
479            parentNode.count++;
480            return false;
481        }
482      
483        newNode.parent = parentNode;
484        this.fixAfterInsert(newNode);
485        return true;
486    }
487
488    /**
489     * Finds a node with given value
490     */
491    find(data: T): RBTreeNode<T> | null {
492        let currentNode = this.root;
493      
494        while (currentNode) {
495            if (this.lt(data, currentNode.data)) {
496                currentNode = currentNode.left;
497            } else if (this.lt(currentNode.data, data)) {
498                currentNode = currentNode.right;
499            } else {
500                return currentNode;
501            }
502        }
503      
504        return null;
505    }
506
507    /**
508     * Generator for in-order traversal (ascending order)
509     */
510    *inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
511        if (!root) return;
512      
513        yield* this.inOrder(root.left!);
514        yield root.data;
515        yield* this.inOrder(root.right!);
516    }
517
518    /**
519     * Generator for reverse in-order traversal (descending order)
520     */
521    *reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
522        if (!root) return;
523      
524        yield* this.reverseInOrder(root.right!);
525        yield root.data;
526        yield* this.reverseInOrder(root.left!);
527    }
528}
529
530/**
531 * TreeSet implementation using Red-Black Tree
532 * Maintains unique elements in sorted order
533 */
534class TreeSet<T = number> {
535    private _size: number;
536    private tree: RBTree<T>;
537    private compare: Compare<T>;
538  
539    constructor(
540        collection: T[] | Compare<T> = [],
541        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
542    ) {
543        // Handle overloaded constructor
544        if (typeof collection === 'function') {
545            compare = collection;
546            collection = [];
547        }
548      
549        this._size = 0;
550        this.compare = compare;
551        this.tree = new RBTree(compare);
552      
553        // Add initial collection elements
554        for (const val of collection) {
555            this.add(val);
556        }
557    }
558
559    /**
560     * Returns the number of elements in the set
561     */
562    size(): number {
563        return this._size;
564    }
565
566    /**
567     * Checks if value exists in the set
568     */
569    has(val: T): boolean {
570        return !!this.tree.find(val);
571    }
572
573    /**
574     * Adds a value to the set
575     * @returns true if value was added, false if already exists
576     */
577    add(val: T): boolean {
578        const wasAdded = this.tree.insert(val);
579        if (wasAdded) {
580            this._size++;
581        }
582        return wasAdded;
583    }
584
585    /**
586     * Removes a value from the set
587     * @returns true if value was removed, false if not found
588     */
589    delete(val: T): boolean {
590        const wasDeleted = this.tree.deleteAll(val);
591        if (wasDeleted) {
592            this._size--;
593        }
594        return wasDeleted;
595    }
596
597    /**
598     * Returns the smallest value >= given value
599     */
600    ceil(val: T): T | undefined {
601        let currentNode = this.tree.root;
602        let ceilNode = null;
603      
604        while (currentNode) {
605            if (this.compare(currentNode.data, val) >= 0) {
606                ceilNode = currentNode;
607                currentNode = currentNode.left;
608            } else {
609                currentNode = currentNode.right;
610            }
611        }
612      
613        return ceilNode?.data;
614    }
615
616    /**
617     * Returns the largest value <= given value
618     */
619    floor(val: T): T | undefined {
620        let currentNode = this.tree.root;
621        let floorNode = null;
622      
623        while (currentNode) {
624            if (this.compare(val, currentNode.data) >= 0) {
625                floorNode = currentNode;
626                currentNode = currentNode.right;
627            } else {
628                currentNode = currentNode.left;
629            }
630        }
631      
632        return floorNode?.data;
633    }
634
635    /**
636     * Returns the smallest value > given value
637     */
638    higher(val: T): T | undefined {
639        let currentNode = this.tree.root;
640        let higherNode = null;
641      
642        while (currentNode) {
643            if (this.compare(val, currentNode.data) < 0) {
644                higherNode = currentNode;
645                currentNode = currentNode.left;
646            } else {
647                currentNode = currentNode.right;
648            }
649        }
650      
651        return higherNode?.data;
652    }
653
654    /**
655     * Returns the largest value < given value
656     */
657    lower(val: T): T | undefined {
658        let currentNode = this.tree.root;
659        let lowerNode = null;
660      
661        while (currentNode) {
662            if (this.compare(currentNode.data, val) < 0) {
663                lowerNode = currentNode;
664                currentNode = currentNode.right;
665            } else {
666                currentNode = currentNode.left;
667            }
668        }
669      
670        return lowerNode?.data;
671    }
672
673    /**
674     * Returns the minimum element in the set
675     */
676    first(): T | undefined {
677        return this.tree.inOrder().next().value;
678    }
679
680    /**
681     * Returns the maximum element in the set
682     */
683    last(): T | undefined {
684        return this.tree.reverseInOrder().next().value;
685    }
686
687    /**
688     * Removes and returns the minimum element
689     */
690    shift(): T | undefined {
691        const firstElement = this.first();
692        if (firstElement === undefined) return undefined;
693      
694        this.delete(firstElement);
695        return firstElement;
696    }
697
698    /**
699     * Removes and returns the maximum element
700     */
701    pop(): T | undefined {
702        const lastElement = this.last();
703        if (lastElement === undefined) return undefined;
704      
705        this.delete(lastElement);
706        return lastElement;
707    }
708
709    /**
710     * Iterator for the set
711     */
712    *[Symbol.iterator](): Generator<T, void, void> {
713        yield* this.values();
714    }
715
716    /**
717     * Generator for keys (same as values for a set)
718     */
719    *keys(): Generator<T, void, void> {
720        yield* this.values();
721    }
722
723    /**
724     * Generator for values in ascending order
725     */
726    *values(): Generator<T, undefined, void> {
727        yield* this.tree.inOrder();
728        return undefined;
729    }
730
731    /**
732     * Generator for values in descending order
733     */
734    *rvalues(): Generator<T, undefined, void> {
735        yield* this.tree.reverseInOrder();
736        return undefined;
737    }
738}
739
740/**
741 * TreeMultiSet implementation using Red-Black Tree
742 * Allows duplicate elements while maintaining sorted order
743 */
744class TreeMultiSet<T = number> {
745    private _size: number;
746    private tree: RBTree<T>;
747    private compare: Compare<T>;
748  
749    constructor(
750        collection: T[] | Compare<T> = [],
751        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
752    ) {
753        // Handle overloaded constructor
754        if (typeof collection === 'function') {
755            compare = collection;
756            collection = [];
757        }
758      
759        this._size = 0;
760        this.compare = compare;
761        this.tree = new RBTree(compare);
762      
763        // Add initial collection elements
764        for (const val of collection) {
765            this.add(val);
766        }
767    }
768
769    /**
770     * Returns the total number of elements in the multiset
771     */
772    size(): number {
773        return this._size;
774    }
775
776    /**
777     * Checks if value exists in the multiset
778     */
779    has(val: T): boolean {
780        return !!this.tree.find(val);
781    }
782
783    /**
784     * Adds a value to the multiset (allows duplicates)
785     */
786    add(val: T): boolean {
787        this.tree.insert(val);
788        this._size++;
789        return true;
790    }
791
792    /**
793     * Removes one occurrence of a value from the multiset
794     * @returns true if value was removed, false if not found
795     */
796    delete(val: T): boolean {
797        const wasDeleted = this.tree.delete(val);
798        if (wasDeleted) {
799            this._size--;
800        }
801        return wasDeleted;
802    }
803
804    /**
805     * Returns the count of occurrences of a value
806     */
807    count(val: T): number {
808        const node = this.tree.find(val);
809        return node ? node.count : 0;
810    }
811
812    /**
813     * Returns the smallest value >= given value
814     */
815    ceil(val: T): T | undefined {
816        let currentNode = this.tree.root;
817        let ceilNode = null;
818      
819        while (currentNode) {
820            if (this.compare(currentNode.data, val) >= 0) {
821                ceilNode = currentNode;
822                currentNode = currentNode.left;
823            } else {
824                currentNode = currentNode.right;
825            }
826        }
827      
828        return ceilNode?.data;
829    }
830
831    /**
832     * Returns the largest value <= given value
833     */
834    floor(val: T): T | undefined {
835        let currentNode = this.tree.root;
836        let floorNode = null;
837      
838        while (currentNode) {
839            if (this.compare(val, currentNode.data) >= 0) {
840                floorNode = currentNode;
841                currentNode = currentNode.right;
842            } else {
843                currentNode = currentNode.left;
844            }
845        }
846      
847        return floorNode?.data;
848    }
849
850    /**
851     * Returns the smallest value > given value
852     */
853    higher(val: T): T | undefined {
854        let currentNode = this.tree.root;
855        let higherNode = null;
856      
857        while (currentNode) {
858            if (this.compare(val, currentNode.data) < 0) {
859                higherNode = currentNode;
860                currentNode = currentNode.left;
861            } else {
862                currentNode = currentNode.right;
863            }
864        }
865      
866        return higherNode?.data;
867    }
868
869    /**
870     * Returns the largest value < given value
871     */
872    lower(val: T): T | undefined {
873        let currentNode = this.tree.root;
874        let lowerNode = null;
875      
876        while (currentNode) {
877            if (this.compare(currentNode.data, val) < 0) {
878                lowerNode = currentNode;
879                currentNode = currentNode.right;
880            } else {
881                currentNode = currentNode.left;
882            }
883        }
884      
885        return lowerNode?.data;
886    }
887
888    /**
889     * Returns the minimum element in the multiset
890     */
891    first(): T | undefined {
892        return this.tree.inOrder().next().value;
893    }
894
895    /**
896     * Returns the maximum element in the multiset
897     */
898    last(): T | undefined {
899        return this.tree.reverseInOrder().next().value;
900    }
901
902    /**
903     * Removes and returns one occurrence of the minimum element
904     */
905    shift(): T | undefined {
906        const firstElement = this.first();
907        if (firstElement === undefined) return undefined;
908      
909        this.delete(firstElement);
910        return firstElement;
911    }
912
913    /**
914     * Removes and returns one occurrence of the maximum element
915     */
916    pop(): T | undefined {
917        const lastElement = this.last();
918        if (lastElement === undefined) return undefined;
919      
920        this.delete(lastElement);
921        return lastElement;
922    }
923
924    /**
925     * Iterator for the multiset
926     */
927    *[Symbol.iterator](): Generator<T, void, void> {
928        yield* this.values();
929    }
930
931    /**
932     * Generator for keys (includes duplicates)
933     */
934    *keys(): Generator<T, void, void> {
935        yield* this.values();
936    }
937
938    /**
939     * Generator for values in ascending order (includes all duplicates)
940     */
941    *values(): Generator<T, undefined, void> {
942        for (const val of this.tree.inOrder()) {
943            let occurrences = this.count(val);
944            while (occurrences--) {
945                yield val;
946            }
947        }
948        return undefined;
949    }
950
951    /**
952     * Generator for values in descending order (includes all duplicates)
953     */
954    *rvalues(): Generator<T, undefined, void> {
955        for (const val of this.tree.reverseInOrder()) {
956            let occurrences = this.count(val);
957            while (occurrences--) {
958                yield val;
959            }
960        }
961        return undefined;
962    }
963}
964

Time and Space Complexity

Time Complexity: O(n × log n)

The algorithm uses BFS to traverse through positions. In the worst case, we visit each of the n positions exactly once. For each position visited:

We perform two bisect_left operations on the SortedSet, each taking O(log n) time
The while loop iterates through valid positions in the range [mi, mx]. Each position is processed exactly once throughout the entire algorithm (added to queue once, removed from SortedSet once)
Each removal operation from SortedSet takes O(log n) time

Since each of the n positions is processed at most once with O(log n) operations (bisect_left and remove from SortedSet), the overall time complexity is O(n × log n).

Space Complexity: O(n)

The space usage includes:

ans array of size n: O(n)
Two SortedSets storing positions, with total elements up to n + 2 (including sentinel values): O(n)
BFS queue storing at most n elements: O(n)
banned list (input parameter, not counted in auxiliary space)

The total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Range Calculation for Reachable Positions

One of the most common mistakes is incorrectly calculating the range of positions reachable from the current position. The formulas for min_reachable and max_reachable are complex because they need to handle edge cases where the subarray extends beyond array boundaries.

Pitfall Example:

# WRONG: Naive approach without considering edge constraints
min_reachable = current_pos - k + 1
max_reachable = current_pos + k - 1

Why it's wrong: When the subarray would extend beyond array boundaries (left of 0 or right of n-1), the actual position after reversal follows a different pattern due to reflection.

Correct Solution:

# Account for edge reflections
min_reachable = max(current_pos - k + 1, k - current_pos - 1)
max_reachable = min(current_pos + k - 1, n * 2 - k - current_pos - 1)

2. Forgetting to Handle Parity Constraints

Another critical pitfall is not recognizing that reversing a subarray only allows movement between positions of opposite parity. From an even position, you can only reach odd positions in one move, and vice versa.

Pitfall Example:

# WRONG: Checking all positions in range
for next_pos in range(min_reachable, max_reachable + 1):
    if next_pos not in banned:
        # Process next_pos

Correct Solution:

# Only check positions with correct parity (opposite of current)
target_set = unvisited_positions[min_reachable % 2]
# Process only positions in target_set (same parity as min_reachable)

3. Inefficient Visited Tracking Leading to TLE

Using a simple visited array or set without optimization can lead to Time Limit Exceeded for large inputs, especially when repeatedly checking which positions in a range haven't been visited yet.

Pitfall Example:

# WRONG: Inefficient linear scan for each position
visited = set([p])
for next_pos in range(min_reachable, max_reachable + 1, 2):
    if next_pos not in visited and next_pos not in banned:
        visited.add(next_pos)
        queue.append(next_pos)

Correct Solution: Using sorted sets with binary search for efficient range queries:

# Use SortedSet for O(log n) operations
idx = target_set.bisect_left(min_reachable)
while target_set[idx] <= max_reachable:
    next_pos = target_set[idx]
    target_set.remove(next_pos)  # O(log n) removal
    # Process next_pos

4. Not Adding Sentinel Values to Prevent Index Out of Bounds

When using binary search on sorted sets, forgetting to add sentinel values can cause index out of bounds errors when all valid positions have been visited.

Pitfall Example:

# WRONG: No sentinel, may crash when set becomes empty in range
while idx < len(target_set) and target_set[idx] <= max_reachable:
    # Process

Correct Solution:

# Add sentinel value larger than any valid position
unvisited_positions[0].add(n)
unvisited_positions[1].add(n)
# Now target_set[idx] is always valid, will be n when no more positions

5. Initializing Banned Positions Incorrectly

A subtle pitfall is not properly handling the banned positions during initialization, especially when the starting position itself might be in the banned list (though typically problem constraints prevent this).

Pitfall Example:

# WRONG: Removing from wrong parity set
for banned_pos in banned:
    unvisited_positions[0].discard(banned_pos)  # Always removing from even set

Correct Solution:

# Remove from the correct parity set
for banned_pos in banned:
    unvisited_positions[banned_pos % 2].discard(banned_pos)
    # Or use remove() if you're certain the position exists

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know

2612. Minimum Reverse Operations

Problem Description

Flowchart Walkthrough

Intuition

Solution Approach

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Example Walkthrough

Solution Implementation

Time and Space Complexity

Common Pitfalls

1. Incorrect Range Calculation for Reachable Positions

2. Forgetting to Handle Parity Constraints

3. Inefficient Visited Tracking Leading to TLE

4. Not Adding Sentinel Values to Prevent Index Out of Bounds

5. Initializing Banned Positions Incorrectly

Recommended Readings