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.
- Difficulty: Hard
- Topics: Arrays, Breadth-First Search, Union Find, Ordered Set
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^50 <= p <= n - 10 <= banned.length <= n - 10 <= banned[i] <= n - 11 <= k <= nbanned[i] != pall values in banned are unique
Hints for Minimum Reverse Operations
Hint 1
Reversing the window
[L, L + k - 1]that contains the 1 atisends it to2L + k - 1 - i. Every operation costs 1, so this is a BFS over positions.Hint 2
From
ithe reachable positions form an arithmetic range with step 2: frommax(i - k + 1, k - 1 - i)tomin(i + k - 1, 2n - k - 1 - i). Trying every window isO(nk)— too slow.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
- Let
nxt[x] = xfor everyxin0 .. n + 1; removingxmeansnxt[x] = x + 2(the next index of the same parity).nandn + 1are never removed. - Remove
pand every banned position. Setans[p] = 0and queuep. - Pop
i. Computelo = max(i - k + 1, k - 1 - i)andhi = min(i + k - 1, 2n - k - 1 - i). - Walk
x = find(lo)whilex <= hi: setans[x] = ans[i] + 1, queue it, remove it, thenx = find(x + 2). - 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 - iand2n - k - 1 - icome from. - Banned positions must never be entered, but they do not block reaching positions beyond them.
- Keep two sentinels (
nandn + 1) sofindalways 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 ansJava
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)