1847. Closest Room
Problem Description
This problem involves a hotel with n
unique rooms, each room represented by its room number and size. Given a list of k
queries, each including a preferred room number and a minimum room size, the task is to find the room that best matches the queries' criteria: the room size must be at least the minimum size given in the query, and the room number must be as close as possible to the preferred room number specified in the query. If two rooms are equally close to the preferred number, the room with the smaller number should be chosen. If no suitable room exists, the answer for that query is -1
. The goal is to return an array of answers for each of the k
queries based on these conditions.
Intuition
To approach this solution, sorting and binary search are key techniques. The fundamental idea is to first sort the rooms by size, which allows us to efficiently eliminate rooms that are too small for a given query. After filtering out the too-small rooms, we need a way to find the closest room number to the preferred one quickly. A binary search can help with this, and a data structure like a sorted list will allow us to use binary search effectively.
Here's the process we'll follow:
- Sort the rooms by size in non-decreasing order. This will help us later when we need to filter out rooms that are too small for a query and is the reason why rooms are processed starting with the largest size first.
- Create a sorted list of just the room numbers. This list will be dynamically updated as we iterate through the queries and remove rooms that don't meet the size requirement.
- Sort the queries by their minimum size in non-decreasing order and keep track of their original indices. Sorting the queries ensures we only have to remove rooms that are too small once for the smallest
minSize
rather than redoing it for each individual query. - Iterate through the sorted queries and perform the following steps:
- For a given query, remove rooms that are too small from the sorted list we created earlier. Once a room is removed for one query, there's no need to consider it for the later queries since we sorted the queries by minimum size already.
- Use binary search to find the room number closest to the preferred one. If it's a tie (equal distance to two room numbers), the binary search helps find the smaller room number.
- Store the result in the appropriate spot in the answer array by using the original index of the query.
This way, we are leveraging efficient sorting and searching algorithms to minimize both the time we spend on each query and the number of rooms we have to consider.
Learn more about Binary Search and Sorting patterns.
Solution Approach
In the provided solution, the implementation leverages Python's sorting capabilities, as well as the SortedList
data structure from the sortedcontainers
package, which maintains the elements in sorted order and supports efficient insertion and removal operations.
Here are the steps detailing the implementation:
-
Sorting the Rooms: The first step is to sort the list of rooms by their size. This is done with the help of a lambda function that serves as a key for the sorting algorithm. The rooms are sorted in ascending order based on size (
x[1]
being the size of the room).rooms.sort(key=lambda x: x[1])
-
Preparing for Queries: In preparation for processing the queries, the solution sorts the indices of the queries array based on the minimum size required for each query. This is so that we process queries with the smallest required sizes first.
idx = sorted(range(k), key=lambda i: queries[i][1])
-
Creating a Sorted List of Room Numbers: A
SortedList
is created consisting of all the room numbers from the sortedrooms
array. As the elements inSortedList
are kept in sorted order, it allows us to use efficient operations likebisect_left
, which is essentially a binary search to find the appropriate insertion point (or the closest element) for a given value.sl = SortedList(x[0] for x in rooms)
-
Processing the Queries: The
for
loop iterates over the queries sorted by size, for each query doing the following:-
Increasing Room Size Cut-off: Any rooms that are too small (
rooms[i][1] < minSize
) for the current query are removed from the sorted list. Increasing the indexi
as we go ensures that we never look back at the smaller rooms for future queries, as the queries themselves are sorted by size.while i < n and rooms[i][1] < minSize: sl.remove(rooms[i][0]) i += 1
-
Binary Search for Closest Room: Using
sl.bisect_left(prefer)
, we find the position where the preferred room number would be inserted into theSortedList
. We then use this position to find the closest room number that still meets the size requirements.p = sl.bisect_left(prefer)
-
Finding the Best Match: There are now two possibilities: the room number at position
p
and the room number immediately beforep
(ifp
is not the first element). Between these two, we choose the one that is closest to the preferred number (and if the distances are the same, the smaller room number is chosen). Ifp
is at the end of the sorted list, we only consider the room number beforep
.if p < len(sl): ans[j] = sl[p] if p and (ans[j] == -1 or ans[j] - prefer >= prefer - sl[p - 1]): ans[j] = sl[p - 1]
-
-
Formatting the Result: Finally, the answer for each query is stored in the
ans
array, which is returned at the end of the function.return ans
The use of a SortedList
for room numbers, sorted queries based on room size requirements, and binary search to find the closest room number are key features of this approach that make it efficient for processing multiple queries against a potentially large list of rooms.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach:
Assume we have the following hotel rooms and queries:
-
Hotel rooms:
- Room 101 with size 300
- Room 102 with size 200
- Room 103 with size 400
- Room 104 with size 500
-
Queries:
- Query 1: Prefer room 105, with minimum size 200
- Query 2: Prefer room 102, with minimum size 300
According to the solution approach, here's how this plays out:
-
Sorting the Rooms: The rooms are sorted by size:
Before sorting: [101, 300], [102, 200], [103, 400], [104, 500]
After sorting: [102, 200], [101, 300], [103, 400], [104, 500]
-
Preparing for Queries: We sort the queries by their minimum size requirement:
Before sorting: Query 1: [105, 200], Query 2: [102, 300]
After sorting: Query 1: [105, 200], Query 2: [102, 300]
-
Creating a Sorted List of Room Numbers: A
SortedList
is created with room numbers:SortedList
: [102, 101, 103, 104] -
Processing the Queries:
-
For Query 1 (prefer 105, min size 200):
- No rooms are too small, all room sizes are greater than 200.
- Perform binary search for the closest room to 105:
p
is assigned the position where 105 would be inserted, which is at the end of the list.- Since
p
equals the length of the list, we only consider the last room number beforep
, which is 104. - The best match for Query 1 is room 104.
-
Move to Query 2 (prefer 102, min size 300):
- Room 102 is removed because its size is less than 300.
- Updated
SortedList
: [101, 103, 104] - Perform binary search for the closest room to 102:
p
is the position where 102 would be inserted, which is at the start.- At
p
, the room number is 101. - Since
p
is not at the end, we consider the next room number (103) and compare distances. - Room 101 is closer to 102 than room 103, so the best match for Query 2 is room 101.
-
-
Formatting the Result:
- The answers array for the queries in their original order is [104, 101].
The above step-by-step process demonstrates how the solution filters out unsuitable rooms and efficiently arrives at the closest room number that satisfies each query's conditions.
Solution Implementation
1from sortedcontainers import SortedList
2from typing import List
3
4class Solution:
5 def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
6 # Sort rooms by size in ascending order
7 rooms.sort(key=lambda room: room[1])
8
9 num_queries = len(queries)
10 # Sorting indices of the queries by the size in ascending order
11 sorted_query_indices = sorted(range(num_queries), key=lambda i: queries[i][1])
12
13 # Initialize answer list with -1, assuming no valid room is found for the queries
14 answers = [-1] * num_queries
15
16 current_room_index = 0
17 num_rooms = len(rooms)
18
19 # Initializing a SortedList object to keep track of room IDs in sorted order
20 sorted_room_ids = SortedList(room[0] for room in rooms)
21
22 # Process the queries in the order of their size requirements
23 for query_index in sorted_query_indices:
24 preferred_id, min_size = queries[query_index]
25
26 # Remove rooms that are smaller than the minimum size from the sorted list
27 while current_room_index < num_rooms and rooms[current_room_index][1] < min_size:
28 sorted_room_ids.remove(rooms[current_room_index][0])
29 current_room_index += 1
30
31 # If all rooms are smaller than the minimum size, break
32 if current_room_index == num_rooms:
33 break
34
35 # Find the closest room ID that is equal or larger than the preferred ID
36 pos = sorted_room_ids.bisect_left(preferred_id)
37 # If such a room exists, set it as the answer for the current query
38 if pos < len(sorted_room_ids):
39 answers[query_index] = sorted_room_ids[pos]
40
41 # Check if the room before is actually closer to the preferred ID
42 # Update the answer for the current query if it is closer
43 if pos > 0 and (answers[query_index] == -1 or
44 answers[query_index] - preferred_id >= preferred_id - sorted_room_ids[pos - 1]):
45 answers[query_index] = sorted_room_ids[pos - 1]
46
47 # Return the list of closest room IDs for each query
48 return answers
49
1import java.util.Arrays;
2import java.util.TreeMap;
3
4class Solution {
5 public int[] closestRoom(int[][] rooms, int[][] queries) {
6 // Number of rooms
7 int numberOfRooms = rooms.length;
8 // Number of queries
9 int numberOfQueries = queries.length;
10
11 // Sort the rooms by size in ascending order
12 Arrays.sort(rooms, (a, b) -> a[1] - b[1]);
13
14 // Create an array of query indices
15 Integer[] queryIndices = new Integer[numberOfQueries];
16 for (int i = 0; i < numberOfQueries; i++) {
17 queryIndices[i] = i;
18 }
19
20 // Sort the query indices based on the room size preference from the queries in ascending order
21 Arrays.sort(queryIndices, (i, j) -> queries[i][1] - queries[j][1]);
22
23 // Room index for traversing the sorted rooms
24 int roomIndex = 0;
25 // TreeMap for keeping track of available rooms (key is room ID, value is a count which is not used here)
26 TreeMap<Integer, Integer> availableRooms = new TreeMap<>();
27 // Initialize the TreeMap with all rooms
28 for (int[] room : rooms) {
29 availableRooms.put(room[0], 1); // Since map value is not used, just set to 1
30 }
31
32 // Array for storing answers to the queries
33 int[] answers = new int[numberOfQueries];
34 // Initialize answers with -1 (which indicates no room found for the query)
35 Arrays.fill(answers, -1);
36
37 // Iterate through each query by sorted room size preference
38 for (int queryIndex : queryIndices) {
39 // Preferred room id and the minimum size required from the query
40 int preferredID = queries[queryIndex][0], minSize = queries[queryIndex][1];
41
42 // Remove rooms from the TreeMap that are smaller than the current query's minimum size requirement
43 while (roomIndex < numberOfRooms && rooms[roomIndex][1] < minSize) {
44 int roomId = rooms[roomIndex][0];
45 if (availableRooms.merge(roomId, -1, Integer::sum) == 0) {
46 availableRooms.remove(roomId);
47 }
48 ++roomIndex;
49 }
50
51 // If no rooms are available that satisfy the size constraint, move on to the next query
52 if (roomIndex == numberOfRooms) {
53 break;
54 }
55
56 // Find the closest room with at least the preferred room ID
57 Integer ceilingKey = availableRooms.ceilingKey(preferredID);
58 if (ceilingKey != null) {
59 answers[queryIndex] = ceilingKey;
60 }
61
62 // Find the closest room with no more than the preferred room ID
63 Integer floorKey = availableRooms.floorKey(preferredID);
64 if (floorKey != null && (answers[queryIndex] == -1 || answers[queryIndex] - preferredID >= preferredID - floorKey)) {
65 // Update the answer if floorKey is closer or equally close to preferred ID compared to ceilingKey
66 answers[queryIndex] = floorKey;
67 }
68 }
69 return answers;
70 }
71}
72
1#include <vector>
2#include <algorithm>
3#include <set>
4#include <numeric>
5
6using namespace std;
7
8class Solution {
9public:
10 vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
11 // Sort room based on their size in ascending order
12 sort(rooms.begin(), rooms.end(), [](const vector<int>& a, const vector<int>& b) {
13 return a[1] < b[1];
14 });
15
16 // Store the size of 'rooms' and 'queries' arrays
17 int numRooms = rooms.size();
18 int numQueries = queries.size();
19
20 // Create an index array for queries and fill it with ascending integers starting at 0
21 vector<int> queryIndices(numQueries);
22 iota(queryIndices.begin(), queryIndices.end(), 0);
23
24 // Sort the indices of 'queries' based on the room size requirement
25 sort(queryIndices.begin(), queryIndices.end(), [&](int i, int j) {
26 return queries[i][1] < queries[j][1];
27 });
28
29 // Initialize the answer vector with -1 indicating no room found
30 vector<int> answers(numQueries, -1);
31
32 // Multiset to store the ids of available rooms
33 multiset<int> availableRoomIds;
34 for (const auto& room : rooms) {
35 availableRoomIds.insert(room[0]);
36 }
37
38 // Keep track of the current position in the sorted 'rooms' array
39 int currentRoomIndex = 0;
40
41 // Iterate through the sorted query indices
42 for (int queryIndex : queryIndices) {
43 // Fetch the preferred room id and the required size from 'queries'
44 int preferredRoomId = queries[queryIndex][0];
45 int minSizeReq = queries[queryIndex][1];
46
47 // Remove rooms that are too small from our availableRoomIds
48 while (currentRoomIndex < numRooms && rooms[currentRoomIndex][1] < minSizeReq) {
49 availableRoomIds.erase(availableRoomIds.find(rooms[currentRoomIndex][0]));
50 ++currentRoomIndex;
51 }
52
53 // If all rooms have been checked, exit the loop
54 if (currentRoomIndex == numRooms) {
55 break;
56 }
57
58 // Find the first room id in the set that is not less than the preferred id
59 auto closestRoomIt = availableRoomIds.lower_bound(preferredRoomId);
60
61 // Check if there is an available room id greater or equal to the preferred id
62 if (closestRoomIt != availableRoomIds.end()) {
63 answers[queryIndex] = *closestRoomIt;
64 }
65
66 // Check for a closer room id that is less than the preferred id
67 if (closestRoomIt != availableRoomIds.begin()) {
68 auto prevRoomIt = prev(closestRoomIt); // Get iterator to the previous element
69 if (answers[queryIndex] == -1 ||
70 abs(*prevRoomIt - preferredRoomId) <= abs(answers[queryIndex] - preferredRoomId)) {
71 answers[queryIndex] = *prevRoomIt;
72 }
73 }
74 }
75 // Return the answers vector containing the id of the closest room for each query
76 return answers;
77 }
78};
79
1function closestRoom(rooms: number[][], queries: number[][]): number[] {
2 // Sort rooms based on their size in ascending order
3 rooms.sort((a, b) => a[1] - b[1]);
4
5 // Store the number of rooms and queries
6 const numRooms = rooms.length;
7 const numQueries = queries.length;
8
9 // Create an index array for queries with indices from 0 to numQueries-1
10 const queryIndices: number[] = Array.from(Array(numQueries).keys());
11
12 // Sort the indices of queries based on the room size requirement
13 queryIndices.sort((i, j) => queries[i][1] - queries[j][1]);
14
15 // Initialize the answers array with -1, indicating no room found
16 const answers: number[] = new Array(numQueries).fill(-1);
17
18 // Set to store the IDs of available rooms
19 const availableRoomIds: Set<number> = new Set(rooms.map(room => room[0]));
20
21 // Keep track of the current position in the sorted rooms array
22 let currentRoomIndex = 0;
23
24 // Iterate through the sorted query indices
25 for (const queryIndex of queryIndices) {
26 // Fetch the preferred room ID and the minimum required size
27 const [preferredRoomId, minSizeReq] = queries[queryIndex];
28
29 // Remove ineligible rooms that are too small
30 while (currentRoomIndex < numRooms && rooms[currentRoomIndex][1] < minSizeReq) {
31 availableRoomIds.delete(rooms[currentRoomIndex][0]);
32 currentRoomIndex++;
33 }
34
35 // Break early if all rooms have been checked
36 if (currentRoomIndex === numRooms) {
37 break;
38 }
39
40 // Array conversion for two-pointer technique since Sets do not have random access
41 const availableRoomIdsArray = Array.from(availableRoomIds);
42
43 // Find the closest room ID that is not less than the preferred ID
44 const insertIndex = sortedIndex(availableRoomIdsArray, preferredRoomId);
45
46 // Check if there's an available room ID greater or equal to the preferred ID
47 if (insertIndex < availableRoomIds.size) {
48 answers[queryIndex] = availableRoomIdsArray[insertIndex];
49 }
50
51 // Check for a closer room ID that is less than the preferred ID
52 if (insertIndex > 0) {
53 const previousRoomId = availableRoomIdsArray[insertIndex - 1];
54 if (
55 answers[queryIndex] === -1 ||
56 Math.abs(previousRoomId - preferredRoomId) <= Math.abs(answers[queryIndex] - preferredRoomId)
57 ) {
58 answers[queryIndex] = previousRoomId;
59 }
60 }
61 }
62
63 // Return the answers array containing the IDs of the closest room for each query
64 return answers;
65}
66
67// Helper function to return the index at which the `value` would be inserted into the `array`
68// ensuring ascending order. It uses binary search for efficiency.
69function sortedIndex(array: number[], value: number): number {
70 let low = 0,
71 high = array.length;
72
73 while (low < high) {
74 const mid = (low + high) >>> 1;
75 if (array[mid] < value) {
76 low = mid + 1;
77 } else {
78 high = mid;
79 }
80 }
81 return low;
82}
83
Time and Space Complexity
The code snippet above defines a class Solution
that contains a method closestRoom
used to find the closest room to the preferred room that also meets the minimum size requirement.
Time Complexity:
Let m
be the length of the rooms
list and n
be the length of the queries
list.
- Sorting the
rooms
list by size takesO(m log m)
. - Sorting the indices of the queries by the room size requirement takes
O(n log n)
. - The SortedList construction from all rooms involves adding each room once, which takes
O(m log m)
. - Iterating through
queries
indices (after sorting by size):- The while loop can, in the worst case, remove each room once (thus, it runs a total of
m
times over all iterations). Removal in a SortedList isO(log m)
, so the total cost of removals isO(m log m)
. - For each query, the
bisect_left
operation in the SortedList isO(log m)
, which is done at most once per query. - Accessing
len(sl)
isO(1)
. - The conditionals and value assignments are O(1).
- The while loop can, in the worst case, remove each room once (thus, it runs a total of
Combining these parts, we can estimate the overall worst-case time complexity as:
O(m log m) + O(n log n) + O(m log m) + n * O(log m)
= O(m log m) + O(n log n) + O(n log m)
= O((m + n) log m) + O(n log n)
Since m log m
can be larger than n log n
or vice versa depending on the input, we take the highest term:
= O(max(m, n) log m)
Note that when m
is much larger than n
, m log m
becomes the dominant term, and when n
is much larger, the two terms contribute significantly and the overall complexity could be approximated by adding both terms.
Space Complexity:
- We use additional memory for the sorted rooms, which is
O(m)
space. - The SortedList, which initially contains
m
ids, also usesO(m)
space. - The
ans
array is of sizen
, which usesO(n)
space.
Thus the total space complexity is:
O(m) + O(m) + O(n) = O(m + n)
This is because m
and n
are independent and could vary significantly.
Learn more about how to find time and space complexity quickly using problem constraints.
Is the following code DFS or BFS?
void search(Node root) { if (!root) return; visit(root); root.visited = true; for (Node node in root.adjacent) { if (!node.visited) { search(node); } } }
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!