2612. Minimum Reverse Operations

HardBreadth-First SearchArrayOrdered Set
Leetcode Link

Problem Description

In this problem, you are given an integer n which stands for the length of an array arr that is initialized with all zeros, except for a single position p which is set to 1. There is also an array called banned that contains indexes in the array arr which must always remain zero - these are the positions that the 1 cannot move to. You have the ability to perform reverse operations on any subarray of size k, which flips the order of elements in that subarray. The challenge is to calculate the minimum number of such operations required to move the 1 from its initial position to every other position in the array that is not banned. If it's not possible to move the 1 to a specific position due to the restrictions imposed by the banned positions, the output for that position should be -1. The result should be returned as an array ans, where ans[i] represents the minimum operations to move the 1 to position i.

Intuition

To approach the solution for this problem, we need to realize that when an index's element gets its position reversed because of a subarray flip, it follows an arithmetic progression - specifically, every reverse operation changes its position by 2. Also, because an index only moves within a certain range around it when reversed, only indices with the same parity (i.e., both even or both odd) can be reached from a given index since we are incrementing or decrementing by 2.

Considering this, any index can transition to any other index of the same parity within the range [i - k + 1, i + k - 1]. There are boundaries to these transitions, which are based on the edge of the array or the size of the flipping subarray. On the edges of the array, the reachable indices are limited. If we look at the left boundary, an element can at most be moved from index i to k - i - 1. Similarly, for the right boundary, an element can be moved to 2 * n - k - i - 1.

With these constraints in mind, we use two ordered sets to track which even and odd indices can still be targeted by these flip operations, excluding the banned positions and the original position of the 1. Then, by using Breadth-First Search (BFS), we sequentially flip subarrays to bring the 1 closer to the target positions. Each time we move 1 to a new position, we check all the indices it can now flip to within the defined boundaries, update their minimum operation count, add them to the queue for further processing, and remove them from the corresponding ordered set to avoid revisiting them.

As the BFS proceeds, it finds the shortest path (minimum flips) required to bring the 1 to each index by flipping through the array while avoiding banned positions. The BFS ensures that once we reach an index, we have done so with the minimal number of operations (since BFS always finds the shortest path first), and removing processed indices ensures we don't process the same index multiple times.

Learn more about Breadth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Solution Approach

The solution uses a combination of Breadth-First Search (BFS) algorithm and Ordered Sets (specifically a SortedSet from the sortedcontainers package in Python). The algorithm iteratively explores the minimum steps required to get the 1 to each valid position in the array, while avoiding the banned indices.

Here's an overview of how the implementation works:

  • First, initialize the ans array to -1, indicating that initially, we assume it's impossible to reach any position other than the starting position p. Set ans[p] to 0, as we're already at position p with no operations.

  • Create two Ordered Sets (one for even indices and another for odd indices) to leverage their properties of maintaining elements in a sorted order and to allow for efficient insertions, deletions, and lookups. This is essential for our problem to quickly determine the next index to consider for a flip operation.

  • Remove any banned indices and the starting index p from the corresponding Ordered Sets, ensuring they are not accidentally traversed during the process.

  • Add an extra index (n, the length of the array) to both Ordered Sets so we can correctly handle subarray selections near the edge of the array without running out of bounds.

  • Initialize a queue with the starting index p where BFS will start its exploration.

  • The BFS loop continues until there are no more indices to explore. In each iteration:

    • Pop the front index i from the queue.

    • Calculate the minimum (mi) and maximum (mx) indices that can be reached by a flip operation from the current index i within the boundaries of the array and the size k of the subarray.

    • Retrieve the relevant SortedSet (s) for the parity of the indices we are processing, whether even or odd.

    • Determine the range of valid indices that could be flipped to from i, which are the indices with the same parity, within mi and mx.

    • Utilize the bisect_left method available in the SortedSet to find the smallest index j that is greater than or equal to mi. This gives us the starting index to explore from within the valid range.

    • Iterate over the SortedSet to flip each valid index within the range, updating ans[j] to be ans[i] + 1 each time (since reaching index j takes one more operation than it took to reach index i).

    • For each flipped index j, add it to the BFS queue for further exploration, and remove it from the SortedSet to avoid duplication of work.

Once BFS completes, every non-banned index in the ans array should contain the minimum number of flip operations required to bring the 1 there from position p, or -1 if it is impossible due to the banned restrictions.

This algorithm ensures correctness due to the nature of BFS always finding the shortest path first and the intelligent handling of index parity which is inherent to the problem's operations. Ordered Sets make the implementation efficient by keeping indices in order and providing fast operations to manipulate them.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

Example Walkthrough

Let's illustrate the solution approach using a small example:

Suppose n = 5, which means our array arr looks like: [0, 0, 0, 0, 0] (indices are [0, 1, 2, 3, 4]). Let's assume the 1 starts at position p = 2, thus arr becomes: [0, 0, 1, 0, 0]. The banned array contains the index 3, so arr[3] should always remain 0. We are allowed to reverse subarrays of size k = 3.

With this setup, our goal is to move 1 to all other positions except 3, while trying to minimize the number of operations (subarray reversals).

  1. Initialize the ans array to [-1, -1, 0, -1, -1], indicating impossible positions with -1 except where the 1 initially is.

  2. Define two SortedSets: one for even indices {0, 4}, and one for odd indices {1} (we exclude 3 because it's banned and 2 because it's the starting position) and add n to both (which becomes {0, 4, 5} and {1, 5}).

  3. Start BFS with the initial position p = 2 in the queue.

  4. For the first iteration, dequeue p = 2:

    • mi (the minimum index we can reach from 2) is 2 - 3 + 1 = 0, and mx (the maximum) is 2 + 3 - 1 = 4.
    • Since p is even, we use the even SortedSet {0, 4, 5}, and find the valid range in the set is {0, 4}.
    • We flip 0 and 4, updating ans to: [1, -1, 0, -1, 1] (it takes 1 operation to reach these positions) and enqueue them for BFS while removing from the set: {5}.

  5. On the next BFS iterations, if we dequeue 0:

    • mi from 0 is 0 (since we can't go lower) and mx is 2.
    • The odd SortedSet is {1, 5}, and the valid range is {1}.
    • We flip 1, updating ans to: [1, 2, 0, -1, 1] (it takes 2 operations to reach position 1 from position 0) and enqueue 1 for BFS while removing it from the set: {5}.

  6. We continue this process until all reachable positions are evaluated or the queue is empty.

At the end of the BFS, the ans array will reflect the minimum operations required to move the 1 to each position, or -1 where it is not possible.

For our example, the final ans array would be [1, 2, 0, -1, 1], showing that it's impossible to get to position 3 due to it being banned, and taking into account the minimum number of subarray reversal operations required to reach the other positions.

Solution Implementation

1from sortedcontainers import SortedSet
2from typing import List
3from collections import deque
4
5class Solution:
6    def min_reverse_operations(self, n: int, p: int, banned: List[int], k: int) -> List[int]:
7        # Initialize a list to hold the answer, with -1 for all indices.
8        # The position `p` is set to 0 as it requires 0 operations to reach from itself.
9        ans = [-1] * n
10        ans[p] = 0
11      
12        # Create two SortedSet instances, one for even indices and one for odd indices.
13        even_odd_sets = [SortedSet() for _ in range(2)]
14      
15        # Populate even_odd_sets with all possible indices, segregated by even and odd.
16        for i in range(n):
17            even_odd_sets[i % 2].add(i)
18      
19        # Remove the initial position `p` and the banned positions from the respective set.
20        even_odd_sets[p % 2].discard(p)
21        for banned_position in banned:
22            even_odd_sets[banned_position % 2].discard(banned_position)
23      
24        # Add a sentinel value (`n`) to both sets to avoid index-out-of-range during set operations.
25        even_odd_sets[0].add(n)
26        even_odd_sets[1].add(n)
27      
28        # Create a queue and begin BFS with the initial position `p`.
29        queue = deque([p])
30        while queue:
31            current_pos = queue.popleft()
32          
33            # Define the minimum and maximum indices we can move to from the current position.
34            min_index = max(current_pos - k + 1, k - current_pos - 1)
35            max_index = min(current_pos + k - 1, n * 2 - k - current_pos - 1)
36          
37            # Select the set that contains the same parity indices as `min_index`.
38            current_set = even_odd_sets[min_index % 2]
39
40            # Find the leftmost index in the set that is greater than or equal to `min_index`.
41            next_index = current_set.bisect_left(min_index)
42          
43            # Continue this process for all indices within the defined range (mi, mx].
44            while current_set[next_index] <= max_index:
45                # Append this index to the queue and update the answer for it.
46                queue.append(current_set[next_index])
47                ans[current_set[next_index]] = ans[current_pos] + 1
48              
49                # Remove the current index from the set as we have found the minimum operations for it.
50                current_set.discard(current_set[next_index])
51              
52                # Re-find the leftmost index in the set that is greater than or equal to `min_index`.
53                next_index = current_set.bisect_left(min_index)
54      
55        # Return the completed answer list.
56        return ans
57
1class Solution {
2  
3    public int[] minReverseOperations(int n, int start, int[] banned, int k) {
4        int[] result = new int[n]; // To store the minimum reverse operations
5
6        // Create two TreeSets to separate indices based on even and odd parity
7        TreeSet<Integer>[] treeSets = new TreeSet[]{new TreeSet<>(), new TreeSet<>()};
8
9        // Initialize the result array and populate the TreeSets with index positions
10        for (int i = 0; i < n; ++i) {
11            treeSets[i % 2].add(i);
12            result[i] = i == start ? 0 : -1; // Initialize with 0 for start position, -1 for others
13        }
14        // Remove the start position from its respective TreeSet as it is already counted.
15        treeSets[start % 2].remove(start);
16        // Remove the banned positions from their respective TreeSet.
17        for (int pos : banned) {
18            treeSets[pos % 2].remove(pos);
19        }
20        // Add 'n' to both TreeSets as a sentinel value
21        treeSets[0].add(n);
22        treeSets[1].add(n);
23
24        // Use a deque to perform a BFS-like algorithm
25        Deque<Integer> queue = new ArrayDeque<>();
26        queue.offer(start);
27        while (!queue.isEmpty()) {
28            int currentIndex = queue.poll();
29            // Calculate the minimum and maximum index we can move to during this step
30            int minIndex = Math.max(currentIndex - k + 1, k - currentIndex - 1);
31            int maxIndex = Math.min(currentIndex + k - 1, n * 2 - k - currentIndex - 1);
32            // Select the TreeSet with the same parity as the minIndex
33            var currentSet = treeSets[minIndex % 2];
34
35            // Iterate through the valid indices within the TreeSet
36            for (int nextIndex = currentSet.ceiling(minIndex); nextIndex <= maxIndex; nextIndex = currentSet.ceiling(minIndex)) {
37                // Add next index to queue and update result with the number of moves taken
38                queue.offer(nextIndex);
39                result[nextIndex] = result[currentIndex] + 1;
40                // Remove the index from the TreeSet as it's processed
41                currentSet.remove(nextIndex);
42            }
43        }
44        return result; // Return the array with the minimum reverse operations
45    }
46}
47
1#include <vector>
2#include <set>
3#include <queue>
4using namespace std;
5
6class Solution {
7public:
8    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
9        vector<int> answer(n, -1); // Initialize the answer vector with -1
10        answer[p] = 0; // The start position requires 0 operations to reach
11        set<int> tiles[2]; // Create sets to hold positions for even and odd indices
12      
13        // Populate the sets with all possible positions
14        for (int i = 0; i < n; ++i) {
15            tiles[i % 2].insert(i);
16        }
17      
18        // Remove the start position from the appropriate set
19        tiles[p % 2].erase(p);
20      
21        // Remove banned positions from the appropriate sets
22        for (int bannedPosition : banned) {
23            tiles[bannedPosition % 2].erase(bannedPosition);
24        }
25      
26        // Insert a sentinel value of n to mark the end of each set
27        tiles[0].insert(n);
28        tiles[1].insert(n);
29      
30        // Start the BFS with the start position
31        queue<int> positionsQueue{{p}};
32      
33        while (!positionsQueue.empty()) {
34            // Take the front position from the queue
35            int currentPosition = positionsQueue.front();
36            positionsQueue.pop();
37          
38            // Calculate minimum and maximum reachable indices from currentPosition
39            int minIndex = max(currentPosition - k + 1, k - currentPosition - 1);
40            int maxIndex = min(currentPosition + k - 1, n * 2 - k - currentPosition - 1);
41          
42            // Select the set which corresponds to the parity of the starting index
43            auto& currentSet = tiles[minIndex % 2];
44          
45            // Find the lower bound of positions we can jump to from the currentPosition
46            auto it = currentSet.lower_bound(minIndex);
47          
48            // Iterate over all reachable positions and update their operation counts
49            while (*it <= maxIndex) {
50                int jumpPosition = *it;
51                answer[jumpPosition] = answer[currentPosition] + 1; // One more operation than currentPosition
52                positionsQueue.push(jumpPosition); // Add this position to the queue for further processing
53                it = currentSet.erase(it); // Remove the position from the set and move iterator to next element
54            }
55        }
56      
57        // Return the final answer vector where each index has the minimum number of reverse operations needed
58        return answer;
59    }
60};
61
1type CompareFn<T> = (lhs: T, rhs: T) => number;
2
3let treeSize: number;
4let tree: RBTree<number>;
5let compareFn: CompareFn<number>;
6
7function initializeTreeSet(
8    collection: number[] | CompareFn<number> = [],
9    compare: CompareFn<number> = (l, r) => (l < r ? -1 : l > r ? 1 : 0),
10) {
11    if (typeof collection === 'function') {
12        compare = collection;
13        collection = [];
14    }
15    treeSize = 0;
16    compareFn = compare;
17    tree = new RBTree(compare);
18    for (const val of collection) {
19        treeSetAdd(val);
20    }
21}
22
23function treeSetSize(): number {
24    return treeSize;
25}
26
27function treeSetHas(val: number): boolean {
28    return !!treeFind(val);
29}
30
31// Add a new element to the tree set
32function treeSetAdd(val: number): boolean {
33    const successful = treeInsert(val);
34    treeSize += successful ? 1 : 0;
35    return successful;
36}
37
38// Remove an element from the tree set
39function treeSetDelete(val: number): boolean {
40    const successful = treeDeleteAll(val);
41    treeSize -= successful ? 1 : 0;
42    return successful;
43}
44
45// Find the lowest element greater than or equal to a given value
46function treeSetCeil(val: number): number | undefined {
47    let node = tree.root;
48    let higher: RBTreeNode<number> | null = null;
49    while (node) {
50        if (compareFn(node.data, val) >= 0) {
51            higher = node;
52            node = node.left;
53        } else {
54            node = node.right;
55        }
56    }
57    return higher?.data;
58}
59
60// Find the highest element lower than or equal to a given value
61function treeSetFloor(val: number): number | undefined {
62    let node = tree.root;
63    let lower: RBTreeNode<number> | null = null;
64    while (node) {
65        if (compareFn(val, node.data) >= 0) {
66            lower = node;
67            node = node.right;
68        } else {
69            node = node.left;
70        }
71    }
72    return lower?.data;
73}
74
75// Rest of the TreeSet functions...
76
Not Sure What to Study? Take the 2-min Quiz：

