2612. Minimum Reverse Operations - Solution

Q: Is Minimum Reverse Operations easy or hard?

Minimum Reverse Operations is classified as a Hard problem with a low acceptance rate around 16%. The difficulty comes from deriving the index transformation after reversal and optimizing neighbor discovery so the BFS does not scan every possible subarray.

Q: Minimum Reverse Operations Python/Java solution

Python implementations commonly use BFS with sorted containers or bisect-based structures, while Java solutions often rely on TreeSet for ordered index retrieval. Both follow the same idea: compute the reachable index range, query the ordered set for candidates, and push them into the BFS queue with distance +1.

Q: How to solve Minimum Reverse Operations in O(n)?

A near-linear solution comes from modeling the problem as BFS and deriving the range of indices reachable after reversing a window containing the current position. By grouping indices by parity and removing them from ordered sets once visited, you avoid revisiting states and keep the total operations close to linear, typically implemented as O(n log n).

Q: What is the best approach for Minimum Reverse Operations?

The most efficient approach uses Breadth-First Search combined with ordered sets. BFS guarantees minimum operations, while ordered sets allow you to quickly retrieve unvisited indices within the reachable range created by reversing a k-length subarray. By separating indices into even and odd sets, you avoid scanning the entire array and achieve about O(n log n) time complexity.

Q: Is Minimum Reverse Operations asked at Google/Amazon/Meta?

Hard BFS and graph-transformation problems like this frequently appear in interviews at companies such as Google, Meta, and Amazon. The problem tests graph modeling, mathematical reasoning about array reversals, and efficient data structures like ordered sets or balanced trees.

Q: What data structure is used in Minimum Reverse Operations?

The optimal solution uses a queue for BFS and ordered sets (often implemented with TreeSet, SortedSet, or balanced BST structures). Two sets are typically maintained for even and odd indices to efficiently fetch valid unvisited positions within a computed range.

Q: What is the time complexity of Minimum Reverse Operations?

The optimized solution runs in O(n log n) time and O(n) space. Each index is inserted and removed from an ordered set at most once, and BFS processes each node a single time. Range queries on the ordered set add the logarithmic factor.

The 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 i^th 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 <= 10⁵
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

Approach overview

Problem Overview: You start at position p in an array of length n. In one move, you can reverse any subarray of length k. Some indices are banned and cannot be visited. The task is to compute the minimum number of reverse operations needed to reach every index, or -1 if it is impossible.

Approach 1: Breadth-First Search with Ordered Set (O(n log n) time, O(n) space)

The state space is the index of the position after each reversal. Treat each index as a node in a graph and run Breadth-First Search from the starting position p. The challenge is efficiently finding all indices reachable by reversing a length-k subarray containing the current index. Reversing maps index i to l + r - i where [l, r] is the chosen window.

Instead of checking every possible window, compute the valid range of reachable indices mathematically. All reachable targets form a sequence with alternating parity. Maintain two ordered sets (even and odd indices) containing unvisited and non-banned positions. During BFS, query the ordered set for indices within the valid range and remove them once visited. This pruning prevents repeated scanning and keeps transitions efficient.

Each index is processed once and removed from the set once, while range queries cost O(log n). BFS guarantees the first time you visit an index is the minimum number of operations. This approach scales well even when n is large because it avoids enumerating all possible reversals explicitly.

Approach 2: Dynamic Programming Simulation (O(n * k) time, O(n) space)

A more direct strategy simulates transitions by evaluating all length-k subarrays that include the current index. For each valid window [l, r], compute the resulting index after reversal and update the minimum number of operations using dynamic programming or BFS-style relaxation. The DP array stores the best known move count for every position.

This approach is easier to reason about because it mirrors the problem statement: iterate over possible windows and apply the reversal mapping. However, each index may examine up to k candidate windows, which leads to O(n * k) time in the worst case. With large constraints, this becomes too slow compared to the ordered-set BFS optimization.

