Scale Engineer

Minimum Reverse Operations

Hard
#2392Time: O(N * K), where N is the number of elements and K is the subarray size. In the worst case, for each of the N nodes, we might iterate up to K times to find all its neighbors. Given N up to 10^5 and K up to N, this can be as slow as O(N^2).Space: O(N), where N is the number of elements. This is for the queue, the `banned` set, the `visited` array, and the `answer` array.1 company
Algorithms
Breadth-First Search
Data structures
ArrayOrdered Set
Companies
Infosys

Prompt

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.

 

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 <= 105
  • 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 

Approaches

2 approaches with complexity analysis and trade-offs.

This problem can be modeled as finding the shortest path from a source node p to all other nodes in an unweighted graph. The nodes of the graph are the indices 0, 1, ..., n-1. An edge exists from index u to v if the 1 can be moved from u to v in a single reverse operation. Since each operation (edge) has a weight of 1, Breadth-First Search (BFS) is the perfect algorithm to find the minimum number of operations.

The naive approach involves a direct implementation of BFS. For each position visited, we generate all possible next positions by iterating through all valid subarrays of size k that contain the current position.

Algorithm

  • Create a set for banned positions for quick O(1) lookups.
  • Initialize an answer array of size n with -1 and a visited array of size n with false.
  • Create a queue for the BFS and add the starting position p.
  • Set answer[p] = 0 and visited[p] = true.
  • While the queue is not empty:
    • Dequeue the current position, let's call it u, and get its distance d = answer[u].
    • Determine the range of possible starting indices j for a k-sized subarray that includes u. This range is [max(0, u - k + 1), min(n - k, u)].
    • Iterate through each possible j in this range.
    • For each j, calculate the next position v of the 1 after the reversal: v = j + (j + k - 1) - u.
    • If v is a valid index, not banned, and not yet visited:
      • Mark v as visited.
      • Set answer[v] = d + 1.
      • Enqueue v.
  • After the BFS completes, the answer array contains the minimum operations for each position.

Walkthrough

The core of this approach is a standard BFS algorithm. We start at position p. In each step of the BFS, we explore all reachable positions from the current one. A position v is reachable from u if there's a subarray of length k containing u which, when reversed, moves the 1 to v.

To find all neighbors of a node u, we must consider every possible subarray of length k that contains u. A subarray starting at index j has the range [j, j + k - 1]. For this subarray to contain u, we must have j <= u < j + k. Also, the subarray must be within the bounds of the main array, so 0 <= j and j + k - 1 < n. Combining these, the starting index j can range from max(0, u - k + 1) to min(n - k, u). For each valid j, the new position v is calculated by finding the symmetric position of u within the subarray [j, j + k - 1], which is v = j + (j + k - 1) - u.

We use a queue to manage the nodes to visit, a visited array to avoid cycles and redundant computations, and an answer array to store the results.

import java.util.*; class Solution {    public int[] minReverseOperations(int n, int p, int[] banned, int k) {        int[] ans = new int[n];        Arrays.fill(ans, -1);         Set<Integer> bannedSet = new HashSet<>();        for (int b : banned) {            bannedSet.add(b);        }         Queue<Integer> queue = new LinkedList<>();        boolean[] visited = new boolean[n];         if (!bannedSet.contains(p)) {            ans[p] = 0;            queue.offer(p);            visited[p] = true;        }         while (!queue.isEmpty()) {            int curr = queue.poll();            int dist = ans[curr];             // Iterate through all possible start positions 'j' of the subarray            int minJ = Math.max(0, curr - k + 1);            int maxJ = Math.min(n - k, curr);             for (int j = minJ; j <= maxJ; j++) {                int nextPos = j + (j + k - 1) - curr;                                if (nextPos >= 0 && nextPos < n && !bannedSet.contains(nextPos) && !visited[nextPos]) {                    visited[nextPos] = true;                    ans[nextPos] = dist + 1;                    queue.offer(nextPos);                }            }        }        return ans;    }}

Complexity

Time

O(N * K), where N is the number of elements and K is the subarray size. In the worst case, for each of the N nodes, we might iterate up to K times to find all its neighbors. Given N up to 10^5 and K up to N, this can be as slow as O(N^2).

Space

O(N), where N is the number of elements. This is for the queue, the `banned` set, the `visited` array, and the `answer` array.

Trade-offs

Pros

  • Conceptually simple and easy to implement.

  • Correctly models the problem as a shortest path search.

Cons

  • The time complexity of O(N * K) is too slow for the given constraints and will likely result in a 'Time Limit Exceeded' error.

Solutions

class Solution {public  int[] minReverseOperations(int n, int p, int[] banned, int k) {    int[] ans = new int[n];    TreeSet<Integer>[] ts = new TreeSet[]{new TreeSet<>(), new TreeSet<>()};    for (int i = 0; i < n; ++i) {      ts[i % 2].add(i);      ans[i] = i == p ? 0 : -1;    }    ts[p % 2].remove(p);    for (int i : banned) {      ts[i % 2].remove(i);    }    ts[0].add(n);    ts[1].add(n);    Deque<Integer> q = new ArrayDeque<>();    q.offer(p);    while (!q.isEmpty()) {      int i = q.poll();      int mi = Math.max(i - k + 1, k - i - 1);      int mx = Math.min(i + k - 1, n * 2 - k - i - 1);      var s = ts[mi % 2];      for (int j = s.ceiling(mi); j <= mx; j = s.ceiling(mi)) {        q.offer(j);        ans[j] = ans[i] + 1;        s.remove(j);      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem