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

Description

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

Approach

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.

Complexity

Time complexity: O(n+k)
Space complexity: O(n)

Code (Swift)

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