Recommended for interviews: The BFS with ordered sets is the expected solution. Interviewers want to see that you model the problem as a graph traversal, derive the reversal index formula, and optimize neighbor discovery using parity grouping and ordered sets. A brute-force or simulation approach demonstrates understanding of the mechanics, but the optimized BFS shows strong algorithmic reasoning with array transformations and efficient range queries.

Approach 1: Approach 1: Breadth-First Search (BFS)

Using BFS, you can explore the minimum operations needed from the given starting position to every other position, treating the movement as edges in a graph. Each valid reverse operation represents an edge. The BFS will help compute the shortest path (minimum operations) to reach each position with '1'.

Python

from collections import deque

def min_reverse_operations(n, p, banned, k):
    result = [-1] * n
    result[p] = 0
    banned_set = set(banned)
    queue = deque([p])

    while queue:
        current = queue.popleft()

        if current + k - 1 < n and (current + k - 1) not in banned_set and result[current + k - 1] == -1:
            result[current + k - 1] = result[current] + 1
            queue.append(current + k - 1)

        if current - k + 1 >= 0 and (current - k + 1) not in banned_set and result[current - k + 1] == -1:
            result[current - k + 1] = result[current] + 1
            queue.append(current - k + 1)

    return result

Java

import java.util.*;

public int[] minReverseOperations(int n, int p, int[] banned, int k) {
    int[] result = new int[n];
    Arrays.fill(result, -1);
    result[p] = 0;
    Set<Integer> bannedSet = new HashSet<>();
    for (int b : banned) {
        bannedSet.add(b);
    }

    Queue<Integer> queue = new LinkedList<>();
    queue.offer(p);

    while (!queue.isEmpty()) {
        int current = queue.poll();

        if ((current + k - 1) < n && !bannedSet.contains(current + k - 1) && result[current + k - 1] == -1) {
            result[current + k - 1] = result[current] + 1;
            queue.offer(current + k - 1);
        }

        if ((current - k + 1) >= 0 && !bannedSet.contains(current - k + 1) && result[current - k + 1] == -1) {
            result[current - k + 1] = result[current] + 1;
            queue.offer(current - k + 1);
        }
    }

    return result;
}

C++

#include <vector>
#include <queue>
using namespace std;

vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
    vector<int> result(n, -1);
    result[p] = 0;
    vector<bool> isBanned(n, false);
    for (int b : banned) {
        isBanned[b] = true;
    }

    queue<int> q;
    q.push(p);

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        if ((current + k - 1) < n && !isBanned[current + k - 1] && result[current + k - 1] == -1) {
            result[current + k - 1] = result[current] + 1;
            q.push(current + k - 1);
        }

        if ((current - k + 1) >= 0 && !isBanned[current - k + 1] && result[current - k + 1] == -1) {
            result[current - k + 1] = result[current] + 1;
            q.push(current - k + 1);
        }
    }

    return result;
}

JavaScript

function minReverseOperations(n, p, banned, k) {
    const result = Array(n).fill(-1);
    result[p] = 0;
    const bannedSet = new Set(banned);
    const queue = [p];

    while (queue.length > 0) {
        const current = queue.shift();

        if (current + k - 1 < n && !bannedSet.has(current + k - 1) && result[current + k - 1] === -1) {
            result[current + k - 1] = result[current] + 1;
            queue.push(current + k - 1);
        }

        if (current - k + 1 >= 0 && !bannedSet.has(current - k + 1) && result[current - k + 1] === -1) {
            result[current - k + 1] = result[current] + 1;
            queue.push(current - k + 1);
        }
    }

    return result;
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int* minReverseOperations(int n, int p, int* banned, int bannedSize, int k, int* returnSize) {
    int* result = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        result[i] = -1;
    }
    result[p] = 0;
    bool* visited = (bool*)calloc(n, sizeof(bool));
    bool* isBanned = (bool*)calloc(n, sizeof(bool));
    for (int i = 0; i < bannedSize; i++) {
        isBanned[banned[i]] = true;
    }

    int* queue = (int*)malloc(n * sizeof(int));
    int front = 0, rear = 0;
    queue[rear++] = p;

    while (front < rear) {
        int current = queue[front++];

        if ((current + k - 1) < n && !isBanned[current + k - 1] && !visited[current + k - 1]) {
            result[current + k - 1] = result[current] + 1;
            queue[rear++] = current + k - 1;
            visited[current + k - 1] = true;
        }

        if ((current - k + 1) >= 0 && !isBanned[current - k + 1] && !visited[current - k + 1]) {
            result[current - k + 1] = result[current] + 1;
            queue[rear++] = current - k + 1;
            visited[current - k + 1] = true;
        }
    }

    *returnSize = n;
    free(visited);
    free(isBanned);
    free(queue);
    return result;
}

using System;
using System.Collections.Generic;

public class Solution {
    public int[] MinReverseOperations(int n, int p, int[] banned, int k) {
        int[] result = new int[n];
        Array.Fill(result, -1);
        result[p] = 0;
        HashSet<int> bannedSet = new HashSet<int>(banned);

        Queue<int> queue = new Queue<int>();
        queue.Enqueue(p);

        while (queue.Count > 0) {
            int current = queue.Dequeue();

            if (current + k - 1 < n && !bannedSet.Contains(current + k - 1) && result[current + k - 1] == -1) {
                result[current + k - 1] = result[current] + 1;
                queue.Enqueue(current + k - 1);
            }

            if (current - k + 1 >= 0 && !bannedSet.Contains(current - k + 1) && result[current - k + 1] == -1) {
                result[current - k + 1] = result[current] + 1;
                queue.Enqueue(current - k + 1);
            }
        }

        return result;
    }
}

The Python solution uses the collections.deque as a queue and a set to efficiently handle banned positions. This enhances the lookup speed during BFS checks, ensuring efficient position reversal handling.

Complexity

Time Complexity: O(n), as each position is visited once during BFS execution.
Space Complexity: O(n), predominantly for the queue and banned set storage.

Try this approach in the editor

Approach 2: Approach 2: Dynamic Programming

Using Dynamic Programming (DP), build solutions incrementally by exploring possible reversals prior to marked positions. Although slightly more cumbersome with edge checking, this approach can yield insights or optimizations for specific arrangements, especially with smaller k ranges or less complex banned specifications.

Python

def min_reverse_operations_dp(n, p, banned, k):
    result = [-1] * n
    result[p] = 0
    banned_set = set(banned)

    for i in range(n):
        if i not in banned_set and result[i] == -1:
            for j in range(max(i - k + 1, 0), min(i + k, n)):
                if result[j] != -1:
                    result[i] = 1 + result[j] if result[i] == -1 else min(result[i], 1 + result[j])

    return result

JavaScript

function minReverseOperationsDP(n, p, banned, k) {
    const result = Array(n).fill(-1);
    result[p] = 0;
    const bannedSet = new Set(banned);

    for (let i = 0; i < n; i++) {
        if (!bannedSet.has(i) && result[i] === -1) {
            for (let j = Math.max(i - k + 1, 0); j < Math.min(i + k, n); j++) {
                if (result[j] !== -1) {
                    result[i] = result[i] === -1 ? 1 + result[j] : Math.min(result[i], 1 + result[j]);
                }
            }
        }
    }

    return result;
}

The Python DP solution attempts to calculate each position's minimum operations by iteratively considering all options of reversed subarrays that might end at a particular unvisited index. The sub-increments build each position's operations count based on known previous transformations.

Complexity

Time Complexity: O(n * k), within nested iteration.
Space Complexity: O(n), primarily for storing DP results.

Try this approach in the editor

Approach 3: Ordered Set + BFS

We notice that for any index i in the subarray interval [l,..r], the flipped index j = l + r - i.

If the subarray moves one position to the right, then j = l + 1 + r + 1 - i = l + r - i + 2, that is, j will increase by 2.

Similarly, if the subarray moves one position to the left, then j = l - 1 + r - 1 - i = l + r - i - 2, that is, j will decrease by 2.

Therefore, for a specific index i, all its flipped indices form an arithmetic progression with common difference 2, that is, all the flipped indices have the same parity.

Next, we consider the range of values of the index i after flipping j.

