Skip to main content
Talentd

Minimum Reverse Operations - Solution & Explanation

HardArrayBreadth-First SearchOrdered Set35 min readAsked at: Infosys
Practice this problem

Problem Statement

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 

Approach Overview

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.

Approach 1: Approach 1: Breadth-First Search (BFS)

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Dynamic Programming

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n * k), within nested iteration.
Space Complexity: O(n), primarily for storing DP results.

Try this approach in the editor →

Approach 3: Ordered Set + BFS

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.

  • If the boundary is not considered, the range of values ​​of j is [i - k + 1, i + k - 1].
  • If the subarray is on the left, then [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).
  • If the subarray is on the right, then [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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Breadth-First Search (BFS)

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.

Approach 2: Dynamic Programming

Time Complexity: O(n * k), within nested iteration.
Space Complexity: O(n), primarily for storing DP results.

Ordered Set + BFS—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS with Ordered SetO(n log n)O(n)Large constraints where you must efficiently discover reachable indices without scanning all windows
Dynamic Programming SimulationO(n * k)O(n)Conceptual understanding or small input sizes where enumerating reversal windows is acceptable

Video Solution

2612. Minimum Reverse Operations | Weekly Contest 339 | LeetCode 2612 • Bro Coders • 1,874 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Minimum Reverse Operations easy or hard?
Minimum Reverse Operations is classified as a Hard problem with a low acceptance rate around 16%. The difficulty comes from deriving the index transformation after reversal and optimizing neighbor discovery so the BFS does not scan every possible subarray.
Minimum Reverse Operations Python/Java solution
Python implementations commonly use BFS with sorted containers or bisect-based structures, while Java solutions often rely on TreeSet for ordered index retrieval. Both follow the same idea: compute the reachable index range, query the ordered set for candidates, and push them into the BFS queue with distance +1.
How to solve Minimum Reverse Operations in O(n)?
A near-linear solution comes from modeling the problem as BFS and deriving the range of indices reachable after reversing a window containing the current position. By grouping indices by parity and removing them from ordered sets once visited, you avoid revisiting states and keep the total operations close to linear, typically implemented as O(n log n).
What is the best approach for Minimum Reverse Operations?
The most efficient approach uses Breadth-First Search combined with ordered sets. BFS guarantees minimum operations, while ordered sets allow you to quickly retrieve unvisited indices within the reachable range created by reversing a k-length subarray. By separating indices into even and odd sets, you avoid scanning the entire array and achieve about O(n log n) time complexity.
Is Minimum Reverse Operations asked at Google/Amazon/Meta?
Hard BFS and graph-transformation problems like this frequently appear in interviews at companies such as Google, Meta, and Amazon. The problem tests graph modeling, mathematical reasoning about array reversals, and efficient data structures like ordered sets or balanced trees.
What data structure is used in Minimum Reverse Operations?
The optimal solution uses a queue for BFS and ordered sets (often implemented with TreeSet, SortedSet, or balanced BST structures). Two sets are typically maintained for even and odd indices to efficiently fetch valid unvisited positions within a computed range.
What is the time complexity of Minimum Reverse Operations?
The optimized solution runs in O(n log n) time and O(n) space. Each index is inserted and removed from an ordered set at most once, and BFS processes each node a single time. Range queries on the ordered set add the logarithmic factor.

Ready to solve this problem?

Practice Minimum Reverse Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays