Minimum Reverse Operations
HardPrompt
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
kif the single 1 is not set to a position inbanned.
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 <= 1050 <= p <= n - 10 <= banned.length <= n - 10 <= banned[i] <= n - 11 <= k <= nbanned[i] != p- all values in
bannedare 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
bannedpositions for quick O(1) lookups. - Initialize an
answerarray of sizenwith-1and avisitedarray of sizenwithfalse. - Create a queue for the BFS and add the starting position
p. - Set
answer[p] = 0andvisited[p] = true. - While the queue is not empty:
- Dequeue the current position, let's call it
u, and get its distanced = answer[u]. - Determine the range of possible starting indices
jfor ak-sized subarray that includesu. This range is[max(0, u - k + 1), min(n - k, u)]. - Iterate through each possible
jin this range. - For each
j, calculate the next positionvof the1after the reversal:v = j + (j + k - 1) - u. - If
vis a valid index, not banned, and not yet visited:- Mark
vas visited. - Set
answer[v] = d + 1. - Enqueue
v.
- Mark
- Dequeue the current position, let's call it
- After the BFS completes, the
answerarray 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.
The bottleneck in the naive BFS is the neighbor discovery step, which takes O(K) time for each node. We can optimize this by observing a key property: all positions reachable from a position u in one step lie within a contiguous range [min_v, max_v] and, more importantly, all share the same parity.
This observation allows us to maintain two separate sets of available (unvisited and not banned) indices: one for even indices and one for odd indices. By using an ordered set data structure like Java's TreeSet, we can efficiently query for all available indices within a specific range. This reduces the complexity of finding neighbors from O(K) to O(log N + M), where M is the number of neighbors found. Since each node is found as a neighbor only once during the entire BFS, the total time complexity is significantly improved.
Algorithm
- Initialize data structures:
answerarray,bannedset, and a BFS queue. - Create two
TreeSets (ordered sets), one for available even indices (availableEven) and one for available odd indices (availableOdd). - Populate these
TreeSets with all indices from0ton-1that are not in thebannedset. - Start the BFS: add
pto the queue, setanswer[p] = 0, and removepfrom its correspondingTreeSet. - While the queue is not empty:
- Dequeue the current position
uand its distanced. - Calculate the range of possible next positions,
[min_v, max_v], based on the possible start indicesjof the reversal subarray. - Determine the parity of the neighbors. If
kis odd, neighbors have the same parity asu. Ifkis even, they have the opposite parity. Select the correspondingTreeSetto search. - Use the
TreeSet.subSet(min_v, true, max_v, true)method to efficiently get an iterable view of all available neighbors within the calculated range. - Iterate through this view. For each neighbor
vfound:- Set
answer[v] = d + 1. - Enqueue
v. - Add
vto a temporary list for removal.
- Set
- After iterating, remove all found neighbors from the
TreeSetto mark them as visited.
- Dequeue the current position
Walkthrough
This approach enhances the standard BFS by using a more efficient data structure for tracking available nodes. Instead of a simple visited array, we use two TreeSets to store unvisited, non-banned indices, partitioned by their parity (even or odd).
When processing a node u from the BFS queue, we first calculate the range of possible next positions. A move from u to v implies u + v = 2*j + k - 1. This means v - u has the same parity as k - 1. Consequently:
- If
kis odd,k-1is even.vandumust have the same parity. - If
kis even,k-1is odd.vandumust have different parities.
This rule tells us which TreeSet (even or odd) to search for neighbors. We then calculate the minimum and maximum possible values for a neighbor v and use the TreeSet.subSet() method to get all available nodes in that range. This is very efficient. Each node found is a new node to visit. We add it to the queue and remove it from its TreeSet to mark it as visited. We collect all neighbors from the subSet view into a temporary list before modifying the TreeSet to avoid ConcurrentModificationException.
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); } TreeSet<Integer> availableEven = new TreeSet<>(); TreeSet<Integer> availableOdd = new TreeSet<>(); for (int i = 0; i < n; i++) { if (!bannedSet.contains(i)) { if (i % 2 == 0) { availableEven.add(i); } else { availableOdd.add(i); } } } Queue<Integer> queue = new LinkedList<>(); if (!bannedSet.contains(p)) { ans[p] = 0; queue.offer(p); if (p % 2 == 0) { availableEven.remove(p); } else { availableOdd.remove(p); } } while (!queue.isEmpty()) { int curr = queue.poll(); int dist = ans[curr]; int minJ = Math.max(0, curr - k + 1); int maxJ = Math.min(n - k, curr); int minNextPos = 2 * minJ + k - 1 - curr; int maxNextPos = 2 * maxJ + k - 1 - curr; TreeSet<Integer> targetSet = (k % 2 == 1) ? (curr % 2 == 0 ? availableEven : availableOdd) : (curr % 2 == 0 ? availableOdd : availableEven); List<Integer> neighbors = new ArrayList<>(); for (Integer nextPos : targetSet.subSet(minNextPos, true, maxNextPos, true)) { neighbors.add(nextPos); } for (Integer neighbor : neighbors) { ans[neighbor] = dist + 1; queue.offer(neighbor); targetSet.remove(neighbor); } } return ans; }}Complexity
Time
O(N log N). Initializing the `TreeSet`s takes O(N log N). Each of the N nodes is enqueued and processed once. For each node, we perform a range query on a `TreeSet`. Finding the start of the range takes O(log N). Each neighbor is found and removed once, costing O(log N) per neighbor. The total complexity of all `TreeSet` operations throughout the BFS is O(N log N).
Space
O(N), where N is the number of elements. The `TreeSet`s can store up to N elements in total. The queue, `banned` set, and `answer` array also contribute to this.
Trade-offs
Pros
Highly efficient with a time complexity of O(N log N), which passes the given constraints.
Effectively utilizes data structures to optimize the neighbor-finding process in BFS.
Cons
More complex to implement due to the use of
TreeSets and the logic for calculating ranges and parities.
Solutions
Solution
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; }}class Solution {public: vector<int> minReverseOperations(int n, int p, vector<int> &banned, int k) { vector<int> ans(n, -1); ans[p] = 0; set<int> ts[2]; for (int i = 0; i < n; ++i) { ts[i % 2].insert(i); } ts[p % 2].erase(p); for (int i : banned) { ts[i % 2].erase(i); } ts[0].insert(n); ts[1].insert(n); queue<int> q{{p}}; while (!q.empty()) { int i = q.front(); q.pop(); int mi = max(i - k + 1, k - i - 1); int mx = min(i + k - 1, n * 2 - k - i - 1); auto &s = ts[mi % 2]; auto it = s.lower_bound(mi); while (*it <= mx) { int j = *it; ans[j] = ans[i] + 1; q.push(j); it = s.erase(it); } } return ans; }};from sortedcontainers import SortedSet class Solution : def minReverseOperations ( self , n : int , p : int , banned : List [ int ], k : int ) -> List [ int ]: ans = [ - 1 ] * n ans [ p ] = 0 ts = [ SortedSet () for _ in range ( 2 )] for i in range ( n ): ts [ i % 2 ]. add ( i ) ts [ p % 2 ]. remove ( p ) for i in banned : ts [ i % 2 ]. remove ( i ) ts [ 0 ]. add ( n ) ts [ 1 ]. add ( n ) q = deque ([ p ]) while q : i = q . popleft () mi = max ( i - k + 1 , k - i - 1 ) mx = min ( i + k - 1 , n * 2 - k - i - 1 ) s = ts [ mi % 2 ] j = s . bisect_left ( mi ) while s [ j ] <= mx : q . append ( s [ j ]) ans [ s [ j ]] = ans [ i ] + 1 s . remove ( s [ j ]) j = s . bisect_left ( mi ) return ansVideo 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.