If the boundary is not considered, the range of values of j is [i - k + 1, i + k - 1].
If the subarray is on the left, then [l, r] = [0, k - 1], so the flipped index j of i is 0 + k - 1 - i, that is, j = k - i - 1, so the left boundary mi = max(i - k + 1, k - i - 1).
If the subarray is on the right, then [l, r] = [n - k, n - 1], so the flipped index j= n - k + n - 1 - i is j = n times 2 - k - i - 1, so the right boundary of j is mx = min(i + k - 1, n times 2 - k - i - 1).

We use two ordered sets to store all the odd indices and even indices to be searched, here we need to exclude the indices in the array banned and the index p.

Then we use BFS to search, each time searching all the flipped indices j of the current index i, that is, j = mi, mi + 2, mi + 4, \dots, mx, updating the answer of index j and adding index j to the search queue, and removing index j from the corresponding ordered set.

When the search is over, the answer to all indices can be obtained.

The time complexity is O(n times log n) and the space complexity is O(n). Where n is the given array length in the problem.

TypeScript

function minReverseOperations(n: number, p: number, banned: number[], k: number): number[] {
    const ans: number[] = Array(n).fill(-1);
    const ts = [new TreeSet<number>(), new TreeSet<number>()];
    for (let i = 0; i < n; ++i) {
        ts[i % 2].add(i);
    }
    ans[p] = 0;
    ts[p % 2].delete(p);
    for (const i of banned) {
        ts[i % 2].delete(i);
    }
    ts[0].add(n);
    ts[1].add(n);
    let q = [p];
    while (q.length) {
        const t: number[] = [];
        for (const i of q) {
            const mi = Math.max(i - k + 1, k - i - 1);
            const mx = Math.min(i + k - 1, n * 2 - k - i - 1);
            const s = ts[mi % 2];
            for (let j = s.ceil(mi)!; j <= mx; j = s.ceil(j)!) {
                t.push(j);
                ans[j] = ans[i] + 1;
                s.delete(j);
            }
        }
        q = t;
    }
    return ans;
}

type Compare<T> = (lhs: T, rhs: T) => number;

class RBTreeNode<T = number> {
    data: T;
    count: number;
    left: RBTreeNode<T> | null;
    right: RBTreeNode<T> | null;
    parent: RBTreeNode<T> | null;
    color: number;
    constructor(data: T) {
        this.data = data;
        this.left = this.right = this.parent = null;
        this.color = 0;
        this.count = 1;
    }

    sibling(): RBTreeNode<T> | null {
        if (!this.parent) return null; // sibling null if no parent
        return this.isOnLeft() ? this.parent.right : this.parent.left;
    }

    isOnLeft(): boolean {
        return this === this.parent!.left;
    }

    hasRedChild(): boolean {
        return (
            Boolean(this.left && this.left.color === 0) ||
            Boolean(this.right && this.right.color === 0)
        );
    }
}

