LeetCode 2612 (Hard). Minimum Reverse Operations. Swift. BFS. O(n+k). O(n)

Sergey Leschev. LeetCode Global TOP 200.

You are given an integer n and an integer p in the range [0, n - 1]. Representing a 0-indexed array arr of length n where all positions are set to 0's, except position p which is set to 1.

You are also given an integer array banned containing some positions from the array. For the ith position in banned, arr[banned[i]] = 0, and banned[i] != p.

You can perform multiple operations on arr. In an operation, you can choose a subarray with size k and reverse the subarray. However, the 1 in arr should never go to any of the positions in banned. In other words, after each operation arr[banned[i]] remains 0.

Return an array ans where for each i from [0, n - 1], ans[i] is the minimum number of reverse operations needed to bring the 1 to position i in arr, or -1 if it is impossible.

A subarray is a contiguous non-empty sequence of elements within an array.

The values of ans[i] are independent for all i's.The reverse of an array is an array containing the values in reverse order.

Example 1:

Input: n = 4, p = 0, banned = [1,2], k = 4

Output: [0,-1,-1,1]

Explanation: In this case k = 4 so there is only one possible reverse operation we can perform, which is reversing the whole array. Initially, 1 is placed at position 0 so the amount of operations we need for position 0 is 0. We can never place a 1 on the banned positions, so the answer for positions 1 and 2 is -1. Finally, with one reverse operation we can bring the 1 to index 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: In this case the 1 is initially at position 0, so the answer for that position is 0. We can perform reverse operations of size 3. The 1 is currently located at position 0, so we need to reverse the subarray [0, 2] for it to leave that position, but reversing that subarray makes position 2 have a 1, which shouldn't happen. So, we can't move the 1 from position 0, making the result for all the other positions -1.

Example 3:

Input: n = 4, p = 2, banned = [0,1,3], k = 1

Output: [-1,-1,0,-1]

Explanation: In this case we can only perform reverse operations of size 1. So the 1 never changes its position.

Constraints:
1 <= n <= 10^5

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

The algorithm follows a breadth-first search (BFS) approach to determine the minimum number of reverse operations needed to bring the 1 to each position in the array.

To speed up the algorithm, we mark banned positions with -2 instead of using set lookups. This optimization reduces the constant coefficient and improves the speed of the algorithm, but it may still result in a time limit exceeded (TLE) error.

For each visited position, there are potentially O(k) target positions that can be reached through reverse operations. To avoid the multiplicative cost of iterating over all these potential positions, we update the nextNode2s array. This array initially points forward by 2, but we update it dynamically to point beyond all the target positions considered for each visited position. This optimization helps improve the efficiency of the algorithm and avoids unnecessary computations.

Time complexity: O(n+k)

Space complexity: O(n)

class Solution { func minReverseOperations(_ n: Int, _ p: Int, _ banned: [Int], _ k: Int) -> [Int] { var out = Array(repeating: -1, count: n) for node in banned { out[node] = -2 } var nodes = [p] var depth = 0 out[p] = depth let step = k - 1 var nextNode2s = Array(0...(n - 1)).map { $0 + 2 } while !nodes.isEmpty { depth += 1 var newNodes = [Int]() for node1 in nodes { let loReverseStart = max(node1 - step, 0) let hiReverseStart = min(node1, n - k) let loNode2 = 2 * loReverseStart + k - 1 - node1 let hiNode2 = 2 * hiReverseStart + k - 1 - node1 let postHiNode2 = hiNode2 + 2 var node2 = loNode2 while node2 <= hiNode2 { let nextNode2 = nextNode2s[node2] nextNode2s[node2] = postHiNode2 if node2 >= 0 && node2 < n && out[node2] == -1 { newNodes.append(node2) out[node2] = depth } node2 = nextNode2 } } nodes = newNodes } for i in 0..<n { if out[i] == -2 { out[i] = -1 } } return out } }

Sources: Github

#swift #leetcode #algorithms

LeetCode 2612 (Hard). Minimum Reverse Operations. Swift. BFS. O(n+k). O(n)

Description

Approach

Complexity

Code (Swift)