Fast Solution | Swift | BFS | O(n+k) | O(n)
Approach\nThe algorithm follows a breadth-first search (BFS) approach to determine the minimum number of reverse operations needed to bring the 1 to each positi
# Approach\nThe 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.\n\nTo 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.\n\nFor 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.\n\n# Complexity\n- Time complexity: O(n+k)\n- Space complexity: O(n)\n\n# Code\n```\nclass Solution {\n    func minReverseOperations(_ n: Int, _ p: Int, _ banned: [Int], _ k: Int) -> [Int] {\n        var out = Array(repeating: -1, count: n)\n        \n        for node in banned {\n            out[node] = -2\n        }\n        \n        var nodes = [p]\n        var depth = 0\n        out[p] = depth\n        let step = k - 1\n        var nextNode2s = Array(0...(n - 1)).map { $0 + 2 }\n        \n        while !nodes.isEmpty {\n            depth += 1\n            var newNodes = [Int]()\n            \n            for node1 in nodes {\n                let loReverseStart = max(node1 - step, 0)\n                let hiReverseStart = min(node1, n - k)\n                let loNode2 = 2 * loReverseStart + k - 1 - node1\n                let hiNode2 = 2 * hiReverseStart + k - 1 - node1\n                \n                let postHiNode2 = hiNode2 + 2\n                var node2 = loNode2\n                \n                while node2 <= hiNode2 {\n                    let nextNode2 = nextNode2s[node2]\n                    nextNode2s[node2] = postHiNode2\n                    \n                    if node2 >= 0 && node2 < n && out[node2] == -1 {\n                        newNodes.append(node2)\n                        out[node2] = depth\n                    }\n                    \n                    node2 = nextNode2\n                }\n            }\n            \n            nodes = newNodes\n        }\n        \n        for i in 0..<n {\n            if out[i] == -2 {\n                out[i] = -1\n            }\n        }\n        \n        return out\n    }\n}\n\n```
['Breadth-First Search', 'Swift']