class RBTree<T> {
    root: RBTreeNode<T> | null;
    lt: (l: T, r: T) => boolean;
    constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
        this.root = null;
        this.lt = (l: T, r: T) => compare(l, r) < 0;
    }

    rotateLeft(pt: RBTreeNode<T>): void {
        const right = pt.right!;
        pt.right = right.left;

        if (pt.right) pt.right.parent = pt;
        right.parent = pt.parent;

        if (!pt.parent) this.root = right;
        else if (pt === pt.parent.left) pt.parent.left = right;
        else pt.parent.right = right;

        right.left = pt;
        pt.parent = right;
    }

    rotateRight(pt: RBTreeNode<T>): void {
        const left = pt.left!;
        pt.left = left.right;

        if (pt.left) pt.left.parent = pt;
        left.parent = pt.parent;

        if (!pt.parent) this.root = left;
        else if (pt === pt.parent.left) pt.parent.left = left;
        else pt.parent.right = left;

        left.right = pt;
        pt.parent = left;
    }

    swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.color;
        p1.color = p2.color;
        p2.color = tmp;
    }

    swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
        const tmp = p1.data;
        p1.data = p2.data;
        p2.data = tmp;
    }

    fixAfterInsert(pt: RBTreeNode<T>): void {
        let parent = null;
        let grandParent = null;

        while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
            parent = pt.parent;
            grandParent = pt.parent.parent;

            /*  Case : A
                Parent of pt is left child of Grand-parent of pt */
            if (parent === grandParent?.left) {
                const uncle = grandParent.right;

                /* Case : 1
                   The uncle of pt is also red
                   Only Recoloring required */
                if (uncle && uncle.color === 0) {
                    grandParent.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent;
                } else {
                    /* Case : 2
                       pt is right child of its parent
                       Left-rotation required */
                    if (pt === parent.right) {
                        this.rotateLeft(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is left child of its parent
                       Right-rotation required */
                    this.rotateRight(grandParent);
                    this.swapColor(parent!, grandParent);
                    pt = parent!;
                }
            } else {
                /* Case : B
               Parent of pt is right child of Grand-parent of pt */
                const uncle = grandParent!.left;

                /*  Case : 1
                    The uncle of pt is also red
                    Only Recoloring required */
                if (uncle != null && uncle.color === 0) {
                    grandParent!.color = 0;
                    parent.color = 1;
                    uncle.color = 1;
                    pt = grandParent!;
                } else {
                    /* Case : 2
                       pt is left child of its parent
                       Right-rotation required */
                    if (pt === parent.left) {
                        this.rotateRight(parent);
                        pt = parent;
                        parent = pt.parent;
                    }

                    /* Case : 3
                       pt is right child of its parent
                       Left-rotation required */
                    this.rotateLeft(grandParent!);
                    this.swapColor(parent!, grandParent!);
                    pt = parent!;
                }
            }
        }
        this.root!.color = 1;
    }

    delete(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        node.count--;
        if (!node.count) this.deleteNode(node);
        return true;
    }

    deleteAll(val: T): boolean {
        const node = this.find(val);
        if (!node) return false;
        this.deleteNode(node);
        return true;
    }

    deleteNode(v: RBTreeNode<T>): void {
        const u = BSTreplace(v);

        // True when u and v are both black
        const uvBlack = (u === null || u.color === 1) && v.color === 1;
        const parent = v.parent!;

        if (!u) {
            // u is null therefore v is leaf
            if (v === this.root) this.root = null;
            // v is root, making root null
            else {
                if (uvBlack) {
                    // u and v both black
                    // v is leaf, fix double black at v
                    this.fixDoubleBlack(v);
                } else {
                    // u or v is red
                    if (v.sibling()) {
                        // sibling is not null, make it red"
                        v.sibling()!.color = 0;
                    }
                }
                // delete v from the tree
                if (v.isOnLeft()) parent.left = null;
                else parent.right = null;
            }
            return;
        }

        if (!v.left || !v.right) {
            // v has 1 child
            if (v === this.root) {
                // v is root, assign the value of u to v, and delete u
                v.data = u.data;
                v.left = v.right = null;
            } else {
                // Detach v from tree and move u up
                if (v.isOnLeft()) parent.left = u;
                else parent.right = u;
                u.parent = parent;
                if (uvBlack) this.fixDoubleBlack(u);
                // u and v both black, fix double black at u
                else u.color = 1; // u or v red, color u black
            }
            return;
        }

        // v has 2 children, swap data with successor and recurse
        this.swapData(u, v);
        this.deleteNode(u);

        // find node that replaces a deleted node in BST
        function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
            // when node have 2 children
            if (x.left && x.right) return successor(x.right);
            // when leaf
            if (!x.left && !x.right) return null;
            // when single child
            return x.left ?? x.right;
        }
        // find node that do not have a left child
        // in the subtree of the given node
        function successor(x: RBTreeNode<T>): RBTreeNode<T> {
            let temp = x;
            while (temp.left) temp = temp.left;
            return temp;
        }
    }

    fixDoubleBlack(x: RBTreeNode<T>): void {
        if (x === this.root) return; // Reached root

        const sibling = x.sibling();
        const parent = x.parent!;
        if (!sibling) {
            // No sibiling, double black pushed up
            this.fixDoubleBlack(parent);
        } else {
            if (sibling.color === 0) {
                // Sibling red
                parent.color = 0;
                sibling.color = 1;
                if (sibling.isOnLeft()) this.rotateRight(parent);
                // left case
                else this.rotateLeft(parent); // right case
                this.fixDoubleBlack(x);
            } else {
                // Sibling black
                if (sibling.hasRedChild()) {
                    // at least 1 red children
                    if (sibling.left && sibling.left.color === 0) {
                        if (sibling.isOnLeft()) {
                            // left left
                            sibling.left.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateRight(parent);
                        } else {
                            // right left
                            sibling.left.color = parent.color;
                            this.rotateRight(sibling);
                            this.rotateLeft(parent);
                        }
                    } else {
                        if (sibling.isOnLeft()) {
                            // left right
                            sibling.right!.color = parent.color;
                            this.rotateLeft(sibling);
                            this.rotateRight(parent);
                        } else {
                            // right right
                            sibling.right!.color = sibling.color;
                            sibling.color = parent.color;
                            this.rotateLeft(parent);
                        }
                    }
                    parent.color = 1;
                } else {
                    // 2 black children
                    sibling.color = 0;
                    if (parent.color === 1) this.fixDoubleBlack(parent);
                    else parent.color = 1;
                }
            }
        }
    }

    insert(data: T): boolean {
        // search for a position to insert
        let parent = this.root;
        while (parent) {
            if (this.lt(data, parent.data)) {
                if (!parent.left) break;
                else parent = parent.left;
            } else if (this.lt(parent.data, data)) {
                if (!parent.right) break;
                else parent = parent.right;
            } else break;
        }

        // insert node into parent
        const node = new RBTreeNode(data);
        if (!parent) this.root = node;
        else if (this.lt(node.data, parent.data)) parent.left = node;
        else if (this.lt(parent.data, node.data)) parent.right = node;
        else {
            parent.count++;
            return false;
        }
        node.parent = parent;
        this.fixAfterInsert(node);
        return true;
    }

    find(data: T): RBTreeNode<T> | null {
        let p = this.root;
        while (p) {
            if (this.lt(data, p.data)) {
                p = p.left;
            } else if (this.lt(p.data, data)) {
                p = p.right;
            } else break;
        }
        return p ?? null;
    }

    *inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.inOrder(root.left!)) yield v;
        yield root.data;
        for (const v of this.inOrder(root.right!)) yield v;
    }

    *reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
        if (!root) return;
        for (const v of this.reverseInOrder(root.right!)) yield v;
        yield root.data;
        for (const v of this.reverseInOrder(root.left!)) yield v;
    }
}

