#1847

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Closest Room

Find the closest hotel room meeting minimum size requirements using binary search over the valid answer space efficiently.

array binary search sorting ordered set

Problem Statement

You are given a hotel with n rooms, each described by a unique room number and its size. The rooms are provided as an array rooms where rooms[i] = [roomIdi, sizei].

Given k queries, each query [preferredj, minSizej] asks for the room whose size is at least minSizej and whose room number is closest to preferredj. If multiple rooms are equally close, return the smallest room number. If no room satisfies the minimum size, return -1.

Examples

Example 1

Input: rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]

Output: [3,-1,3]

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]

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

Solution Approach

Sort rooms and queries

Sort rooms in descending order of size. Sort queries in descending order of minSize. This ensures that when processing queries, all rooms considered are eligible for the current minSize.

Use an ordered set for valid rooms

Maintain an ordered set of room numbers that meet the current query's minSize. Insert rooms while processing queries in order, enabling fast lookup for the closest room using binary search over the set.

Find closest room for each query

For each query, perform a binary search in the ordered set to find the room with the smallest absolute difference to preferredj. Return the smallest room number in case of a tie, or -1 if no valid room exists.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting rooms and queries takes O(n log n + k log k). Maintaining an ordered set allows O(log n) insertions and binary search for each query, resulting in overall O((n + k) log n) time. Space is O(n) for the ordered set.

What Interviewers Usually Probe

Consider sorting queries to optimize the closest room search for larger sizes.
Think about using a data structure supporting fast nearest neighbor queries.
Check tie-breaking rules carefully; returning the smallest room ID is required.

Common Pitfalls or Variants

Common pitfalls

Ignoring tie-breaking by smallest room number leads to wrong answers.
Processing queries without sorting can cause inefficient searches or incorrect eligibility.
Not maintaining a dynamic set of valid rooms causes missed or incorrect matches.

Follow-up variants

Find closest room but maximize room size instead of minimizing absolute difference.
Queries include a range of preferred rooms instead of a single preferred number.
Return multiple closest rooms when more than one satisfies the distance and size constraints.

FAQ

What is the best approach pattern for Closest Room?

Binary search over the valid answer space combined with sorting rooms and queries ensures fast nearest room lookup.

How do I handle multiple rooms equally close to the preferred room?

Always return the room with the smallest room number when absolute differences tie.

Can this approach handle large inputs efficiently?

Yes, sorting and maintaining an ordered set allow O((n + k) log n) performance suitable for n up to 10^5.

Why sort queries in descending minSize order?

Sorting allows incremental insertion of eligible rooms, ensuring only rooms meeting the current query's size are considered.

What data structure is ideal for finding the closest room quickly?

An ordered set or balanced BST enables efficient insertions and binary searches to find the closest room.

terminal

Solution

Solution 1: Offline Query + Ordered Set + Binary Search

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def closestRoom(
        self, rooms: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        rooms.sort(key=lambda x: x[1])
        k = len(queries)
        idx = sorted(range(k), key=lambda i: queries[i][1])
        ans = [-1] * k
        i, n = 0, len(rooms)
        sl = SortedList(x[0] for x in rooms)
        for j in idx:
            prefer, minSize = queries[j]
            while i < n and rooms[i][1] < minSize:
                sl.remove(rooms[i][0])
                i += 1
            if i == n:
                break
            p = sl.bisect_left(prefer)
            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]
        return ans

Continue Practicing

#1818 minimum absolute sum difference #2251 number of flowers in full bloom #2659 make array empty