C++ fast BFS solution, beats 100%
Approach\nIn this problem, vanilla BFS would be O(n^2). Taking advantage of the fact that the range of neighbors of adjacent nodes mostly overlap, we can keep t
# Approach\nIn this problem, vanilla BFS would be $$O(n^2)$$. Taking advantage of the fact that the range of neighbors of adjacent nodes mostly overlap, we can keep track of the ones already processed and avoid repeatedly processing them.\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(n)$$\n\nRuntime: 221 ms (currently beats 100%)\nMemory Usage: 99.9 MB (currently beats 100%)\nhttps://leetcode.com/submissions/detail/926416250/\n\n# Code\n```\nclass Solution {\npublic:\n    vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {\n        vector<int> distances(n, INT_MAX);\n        for (int x: banned) {\n            distances[x] = -1;\n        }\n        \n        vector<int> nodes, new_nodes;\n        distances[p] = 0;\n        nodes.push_back(p);\n        \n        while (nodes.size()) {\n            int i_min = INT_MAX;\n            int i_max = INT_MIN;\n            \n            for (int node: nodes) {\n                int base = node - k + 1;\n                \n                // j: segment start position\n                // i: update position\n                auto j2i = [=](int j) {\n                    return base + (j - base) * 2;\n                };\n                \n                auto update = [&](int i) {\n                    if (distances[i] == INT_MAX) {\n                        distances[i] = distances[node] + 1;\n                        new_nodes.push_back(i);\n                    }\n                };\n                \n                // inclusive\n                int lo = j2i(max(0, base));\n                int hi = j2i(min(node + k, n) - k);\n                for (int i = lo; i <= min(hi, i_min-2); i += 2) update(i);\n                for (int i = max(lo, i_max+2); i <= hi; i += 2) update(i);\n                i_min = min(i_min, lo);\n                i_max = max(i_max, hi);\n            }\n            \n            swap(nodes, new_nodes);\n            new_nodes.clear();\n        }\n        \n        for (int &x: distances) {\n            if (x == INT_MAX) x = -1;\n        }\n        return distances;\n    }\n};\n```
['C++']