What are the most two important steps in writing a depth first search function? (Select 2)

Time and Space Complexity

The time complexity of the function mainly consists of these parts:

  • Initial setup of the ans list, which takes O(n) time as it creates a list of -1 of size n.
  • Creation of the two SortedSet instances, each insertion operation in a SortedSet takes O(log n) time and overall for n elements (including banned ones and the added n) it totals to O(m log m) where m is the number of elements added to the sets.
  • The removal of elements from the SortedSet instances. There can be up to n removal operations, and each removal operation takes O(log n) time. Thus, the total for this part is also O(n log n).
  • The while loop which includes a deque popping operation which is O(1) per element. For the SortedSet range queries and removals, the worst-case scenario would involve visiting each element once at a cost of O(log n) per access/removal operation, which sums up to O(n log n).

Given these parts, it is important to note the complexity O(m log m) of inserting elements into the SortedSet, which is dominated by the O(n log n) operations since we're considering the input size as n.

The space complexity of the function consists of:

  • The ans list which takes O(n) space.
  • The two SortedSet instances which can contain up to n items each (initially all indexes of the array and then some are removed), thus taking O(n) space.
  • The deque which in the worst-case can contain n elements, again taking up O(n) space.

Putting this together, we get that the time complexity of the function is O(n \log n) and the space complexity is O(n), which agrees with the provided reference answer.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Recommended Readings

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