[C++] beats 96.97% using KMP algorithm
This solution would be probably the best performing if we didn\'t know the queries beforehand, which we can sort beforehand by size and add only valid solutions
This solution would be probably the best performing if we didn\'t know the queries beforehand, which we can sort beforehand by size and add only valid solutions (by room size) in a set and search the closest ID in logN. Still it beats 96.97% of C++ online submissions. Why it is still good to know it? In an interview you could be asked the question slightly differently - you don\'t get the list of queries and you can\'t sort them beforehand. And the described alternative solution will quickly be unacceptable.\n\nIn this solution here, we sort the rooms by ID and search for the closest ID using binary search.\nIn order to get a room, which is big enough, we would need to search for the closest one to this ID from both sides. We can do this only in linear time, since we can\'t sort the rooms by size and ID at the same time...\nBut what we can do is utilize the principle used in the KPM algorithm (string search in O(N) - take a look on it for the interviews).\nHow does it work, we go through the rooms from left to right and for each room we save the index of the next room (on the left side), which has a greater size. The same we do for the opposite direction.\nIn this way, we can speed up our search process by skipping all the rooms in between, which have a smaller size. \nIn the concrete example, we will have to search on the left and on the right side and pick the closest room ID. Note that, if we didn\'t match the room ID initially with the binary search, we need to do the same for the idx on the left, since it is an alternative, which could result in a closer room ID.\n\n```\nclass Solution {\n    int closer(int target, int alt1, int alt2) {\n        if (alt1 == -1) return alt2;\n        if (alt2 == -1) return alt1;\n        if (abs(alt1 - target) < abs(alt2 - target)) return alt1;\n        if (abs(alt1 - target) == abs(alt2 - target) && alt1 < alt2) return alt1;\n        return alt2;\n    }    \npublic:\n    vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {       \n        sort(rooms.begin(), rooms.end(), [](const vector<int>& a, const vector<int>& b){\n            return (a[0] == b[0])? a[1] < b[1] : a[0] < b[0]; // sort by room ID, size if same\n        });\n        \n        // vector of indices with closest element by ID, which has a room\n        // size greater than this; if non-existing: -1 (from left and right)       \n        int n = rooms.size();\n        vector<int> left(n, -1), right(n, -1);\n\n        for (int i = 1; i < rooms.size(); ++i) { // look only at the left side\n            int idx = i - 1;\n            while (idx >= 0 && rooms[i][1] >= rooms[idx][1]) {\n                idx = left[idx];\n            }\n            left[i] = idx;\n        }\n\n        for (int i = rooms.size() - 2; i >= 0; --i) { // look only at the right side\n            int idx = i + 1;\n            while (idx >= 0 && idx < rooms.size() && \n                   rooms[i][1] >= rooms[idx][1]) {\n                idx = right[idx];\n            }\n            right[i] = idx;\n        }\n        \n        vector<int> ans;\n        for (auto& q: queries) {\n            auto it = lower_bound(rooms.begin(), rooms.end(), q[0], // compare by ID\n                                  [](const vector<int>& v, int value){\n                                      return v[0] < value;\n                                  });\n            \n            int idx = (it == rooms.end())? rooms.size() - 1 : distance(rooms.begin(), it);\n            int id = -1, i = idx;\n\n            for (i = idx; i >= 0 && rooms[i][1] < q[1]; i = left[i]);\n            if (i >= 0) id = closer(q[0], rooms[i][0], id);\n            \n            for (i = idx; i >= 0 && rooms[i][1] < q[1]; i = right[i]);\n            if (i >= 0) id = closer(q[0], rooms[i][0], id);\n\n            if (rooms[idx][0] > q[0]) {\n                for (i = idx - 1; i >= 0 && rooms[i][1] < q[1]; i = left[i]);\n                if (i >= 0) id = closer(q[0], rooms[i][0], id);\n\n                for (i = idx - 1; i >= 0 && rooms[i][1] < q[1]; i = right[i]);\n                if (i >= 0) id = closer(q[0], rooms[i][0], id);\n            }\n            \n            ans.push_back(id);\n        }\n        \n        return ans;\n    }\n};\n```
['Binary Tree', 'C++']