Minimum Reverse Operations

Hard
1708.

Minimum Reverse Operations

Minimum Reverse Operations is a hard coding problem on arrays, breadth-first search and union find, asked in Amazon and Google interviews.

An array arr of length n is all zeros except arr[p] = 1. The positions listed in banned are forbidden for the 1 (p itself is never banned).

In one operation you choose a contiguous subarray of length exactly k and reverse it — but only if, afterwards, the 1 does not sit on a banned position.

Return an array ans of length n where ans[i] is the minimum number of operations that bring the 1 to position i, or -1 if that is impossible.

Example 1

Input
n = 4, p = 0, banned = [1,2], k = 4
Output
[0,-1,-1,1]
Explanation
Reversing the whole array moves the 1 from 0 to 3. Positions 1 and 2 are banned.

Example 2

Input
n = 5, p = 0, banned = [2,4], k = 3
Output
[0,-1,-1,-1,-1]
Explanation
From 0 the only length-3 window is [0..2], which would land the 1 on banned 2.

Example 3

Input
n = 4, p = 2, banned = [0,1,3], k = 1
Output
[-1,-1,0,-1]
Explanation
Reversing a single element moves nothing.

Constraints

  • 1 <= n <= 10^5
  • 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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} p
 * @param {number[]} banned
 * @param {number} k
 * @return {number[]}
 */
var minReverseOperations = function(n, p, banned, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Reverse Operations — Solution in Python, Java & C++

Minimum Reverse Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Reverse Operations is a hard coding problem on arrays, breadth-first search and union find, asked in Amazon and Google interviews.

Problem statement

An array arr of length n is all zeros except arr[p] = 1. The positions listed in banned are forbidden for the 1 (p itself is never banned).

In one operation you choose a contiguous subarray of length exactly k and reverse it — but only if, afterwards, the 1 does not sit on a banned position.

Return an array ans of length n where ans[i] is the minimum number of operations that bring the 1 to position i, or -1 if that is impossible.

Example 1

Input: n = 4, p = 0, banned = [1,2], k = 4
Output: [0,-1,-1,1]
Explanation: Reversing the whole array moves the 1 from 0 to 3. Positions 1 and 2 are banned.

Example 2

Input: n = 5, p = 0, banned = [2,4], k = 3
Output: [0,-1,-1,-1,-1]
Explanation: From 0 the only length-3 window is [0..2], which would land the 1 on banned 2.

Example 3

Input: n = 4, p = 2, banned = [0,1,3], k = 1
Output: [-1,-1,0,-1]
Explanation: Reversing a single element moves nothing.

Constraints

  • 1 <= n <= 10^5
  • 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

Hints for Minimum Reverse Operations

  1. Hint 1

    Reversing the window [L, L + k - 1] that contains the 1 at i sends it to 2L + k - 1 - i. Every operation costs 1, so this is a BFS over positions.

  2. Hint 2

    From i the reachable positions form an arithmetic range with step 2: from max(i - k + 1, k - 1 - i) to min(i + k - 1, 2n - k - 1 - i). Trying every window is O(nk) — too slow.

  3. Hint 3

    Each position needs to be discovered only once. Keep the still-unvisited positions of each parity in a structure that jumps straight to the next unvisited one (a sorted set, or a 'next pointer' union-find), and delete positions as you visit them.

How to solve Minimum Reverse Operations

The moves from position i reach every position of one parity inside a contiguous range, and BFS only needs to touch each position the first time it is discovered. A union-find 'next unvisited' pointer per parity lets each BFS step skip straight over positions already visited or banned, so the whole search is near-linear.

Approach

  1. Let nxt[x] = x for every x in 0 .. n + 1; removing x means nxt[x] = x + 2 (the next index of the same parity). n and n + 1 are never removed.
  2. Remove p and every banned position. Set ans[p] = 0 and queue p.
  3. Pop i. Compute lo = max(i - k + 1, k - 1 - i) and hi = min(i + k - 1, 2n - k - 1 - i).
  4. Walk x = find(lo) while x <= hi: set ans[x] = ans[i] + 1, queue it, remove it, then x = find(x + 2).
  5. Positions never reached keep -1.

Why it works

The window start L ranges over max(0, i - k + 1) .. min(n - k, i), and the landing spot 2L + k - 1 - i moves by 2 as L grows, so the reachable set is exactly every second position between lo and hi. BFS order gives each position its minimum number of operations, and removing a position the moment it is reached (or from the start, if banned) means find never returns it again.

Complexity

  • Time — O(n α(n))
  • Space — O(n)

Pitfalls

  • Both ends of the range are clipped by the array edges, which is where k - 1 - i and 2n - k - 1 - i come from.
  • Banned positions must never be entered, but they do not block reaching positions beyond them.
  • Keep two sentinels (n and n + 1) so find always stops inside the array of pointers.

Reference solution

Python

from typing import List
from collections import deque

def minReverseOperations(n: int, p: int, banned: List[int], k: int) -> List[int]:
    nxt = list(range(n + 2))

    def find(x):
        root = x
        while nxt[root] != root:
            root = nxt[root]
        while nxt[x] != root:
            nxt[x], x = root, nxt[x]
        return root

    def remove(x):
        nxt[x] = x + 2

    ans = [-1] * n
    ans[p] = 0
    remove(p)
    for b in banned:
        remove(b)
    q = deque([p])
    while q:
        i = q.popleft()
        lo = max(i - k + 1, k - 1 - i)
        hi = min(i + k - 1, 2 * n - k - 1 - i)
        x = find(lo)
        while x <= hi:
            ans[x] = ans[i] + 1
            q.append(x)
            remove(x)
            x = find(x + 2)
    return ans

Java

static int[] nxtPtr;

static int findNext(int x) {
    int root = x;
    while (nxtPtr[root] != root) root = nxtPtr[root];
    while (nxtPtr[x] != root) { int t = nxtPtr[x]; nxtPtr[x] = root; x = t; }
    return root;
}

public static int[] minReverseOperations(int n, int p, int[] banned, int k) {
    nxtPtr = new int[n + 2];
    for (int i = 0; i < n + 2; i++) nxtPtr[i] = i;
    int[] ans = new int[n];
    Arrays.fill(ans, -1);
    ans[p] = 0;
    nxtPtr[p] = p + 2;
    for (int b : banned) nxtPtr[b] = b + 2;
    int[] q = new int[n];
    int head = 0, tail = 0;
    q[tail++] = p;
    while (head < tail) {
        int cur = q[head++];
        int lo = Math.max(cur - k + 1, k - 1 - cur), hi = Math.min(cur + k - 1, 2 * n - k - 1 - cur);
        for (int x = findNext(lo); x <= hi; x = findNext(x + 2)) {
            ans[x] = ans[cur] + 1;
            q[tail++] = x;
            nxtPtr[x] = x + 2;
        }
    }
    return ans;
}

C++

vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
    vector<int> nxt(n + 2);
    iota(nxt.begin(), nxt.end(), 0);
    auto find = [&](int x) {
        int root = x;
        while (nxt[root] != root) root = nxt[root];
        while (nxt[x] != root) { int t = nxt[x]; nxt[x] = root; x = t; }
        return root;
    };
    vector<int> ans(n, -1);
    ans[p] = 0;
    nxt[p] = p + 2;
    for (int b : banned) nxt[b] = b + 2;
    vector<int> q = {p};
    for (size_t h = 0; h < q.size(); h++) {
        int cur = q[h];
        int lo = max(cur - k + 1, k - 1 - cur), hi = min(cur + k - 1, 2 * n - k - 1 - cur);
        for (int x = find(lo); x <= hi; x = find(x + 2)) {
            ans[x] = ans[cur] + 1;
            q.push_back(x);
            nxt[x] = x + 2;
        }
    }
    return ans;
}

JavaScript

var minReverseOperations = function(n, p, banned, k) {
    var nxt = new Array(n + 2);
    for (var i = 0; i < n + 2; i++) nxt[i] = i;
    var find = function(x) {
        var root = x;
        while (nxt[root] !== root) root = nxt[root];
        while (nxt[x] !== root) { var t = nxt[x]; nxt[x] = root; x = t; }
        return root;
    };
    var ans = new Array(n);
    for (var j = 0; j < n; j++) ans[j] = -1;
    ans[p] = 0;
    nxt[p] = p + 2;
    for (var b = 0; b < banned.length; b++) nxt[banned[b]] = banned[b] + 2;
    var q = [p];
    for (var h = 0; h < q.length; h++) {
        var cur = q[h];
        var lo = Math.max(cur - k + 1, k - 1 - cur), hi = Math.min(cur + k - 1, 2 * n - k - 1 - cur);
        var x = find(lo);
        while (x <= hi) {
            ans[x] = ans[cur] + 1;
            q.push(x);
            nxt[x] = x + 2;
            x = find(x + 2);
        }
    }
    return ans;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Breadth-First Search (BFS)