class TreeSet<T = number> {
    _size: number;
    tree: RBTree<T>;
    compare: Compare<T>;
    constructor(
        collection: T[] | Compare<T> = [],
        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
    ) {
        if (typeof collection === 'function') {
            compare = collection;
            collection = [];
        }
        this._size = 0;
        this.compare = compare;
        this.tree = new RBTree(compare);
        for (const val of collection) this.add(val);
    }

    size(): number {
        return this._size;
    }

    has(val: T): boolean {
        return !!this.tree.find(val);
    }

    add(val: T): boolean {
        const successful = this.tree.insert(val);
        this._size += successful ? 1 : 0;
        return successful;
    }

    delete(val: T): boolean {
        const deleted = this.tree.deleteAll(val);
        this._size -= deleted ? 1 : 0;
        return deleted;
    }

    ceil(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(p.data, val) >= 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    floor(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(val, p.data) >= 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    higher(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(val, p.data) < 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    lower(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(p.data, val) < 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    first(): T | undefined {
        return this.tree.inOrder().next().value;
    }

    last(): T | undefined {
        return this.tree.reverseInOrder().next().value;
    }

    shift(): T | undefined {
        const first = this.first();
        if (first === undefined) return undefined;
        this.delete(first);
        return first;
    }

    pop(): T | undefined {
        const last = this.last();
        if (last === undefined) return undefined;
        this.delete(last);
        return last;
    }

    *[Symbol.iterator](): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *keys(): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *values(): Generator<T, undefined, void> {
        for (const val of this.tree.inOrder()) yield val;
        return undefined;
    }

    /**
     * Return a generator for reverse order traversing the set
     */
    *rvalues(): Generator<T, undefined, void> {
        for (const val of this.tree.reverseInOrder()) yield val;
        return undefined;
    }
}

class TreeMultiSet<T = number> {
    _size: number;
    tree: RBTree<T>;
    compare: Compare<T>;
    constructor(
        collection: T[] | Compare<T> = [],
        compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
    ) {
        if (typeof collection === 'function') {
            compare = collection;
            collection = [];
        }
        this._size = 0;
        this.compare = compare;
        this.tree = new RBTree(compare);
        for (const val of collection) this.add(val);
    }

    size(): number {
        return this._size;
    }

    has(val: T): boolean {
        return !!this.tree.find(val);
    }

    add(val: T): boolean {
        const successful = this.tree.insert(val);
        this._size++;
        return successful;
    }

    delete(val: T): boolean {
        const successful = this.tree.delete(val);
        if (!successful) return false;
        this._size--;
        return true;
    }

    count(val: T): number {
        const node = this.tree.find(val);
        return node ? node.count : 0;
    }

    ceil(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(p.data, val) >= 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    floor(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(val, p.data) >= 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    higher(val: T): T | undefined {
        let p = this.tree.root;
        let higher = null;
        while (p) {
            if (this.compare(val, p.data) < 0) {
                higher = p;
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return higher?.data;
    }

    lower(val: T): T | undefined {
        let p = this.tree.root;
        let lower = null;
        while (p) {
            if (this.compare(p.data, val) < 0) {
                lower = p;
                p = p.right;
            } else {
                p = p.left;
            }
        }
        return lower?.data;
    }

    first(): T | undefined {
        return this.tree.inOrder().next().value;
    }

    last(): T | undefined {
        return this.tree.reverseInOrder().next().value;
    }

    shift(): T | undefined {
        const first = this.first();
        if (first === undefined) return undefined;
        this.delete(first);
        return first;
    }

    pop(): T | undefined {
        const last = this.last();
        if (last === undefined) return undefined;
        this.delete(last);
        return last;
    }

    *[Symbol.iterator](): Generator<T, void, void> {
        yield* this.values();
    }

    *keys(): Generator<T, void, void> {
        for (const val of this.values()) yield val;
    }

    *values(): Generator<T, undefined, void> {
        for (const val of this.tree.inOrder()) {
            let count = this.count(val);
            while (count--) yield val;
        }
        return undefined;
    }

    /**
     * Return a generator for reverse order traversing the multi-set
     */
    *rvalues(): Generator<T, undefined, void> {
        for (const val of this.tree.reverseInOrder()) {
            let count = this.count(val);
            while (count--) yield val;
        }
        return undefined;
    }
}

func minReverseOperations(n int, p int, banned []int, k int) []int {
	ans := make([]int, n)
	ts := [2]*redblacktree.Tree{redblacktree.NewWithIntComparator(), redblacktree.NewWithIntComparator()}
	for i := 0; i < n; i++ {
		ts[i%2].Put(i, struct{}{})
		ans[i] = -1
	}
	ans[p] = 0
	ts[p%2].Remove(p)
	for _, i := range banned {
		ts[i%2].Remove(i)
	}
	ts[0].Put(n, struct{}{})
	ts[1].Put(n, struct{}{})
	q := []int{p}
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		mi := max(i-k+1, k-i-1)
		mx := min(i+k-1, n*2-k-i-1)
		s := ts[mi%2]
		for x, _ := s.Ceiling(mi); x.Key.(int) <= mx; x, _ = s.Ceiling(mi) {
			j := x.Key.(int)
			s.Remove(j)
			ans[j] = ans[i] + 1
			q = append(q, j)
		}
	}
	return ans
}

Rust

use std::collections::{BTreeSet, VecDeque};

impl Solution {
    pub fn min_reverse_operations(n: i32, p: i32, banned: Vec<i32>, k: i32) -> Vec<i32> {
        let mut ans = vec![-1; n as usize];
        let mut ts = [BTreeSet::new(), BTreeSet::new()];

        for i in 0..n {
            ts[(i % 2) as usize].insert(i);
        }
        ans[p as usize] = 0;
        ts[(p % 2) as usize].remove(&p);

        for &b in &banned {
            ts[(b % 2) as usize].remove(&b);
        }

        ts[0].insert(n);
        ts[1].insert(n);
        let mut q = VecDeque::new();
        q.push_back(p);

        while let Some(i) = q.pop_front() {
            let mi = (i - k + 1).max(k - i - 1);
            let mx = (i + k - 1).min(2 * n - k - i - 1);
            let s = &mut ts[(mi % 2) as usize];

            while let Some(&j) = s.range(mi..=mx).next() {
                q.push_back(j);
                ans[j as usize] = ans[i as usize] + 1;
                s.remove(&j);
            }
        }

        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Breadth-First Search (BFS)	Time Complexity: `O(n)`, as each position is visited once during BFS execution. Space Complexity: `O(n)`, predominantly for the queue and banned set storage.
Approach 2: Dynamic Programming	Time Complexity: `O(n * k)`, within nested iteration. Space Complexity: `O(n)`, primarily for storing DP results.
Ordered Set + BFS	–

Complexity analysis

Approach	Time	Space	When to Use
BFS with Ordered Set	O(n log n)	O(n)	Large constraints where you must efficiently discover reachable indices without scanning all windows
Dynamic Programming Simulation	O(n * k)	O(n)	Conceptual understanding or small input sizes where enumerating reversal windows is acceptable

Frequently asked questions

Is Minimum Reverse Operations easy or hard?

Minimum Reverse Operations is classified as a Hard problem with a low acceptance rate around 16%. The difficulty comes from deriving the index transformation after reversal and optimizing neighbor discovery so the BFS does not scan every possible subarray.

Minimum Reverse Operations Python/Java solution

Python implementations commonly use BFS with sorted containers or bisect-based structures, while Java solutions often rely on TreeSet for ordered index retrieval. Both follow the same idea: compute the reachable index range, query the ordered set for candidates, and push them into the BFS queue with distance +1.

How to solve Minimum Reverse Operations in O(n)?

A near-linear solution comes from modeling the problem as BFS and deriving the range of indices reachable after reversing a window containing the current position. By grouping indices by parity and removing them from ordered sets once visited, you avoid revisiting states and keep the total operations close to linear, typically implemented as O(n log n).

What is the best approach for Minimum Reverse Operations?

The most efficient approach uses Breadth-First Search combined with ordered sets. BFS guarantees minimum operations, while ordered sets allow you to quickly retrieve unvisited indices within the reachable range created by reversing a k-length subarray. By separating indices into even and odd sets, you avoid scanning the entire array and achieve about O(n log n) time complexity.

Is Minimum Reverse Operations asked at Google/Amazon/Meta?

Hard BFS and graph-transformation problems like this frequently appear in interviews at companies such as Google, Meta, and Amazon. The problem tests graph modeling, mathematical reasoning about array reversals, and efficient data structures like ordered sets or balanced trees.

What data structure is used in Minimum Reverse Operations?

The optimal solution uses a queue for BFS and ordered sets (often implemented with TreeSet, SortedSet, or balanced BST structures). Two sets are typically maintained for even and odd indices to efficiently fetch valid unvisited positions within a computed range.

What is the time complexity of Minimum Reverse Operations?

The optimized solution runs in O(n log n) time and O(n) space. Each index is inserted and removed from an ordered set at most once, and BFS processes each node a single time. Range queries on the ordered set add the logarithmic factor.

Minimum Reverse Operations solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Breadth-First Search (BFS)

Approach 2: Approach 2: Dynamic Programming

Approach 3: Ordered Set + BFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Reverse Operations solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Breadth-First Search (BFS)

Approach 2: Approach 2: Dynamic Programming

Approach 3: Ordered Set + BFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems