Breadth-First Search with TreeSet: Minimum Reverse Operations for Array Positioning
Intuition\nThe approach uses a breadth-first search to find the minimum number of reverse operations required to bring the 1 to each position in the array. It e
# Intuition\nThe approach uses a breadth-first search to find the minimum number of reverse operations required to bring the 1 to each position in the array. It efficiently uses two TreeSet objects to track available positions based on their parity and avoids banned positions. By processing positions in levels, it ensures that the minimum number of moves is calculated correctly.\n\n# Approach\n1. Create two TreeSet objects, `even` and `odd`, to store positions with even and odd indices respectively.\n2. Create a boolean array, `skip`, to mark banned positions.\n3. Mark the banned positions in the `skip` array.\n4. Add values to the `even` and `odd` sets that are not banned, based on their parity.\n5. Create a `result` array and initialize it with -1 to store the minimum number of operations required for each position.\n6. Create a `Queue` called queue and add the initial position `p` to it.\n7. While the queue is not empty, do the following:\nProcess positions in the current level.\n    * Calculate the minimum and maximum indices for the subarray based on the current position and the value of `k`.\n    * Choose the appropriate TreeSet based on the parity of the minimum index.\n    * Add all positions in the range to the queue and remove them from the set.\n    * Increment the number of moves for the next level.\n8. Return the `result` array.\n\n# Complexity\n- Time complexity:\nThe code processes each position in the array once, and for each position, it performs operations on the TreeSet in logarithmic time. Therefore, the overall time complexity is O(n log n), where n is the size of the array.\n\n- Space complexity:\nThe code uses TreeSet objects to store the available positions, which require O(n) space. Additionally, it uses arrays and queues of size n for bookkeeping. Therefore, the overall space complexity is O(n).\n\n# Code\n```\nclass Solution {\n    public int[] minReverseOperations(int n, int p, int[] banned, int k) {\n        TreeSet<Integer> even = new TreeSet<>();\n        TreeSet<Integer> odd = new TreeSet<>();\n        \n        TreeSet<Integer> set;\n        \n        boolean [] skip = new boolean [n];\n        \n        for (int num : banned) {\n            skip[num] = true;\n        }\n        \n        int start = p;\n        \n        // Add values to the set that are not banned\n        for (int i = 0; i < n; ++i) {\n            if (skip[i] || i == p)\n                continue;\n            \n            if (i % 2 == 1)\n                odd.add(i);\n            else\n                even.add(i);\n        }\n        \n        int [] result = new int [n];\n        Arrays.fill(result, -1);\n        \n        Queue<Integer> queue = new LinkedList<>();\n        queue.add(p);\n        \n        int size;\n        int current;\n        int moves = 0;\n        \n        int min, max;\n        \n        Integer key;\n        \n        int mCurrent;\n        \n        while (!queue.isEmpty()) {\n            size = queue.size();\n            \n            \n            while (size-- > 0) {\n                current = queue.remove();\n                \n                result[current] = moves;\n                \n                \n                // calculate min index\n                if (current < k - 1) {\n                    min = (k - 1) - current;\n                }else {\n                    min = current - k + 1;\n                }\n                \n                // calculate max index\n                mCurrent = (n - 1) - current;\n                if (mCurrent < k - 1) {\n                    max = (k - 1) - mCurrent;\n                }else {\n                    max = mCurrent - k + 1;\n                }\n                max = (n - 1) - max;\n                \n                \n                // chose the correct parity set\n                set = min % 2 == 0 ? even : odd;\n                \n                key = set.ceiling(min);\n                \n                // add all values in range to the queue and remove from set\n                while (key != null && key <= max) {\n                    queue.add(key);\n                    set.remove(key);\n                    key = set.ceiling(min);\n                }\n            }\n            \n            ++moves;\n        }\n        \n        \n        return result;\n    }\n}\n```
['Array', 'Breadth-First Search', 'Ordered Set', 'Java']