Minimum Reverse Operations

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 ith result is __ the minimum number of operations needed to bring the single 1 to position i in arr, or -1 if it is impossible.

Examples

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^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

Solution

Method 1 – BFS + Efficient Range Updates

Intuition

Model the problem as a shortest path search: from position p, use BFS to reach all positions, only moving to positions not banned. For each position, compute all possible next positions by reversing a subarray of size k.

Approach

1. Mark banned positions.
2. Use BFS from p, for each position, try all possible reverse operations.
3. For each reachable position, record the minimum number of operations.
4. Use sets or boolean arrays for efficient lookup and marking.

Code

C++

#include <vector>
#include <queue>
#include <unordered_set>
class Solution {
public:
    std::vector<int> minReverseOperations(int n, int p, std::vector<int>& banned, int k) {
        std::vector<int> res(n, -1);
        std::vector<bool> is_banned(n, false);
        for (int b : banned) is_banned[b] = true;
        std::queue<int> q; q.push(p); res[p]=0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            int minL = std::max(u-k+1, 0), maxL = std::min(u, n-k);
            for (int l = minL; l <= maxL; ++l) {
                int v = l+k-1-(u-l);
                if (!is_banned[v] && res[v]==-1) {
                    res[v]=res[u]+1; q.push(v);
                }
            }
        }
        return res;
    }
};

Go

func minReverseOperations(n, p int, banned []int, k int) []int {
    res := make([]int, n)
    for i := range res { res[i] = -1 }
    isBanned := make([]bool, n)
    for _, b := range banned { isBanned[b] = true }
    q := []int{p}; res[p]=0
    for len(q)>0 {
        u := q[0]; q = q[1:]
        minL := u-k+1; if minL<0 { minL=0 }
        maxL := u; if maxL>n-k { maxL=n-k }
        for l := minL; l <= maxL; l++ {
            v := l+k-1-(u-l)
            if !isBanned[v] && res[v]==-1 {
                res[v]=res[u]+1; q = append(q,v)
            }
        }
    }
    return res
}

Java

import java.util.*;
class Solution {
    public int[] minReverseOperations(int n, int p, int[] banned, int k) {
        int[] res = new int[n]; Arrays.fill(res,-1);
        boolean[] isBanned = new boolean[n];
        for (int b : banned) isBanned[b]=true;
        Queue<Integer> q = new LinkedList<>(); q.add(p); res[p]=0;
        while (!q.isEmpty()) {
            int u = q.poll();
            int minL = Math.max(u-k+1,0), maxL = Math.min(u,n-k);
            for (int l = minL; l <= maxL; l++) {
                int v = l+k-1-(u-l);
                if (!isBanned[v] && res[v]==-1) {
                    res[v]=res[u]+1; q.add(v);
                }
            }
        }
        return res;
    }
}

Kotlin

class Solution {
    fun minReverseOperations(n: Int, p: Int, banned: IntArray, k: Int): IntArray {
        val res = IntArray(n){-1}
        val isBanned = BooleanArray(n)
        for (b in banned) isBanned[b]=true
        val q = ArrayDeque<Int>()
        q.add(p); res[p]=0
        while (q.isNotEmpty()) {
            val u = q.removeFirst()
            val minL = maxOf(u-k+1,0); val maxL = minOf(u,n-k)
            for (l in minL..maxL) {
                val v = l+k-1-(u-l)
                if (!isBanned[v] && res[v]==-1) {
                    res[v]=res[u]+1; q.add(v)
                }
            }
        }
        return res
    }
}

Python

from collections import deque
class Solution:
    def minReverseOperations(self, n: int, p: int, banned: list[int], k: int) -> list[int]:
        res = [-1]*n
        is_banned = [False]*n
        for b in banned: is_banned[b]=True
        q = deque([p]); res[p]=0
        while q:
            u = q.popleft()
            minL, maxL = max(u-k+1,0), min(u,n-k)
            for l in range(minL, maxL+1):
                v = l+k-1-(u-l)
                if not is_banned[v] and res[v]==-1:
                    res[v]=res[u]+1; q.append(v)
        return res

Rust

use std::collections::VecDeque;
impl Solution {
    pub fn min_reverse_operations(n: i32, p: i32, banned: Vec<i32>, k: i32) -> Vec<i32> {
        let n = n as usize; let p = p as usize; let k = k as usize;
        let mut res = vec![-1;n]; let mut is_banned = vec![false;n];
        for b in banned { is_banned[b as usize]=true; }
        let mut q = VecDeque::new(); q.push_back(p); res[p]=0;
        while let Some(u) = q.pop_front() {
            let min_l = u+1>=k ? u+1-k : 0;
            let max_l = if u>n-k { n-k } else { u };
            for l in min_l..=max_l {
                let v = l+k-1-(u-l);
                if v<n && !is_banned[v] && res[v]==-1 {
                    res[v]=res[u]+1; q.push_back(v);
                }
            }
        }
        res
    }
}

TypeScript

class Solution {
    minReverseOperations(n: number, p: number, banned: number[], k: number): number[] {
        const res = Array(n).fill(-1);
        const isBanned = Array(n).fill(false);
        for (const b of banned) isBanned[b]=true;
        const q = [p]; res[p]=0;
        while (q.length) {
            const u = q.shift()!;
            const minL = Math.max(u-k+1,0), maxL = Math.min(u,n-k);
            for (let l = minL; l <= maxL; l++) {
                const v = l+k-1-(u-l);
                if (!isBanned[v] && res[v]===-1) {
                    res[v]=res[u]+1; q.push(v);
                }
            }
        }
        return res;
    }
}

Complexity

• ⏰ Time complexity: O(n*k) — Each position can be reached in O(k) ways.
• 🧺 Space complexity: O(n) — For result and banned arrays.