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:
minSizej, andabs(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.length1 <= n <= 105k == queries.length1 <= k <= 1041 <= roomIdi, preferredj <= 1071 <= sizei, minSizej <= 107Problem Overview: You are given a list of rooms where each room has an id and size. For every query [preferredId, minSize], return the room whose size is at least minSize and whose ID is closest to preferredId. If two rooms are equally close, return the smaller ID. If none satisfy the size constraint, return -1.
Approach 1: Sorting and Two-pointer with Ordered Set (O((n + q) log n) time, O(n) space)
Sort rooms in descending order of size. Sort queries by minSize in descending order while keeping their original indices. Iterate through queries and gradually add valid rooms (whose size ≥ current query's minSize) into an ordered structure containing room IDs. This behaves like a two-pointer sweep: one pointer scans the sorted rooms while queries are processed from largest to smallest size requirement.
Use an ordered set (such as TreeSet or a balanced BST) to maintain room IDs. For each query, perform a floor and ceiling search around preferredId. Compare distances and choose the closest ID. Each insertion and lookup costs O(log n), so the overall complexity becomes O((n + q) log n) with O(n) extra space. This approach combines sorting with an ordered set to efficiently maintain candidate rooms.
Approach 2: Binary Search with Sorting (O((n + q) log n) time, O(n) space)
Start by sorting rooms by size in descending order and processing queries in the same order of decreasing minSize. Maintain a dynamically growing sorted list of valid room IDs. As you move through the rooms list, insert each qualifying room ID into this structure.
For every query, perform binary search on the sorted IDs to locate the insertion position of preferredId. The closest candidate must be either the element just before or just after that position. Compute the absolute difference for both candidates and pick the best match (prefer smaller ID on ties). Binary search keeps each query lookup at O(log n), while insertions also cost O(log n) depending on the container used.
Recommended for interviews: The sorting + ordered set sweep is the solution most interviewers expect. It demonstrates control over offline query processing, sorting strategies, and efficient nearest-neighbor search using balanced trees. A brute force scan would take O(nq) and fails at scale, but explaining it first shows you understand the constraints. The optimized solution shows strong command of array preprocessing and logarithmic search structures.
This approach focuses on sorting the rooms by size in descending order. For each query, we track the potential valid rooms that satisfy the minimum size condition using a two-pointer strategy along with a set data structure to efficiently find and sort room IDs based on the required distance.
We iterate over each query, updating the list of valid rooms, then determine the closest room ID using the sorted set.
The solution sorts the rooms based on size in descending order and processes each query in a similar fashion. It uses a SortedList to maintain a sorted list of room IDs that meet the size criteria for the current query. For each query, it represents the current valid rooms as sorted IDs to easily find those closest to the preferred room ID.
Time Complexity: O((n + k) log n). Sorting the rooms and queries each takes O(n log n) and O(k log k), respectively. Each query involves operations on a SortedList which are O(log n) on average.
Space Complexity: O(n), for storing room IDs in a sorted set.
This approach optimizes the search by employing binary search. First, the rooms are sorted based on size, and for each query, a binary search is conducted to filter eligible rooms that meet minSize. Subsequently, a linear scan finds the closest room ID.
This C++ implementation utilizes sorting for rooms and queries. Binary search with two-pointer navigation improves efficiency over a naive linear search. The use of a set keeps room IDs ordered, and lower_bound is used for proximity checks.
C++
JavaScript
Time Complexity: O((n + k) log n), where sorting and binary search operations predominate.
Space Complexity: O(n) for storing the current valid room IDs.
We notice that the order of queries does not affect the answer, and the problem involves the size relationship of room areas. Therefore, we can sort the queries in ascending order of minimum area, so that we can process each query from small to large. Also, we sort the rooms in ascending order of area.
Next, we create an ordered list and add all room numbers to the ordered list.
Then, we process each query from small to large. For each query, we first remove all rooms with an area less than or equal to the current query's minimum area from the ordered list. Then, in the remaining rooms, we use binary search to find the room number closest to the current query. If there is no such room, we return -1.
The time complexity is O(n times log n + k times log k), and the space complexity is O(n + k). Where n and k are the number of rooms and queries, respectively.
| Approach | Complexity |
|---|---|
| Sorting and Two-pointer Approach | Time Complexity: O((n + k) log n). Sorting the rooms and queries each takes O(n log n) and O(k log k), respectively. Each query involves operations on a SortedList which are O(log n) on average. |
| Binary Search with Sorting | Time Complexity: O((n + k) log n), where sorting and binary search operations predominate. |
| Offline Query + Ordered Set + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(nq) | O(1) | Small input sizes or when optimizing is unnecessary |
| Sorting + Ordered Set (Two-pointer sweep) | O((n + q) log n) | O(n) | Best general solution for large inputs and interview settings |
| Binary Search on Sorted IDs | O((n + q) log n) | O(n) | When using languages with built-in sorted containers or bisect utilities |
花花酱 LeetCode 1847. Closest Room - 刷题找工作 EP393 • Hua Hua • 3,080 views views
Watch 8 more video solutions →Practice Closest Room with our built-in code editor and test cases.
Practice on FleetCode