BFS with a binary set (memory size reduction)
Intuition\n Describe your first thoughts on how to solve this problem. \n\nA BFS works best here, filling in the array one operation at a time. The important th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nA BFS works best here, filling in the array one operation at a time. The important thing, as noted by other solutions, is to keep track of which spaces are still open, so you can skip checking operations that are redundant.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nMany other solutions then use a `std::set` to keep track of which positions are still open. That method requires `n` nodes to be inserted at the beginning of the algorithm. Thus we know we will be allocating at least $$O(n)$$ memory. On the other hand, allocating a bit array, with each bit representing a number, is similarly $$O(n)$$, but much, much more compact. Moreover, finding or deleting entries in a bit array is constant with almost no overhead, unlike for `std::set`.\n\nTo iterate through this bit array, we craft a special function `find_next_bit_array` that takes advantage of C++20\'s new `<bit>` header to find the next marked bit in roughly constant time. \n\n# Complexity\n- Time complexity: $$O(n)$$-ish**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n** Okay technically `find_next_bit_array` is linear so the time complexity should be $$O(n^2)$$. However, its growth is rather slow,  and is proportional to the size of the gaps in the bit array rather than `n`. \n\n# Code\n```\nclass Solution {\npublic:\n    // Finds the position of the next filled bit on or after start\n    int find_next_bit_array(const int start, const int max, const std::vector<uint64_t> & src) {\n        int index = start / 64;\n        const uint64_t mask = (1ull << (start % 64)) - 1ull;\n        const uint64_t next_bit = src[index] & ~mask;\n        if (next_bit != 0) {\n            const int result = index * 64 + std::countr_zero(next_bit);\n            return std::min(max, result);\n        }\n        while ((++index) * 64 < max) {\n            if (src[index] != 0) {\n                const int result = index * 64 + std::countr_zero(src[index]);\n                return std::min(max, result);\n            }\n        }\n        return max;\n    }\n\n    std::vector<int> minReverseOperations(const int n, const int p, const std::vector<int> & banned, const int k) {\n        std::vector<int> result;\n        result.resize(n, -1);\n        result[p] = 0;\n        if (k == 1) return result;\n        // Seperate out the even and odd valid positions\n        std::array<std::vector<uint64_t>, 2> valid_positions;\n        const int even_word_count = ((n / 2) + 63) / 64, // Round up\n            odd_word_count = (((n + 1) / 2) + 63) / 64;\n        valid_positions[0].resize(even_word_count, ~0ull);\n        valid_positions[1].resize(odd_word_count, ~0ull);\n        // These operations remove the undesired bits\n        valid_positions[p % 2][p / 128] &= ~(1ull << ((p / 2) % 64));\n        for (const auto i : banned) {\n            valid_positions[i % 2][i / 128] &= ~(1ull << ((i / 2) % 64));\n        }\n        std::queue<int> index_queue;\n        index_queue.push(p);\n        for (; !index_queue.empty(); ) {\n            const int index = index_queue.front();\n            index_queue.pop();\n            const int iteration = result[index];\n            const int is_odd = (index + k - 1) % 2;\n            const int start = std::max(index - k + 1, k - index - 1) / 2;\n            const int end = std::min(index + k + 1, 2 * n - index - k + 1) / 2;\n            int it = find_next_bit_array(start, end, valid_positions[is_odd]);\n            for (; it < end; it = find_next_bit_array(it + 1, end, valid_positions[is_odd])) {\n                const int real_index = 2 * it + is_odd;\n                result[real_index] = iteration + 1;\n                index_queue.push(real_index);\n                // It is important to remove the index that was just set\n                valid_positions[is_odd][it / 64] &= ~(1ull << (it % 64));\n            }\n        }\n        return result;\n    }\n};\n```
['Bit Manipulation', 'Breadth-First Search', 'C++']