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:
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:
Example 2:
Input: n = 5, p = 0, banned = [2,4], k = 3
Output: [0,-1,-1,-1,-1]
Explanation:
[0, 2] because position 2 is in banned.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 <= n banned[i] != pbanned are unique Problem Overview: You start at position p in an array of length n. In one move, you can reverse any subarray of length k. Some indices are banned and cannot be visited. The task is to compute the minimum number of reverse operations needed to reach every index, or -1 if it is impossible.
Approach 1: Breadth-First Search with Ordered Set (O(n log n) time, O(n) space)
The state space is the index of the position after each reversal. Treat each index as a node in a graph and run Breadth-First Search from the starting position p. The challenge is efficiently finding all indices reachable by reversing a length-k subarray containing the current index. Reversing maps index i to l + r - i where [l, r] is the chosen window.
Instead of checking every possible window, compute the valid range of reachable indices mathematically. All reachable targets form a sequence with alternating parity. Maintain two ordered sets (even and odd indices) containing unvisited and non-banned positions. During BFS, query the ordered set for indices within the valid range and remove them once visited. This pruning prevents repeated scanning and keeps transitions efficient.
Each index is processed once and removed from the set once, while range queries cost O(log n). BFS guarantees the first time you visit an index is the minimum number of operations. This approach scales well even when n is large because it avoids enumerating all possible reversals explicitly.
Approach 2: Dynamic Programming Simulation (O(n * k) time, O(n) space)
A more direct strategy simulates transitions by evaluating all length-k subarrays that include the current index. For each valid window [l, r], compute the resulting index after reversal and update the minimum number of operations using dynamic programming or BFS-style relaxation. The DP array stores the best known move count for every position.
This approach is easier to reason about because it mirrors the problem statement: iterate over possible windows and apply the reversal mapping. However, each index may examine up to k candidate windows, which leads to O(n * k) time in the worst case. With large constraints, this becomes too slow compared to the ordered-set BFS optimization.
Recommended for interviews: The BFS with ordered sets is the expected solution. Interviewers want to see that you model the problem as a graph traversal, derive the reversal index formula, and optimize neighbor discovery using parity grouping and ordered sets. A brute-force or simulation approach demonstrates understanding of the mechanics, but the optimized BFS shows strong algorithmic reasoning with array transformations and efficient range queries.
Using BFS, you can explore the minimum operations needed from the given starting position to every other position, treating the movement as edges in a graph. Each valid reverse operation represents an edge. The BFS will help compute the shortest path (minimum operations) to reach each position with '1'.
This C solution uses Breadth-First Search (BFS) for traversing valid operations from initial position p. We use an array to keep track of minimum operations needed to reach each position, initialized to -1 (denoting impossibility to reach). Another boolean array, isBanned, is used to check banned positions efficiently. We use a queue to process nodes in the BFS manner while checking bounds and banned conditions.
Time Complexity: O(n), where n is the number of positions in arr.
Space Complexity: O(n), primarily for the BFS queue and visited arrays.
Using Dynamic Programming (DP), build solutions incrementally by exploring possible reversals prior to marked positions. Although slightly more cumbersome with edge checking, this approach can yield insights or optimizations for specific arrangements, especially with smaller k ranges or less complex banned specifications.
The Python DP solution attempts to calculate each position's minimum operations by iteratively considering all options of reversed subarrays that might end at a particular unvisited index. The sub-increments build each position's operations count based on known previous transformations.
Python
JavaScript
Time Complexity: O(n * k), within nested iteration.
Space Complexity: O(n), primarily for storing DP results.
We notice that for any index i in the subarray interval [l,..r], the flipped index j = l + r - i.
If the subarray moves one position to the right, then j = l + 1 + r + 1 - i = l + r - i + 2, that is, j will increase by 2.
Similarly, if the subarray moves one position to the left, then j = l - 1 + r - 1 - i = l + r - i - 2, that is, j will decrease by 2.
Therefore, for a specific index i, all its flipped indices form an arithmetic progression with common difference 2, that is, all the flipped indices have the same parity.
Next, we consider the range of values of the index i after flipping j.
j is [i - k + 1, i + k - 1].[l, r] = [0, k - 1], so the flipped index j of i is 0 + k - 1 - i, that is, j = k - i - 1, so the left boundary mi = max(i - k + 1, k - i - 1).[l, r] = [n - k, n - 1], so the flipped index j= n - k + n - 1 - i is j = n times 2 - k - i - 1, so the right boundary of j is mx = min(i + k - 1, n times 2 - k - i - 1).We use two ordered sets to store all the odd indices and even indices to be searched, here we need to exclude the indices in the array banned and the index p.
Then we use BFS to search, each time searching all the flipped indices j of the current index i, that is, j = mi, mi + 2, mi + 4, \dots, mx, updating the answer of index j and adding index j to the search queue, and removing index j from the corresponding ordered set.
When the search is over, the answer to all indices can be obtained.
The time complexity is O(n times log n) and the space complexity is O(n). Where n is the given array length in the problem.
| Approach | Complexity |
|---|---|
| Approach 1: Breadth-First Search (BFS) | Time Complexity: |
| Approach 2: Dynamic Programming | Time Complexity: |
| Ordered Set + BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS with Ordered Set | O(n log n) | O(n) | Large constraints where you must efficiently discover reachable indices without scanning all windows |
| Dynamic Programming Simulation | O(n * k) | O(n) | Conceptual understanding or small input sizes where enumerating reversal windows is acceptable |
2612. Minimum Reverse Operations | Weekly Contest 339 | LeetCode 2612 • Bro Coders • 1,798 views views
Watch 6 more video solutions →Practice Minimum Reverse Operations with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor