Watch 9 video solutions for Closest Room, a hard level problem involving Array, Binary Search, Sorting. This walkthrough by Hua Hua has 3,080 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |