In this guide, you will get 1847. Closest Room LeetCode Solution with the best time and space complexity. The solution to Closest Room problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
There is a hotel with n rooms. The rooms are represented by a 2D integer array rooms where rooms[i] = [roomIdi, sizei] denotes that there is a room with room number roomIdi and size equal to sizei. Each roomIdi is guaranteed to be unique.
You are also given k queries in a 2D array queries where queries[j] = [preferredj, minSizej]. The answer to the jth query is the room number id of a room such that:
The room has a size of at least minSizej, and
abs(id – preferredj) is minimized, where abs(x) is the absolute value of x.
If there is a tie in the absolute difference, then use the room with the smallest such id. If there is no such room, the answer is -1.
Return an array answer of length k where answer[j] contains the answer to the jth query.
Example 1:
Input: rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]
Output: [3,-1,3]
Explanation: The answers to the queries are as follows:
Query = [3,1]: Room number 3 is the closest as abs(3 – 3) = 0, and its size of 2 is at least 1. The answer is 3.
Query = [3,3]: There are no rooms with a size of at least 3, so the answer is -1.
Query = [5,2]: Room number 3 is the closest as abs(3 – 5) = 2, and its size of 2 is at least 2. The answer is 3.
Example 2:
Input: rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]
Output: [2,1,3]
Explanation: The answers to the queries are as follows:
Query = [2,3]: Room number 2 is the closest as abs(2 – 2) = 0, and its size of 3 is at least 3. The answer is 2.
Query = [2,4]: Room numbers 1 and 3 both have sizes of at least 4. The answer is 1 since it is smaller.
Query = [2,5]: Room number 3 is the only room with a size of at least 5. The answer is 3.
Constraints:
n == rooms.length
1 <= n <= 105
k == queries.length
1 <= k <= 104
1 <= roomIdi, preferredj <= 107
1 <= sizei, minSizej <= 107
Complexity Analysis
Time Complexity: O(\texttt{sort}(n) + \texttt{sort}(q) + q\log n)
Space Complexity: O(n + q)
1847. Closest Room LeetCode Solution in C++
class Solution {
public:
vector<int> closestRoom(vector<vector<int>>& rooms,
vector<vector<int>>& queries) {
vector<int> ans(queries.size());
set<int> roomIds;
for (int i = 0; i < queries.size(); ++i)
queries[i].push_back(i);
auto descSize = auto& a, const auto& b) {
return a[1] > b[1];
};
ranges::sort(rooms, descSize);
ranges::sort(queries, descSize);
int i = 0; // rooms' index
for (const vector<int>& query : queries) {
while (i < rooms.size() && rooms[i][1] >= query[1])
roomIds.insert(rooms[i++][0]);
ans[query[2]] = searchClosestRoomId(roomIds, query[0]);
}
return ans;
}
private:
int searchClosestRoomId(set<int>& roomIds, int preferred) {
const auto it = roomIds.lower_bound(preferred);
const int id1 = it == roomIds.cbegin() ? -1 : *(prev(it));
const int id2 = it == roomIds.cend() ? -1 : *it;
if (id1 == -1)
return id2;
if (id2 == -1)
return id1;
if (abs(preferred - id1) <= abs(preferred - id2))
return id1;
return id2;
}
}; /* code provided by PROGIEZ */
1847. Closest Room LeetCode Solution in Java
class Solution {
public int[] closestRoom(int[][] rooms, int[][] queries) {
int[] ans = new int[queries.length];
Integer[] indices = new Integer[queries.length];
TreeSet<Integer> roomIds = new TreeSet<>();
for (int i = 0; i < queries.length; ++i)
indices[i] = i;
Arrays.sort(rooms, (a, b) -> Integer.compare(b[1], a[1]));
Arrays.sort(indices, (a, b) -> Integer.compare(queries[b][1], queries[a][1]));
int i = 0; // rooms' index
for (final int index : indices) {
while (i < rooms.length && rooms[i][1] >= queries[index][1])
roomIds.add(rooms[i++][0]);
ans[index] = searchClosestRoomId(roomIds, queries[index][0]);
}
return ans;
}
private int searchClosestRoomId(TreeSet<Integer> roomIds, int preferred) {
Integer floor = roomIds.floor(preferred);
Integer ceiling = roomIds.ceiling(preferred);
final int id1 = floor == null ? -1 : floor;
final int id2 = ceiling == null ? -1 : ceiling;
if (id1 == -1)
return id2;
if (id2 == -1)
return id1;
if (Math.abs(preferred - id1) <= Math.abs(preferred - id2))
return id1;
return id2;
}
} // code provided by PROGIEZ
1847. Closest Room LeetCode Solution in Python
from sortedcontainers import SortedList
class Solution:
def closestRoom(
self,
rooms: list[list[int]],
queries: list[list[int]],
) -> list[int]:
ans = [0] * len(queries)
qs = [[*q, i] for i, q in enumerate(queries)]
roomIds = SortedList()
rooms.sort(key=lambda x: -x[1])
qs.sort(key=lambda x: -x[1])
def searchClosestRoomId(roomIds: SortedList, preferred: int):
if not roomIds:
return -1
candIds = []
i = roomIds.bisect_right(preferred)
if i > 0:
candIds.append(roomIds[i - 1])
if i < len(roomIds):
candIds.append(roomIds[i])
return min(candIds, key=lambda x: abs(x - preferred))
i = 0 # rooms' index
for preferred, minSize, index in qs:
while i < len(rooms) and rooms[i][1] >= minSize:
roomIds.add(rooms[i][0])
i += 1
ans[index] = searchClosestRoomId(roomIds, preferred)
return ans # code by PROGIEZ
