BFS Java Solution 7ms || 100% working 🔥🔥
Intuition\nUsing BFS to traverse a graph-like representation of the sequence and keeping track of the depth or level of each position to determine the minimum n
# Intuition\nUsing BFS to traverse a graph-like representation of the sequence and keeping track of the depth or level of each position to determine the minimum number of reverse operations. Taking into account banned positions to optimize the algorithm.\n\n\n# Approach\n\nThe approach involves using BFS to find the minimum number of reverse operations required to transform a given sequence. We initialize an array to store the result and mark banned positions. Starting from a given position, we perform a BFS traversal, keeping track of the depth and updating the result array. Finally, we return the result array.\n\n# Complexity\n- Time complexity: ***O(n+k)***\n\n- Space complexity: ***O(n)***\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int[] minReverseOperations(int n, int p, int[] banned, int k) {\n        int[] out = new int[n];\n        Arrays.fill(out, -1);\n        \n        for (int node : banned) {\n            out[node] = -2;\n        }\n        \n        List<Integer> nodes = new ArrayList<>();\n        nodes.add(p);\n        \n        int depth = 0;\n        out[p] = depth;\n        int step = k - 1;\n        \n        int[] nextNode2s = new int[n + 1];\n        for (int i = 0; i < n + 1; i++) {\n            nextNode2s[i] = i + 2;\n        }\n        \n        while (!nodes.isEmpty()) {\n            depth++;\n            List<Integer> newNodes = new ArrayList<>();\n            \n            for (int node1 : nodes) {\n                int loReverseStart = Math.max(node1 - step, 0);\n                int hiReverseStart = Math.min(node1, n - k);\n                int loNode2 = 2 * loReverseStart + k - 1 - node1;\n                int hiNode2 = 2 * hiReverseStart + k - 1 - node1;\n                int postHiNode2 = hiNode2 + 2;\n                int node2 = loNode2;\n                while (node2 <= hiNode2) {\n                    int nextNode2 = nextNode2s[node2];\n                    nextNode2s[node2] = postHiNode2;\n                    if (node2 >= 0 && node2 < n && out[node2] == -1) {\n                        newNodes.add(node2);\n                        out[node2] = depth;\n                    }       \n                    node2 = nextNode2;\n                }\n            }   \n            nodes = newNodes;\n        }\n        for (int i = 0; i < n; i++) {\n            if (out[i] == -2) {\n                out[i] = -1;\n            }\n        }\n        return out;\n    }\n}\n\n```\n![free Delivery.png](https://assets.leetcode.com/users/images/26d5eb70-4ee8-4703-bfb7-494d356693e0_1687939722.5027916.png)
['Array', 'Breadth-First Search', 'Ordered Set', 'Java']