Closest Room: Offline Queries with Sorted Set

Closest Room is LeetCode 1847, and it is one of the best problems for learning how to combine offline query processing with a sorted set. You have a list of hotel rooms, each with an id and a size. You receive queries asking for the room id closest to a preferred value, but only among rooms that meet a minimum size requirement. The naive approach checks every room for every query. The efficient approach processes queries in a clever order so that you only need a single binary search per query.

Why this problem matters

This problem teaches a general pattern: when queries have filters that can be ordered, process them offline so you can incrementally build your search structure. You will see this same idea in problems involving thresholds, deadlines, and capacity constraints. The combination of sorting, incremental insertion, and binary search is a toolkit that transfers directly to many interview and contest problems.

The key insight

If you sort queries by minSize in descending order and sort rooms by size in descending order, you can process queries from strictest to most lenient. As you move to the next query (with a smaller or equal minSize), you add any newly eligible rooms to a sorted set. Since rooms only get added and never removed, the sorted set grows monotonically. For each query, you binary search the sorted set for the closest room id to the preferred value.

This avoids recomputing which rooms are eligible for each query. Every room gets inserted into the sorted set exactly once across all queries.

The solution

from sortedcontainers import SortedList

def closestRoom(rooms, queries):
    rooms.sort(key=lambda r: -r[1])
    indexed_queries = sorted(enumerate(queries), key=lambda q: -q[1][1])

    result = [-1] * len(queries)
    sl = SortedList()
    j = 0

    for qi, (preferred, minSize) in indexed_queries:
        while j < len(rooms) and rooms[j][1] >= minSize:
            sl.add(rooms[j][0])
            j += 1

        if not sl:
            result[qi] = -1
            continue

        idx = sl.bisect_left(preferred)
        best = -1
        best_diff = float('inf')

        if idx < len(sl):
            diff = sl[idx] - preferred
            if diff < best_diff or (diff == best_diff and sl[idx] < best):
                best = sl[idx]
                best_diff = diff

        if idx > 0:
            diff = preferred - sl[idx - 1]
            if diff < best_diff or (diff == best_diff and sl[idx - 1] < best):
                best = sl[idx - 1]
                best_diff = diff

        result[qi] = best

    return result

The code sorts rooms by size descending and queries by minSize descending. It walks through queries in that order, adding eligible rooms to a SortedList. For each query, it uses bisect_left to find where the preferred id would land in the sorted set, then checks the neighbor on each side to find the closest id. Ties are broken by choosing the smaller room id.

The pointer j only moves forward across all queries. Each room is inserted into the sorted set exactly once. The bisect_left call runs in O(log n) time, and checking the two neighbors is O(1).

Visual walkthrough

Complexity analysis

Sorting rooms takes O(n log n). Sorting queries takes O(q log q). Each room is inserted into the sorted set once, and each insertion is O(log n), giving O(n log n) total. Each query does one binary search in O(log n). The overall time is O((n + q) log n). Space is O(n) for the sorted set plus O(q) for the result array.

The building blocks

1. Offline query processing

When queries have a threshold or filter parameter, sorting queries by that parameter lets you build your data structure incrementally. Instead of rebuilding for each query, you add elements as they become relevant. This turns a potentially O(n * q) approach into something much faster.

The key requirement is that queries are independent, so answering them out of order does not change the results. You just need to map answers back to the original query indices.

2. Binary search in a sorted set

Once you have a collection of valid room ids in a sorted structure, finding the closest one to a target is a binary search problem. You find the insertion point, then compare the neighbors on both sides. The closest value is one of at most two candidates: the largest value < the target, or the smallest value >= the target.

In Python, SortedList from sortedcontainers gives you O(log n) insertion and O(log n) bisect. In C++ or Java, you would use std::set with lower_bound or TreeSet with floor and ceiling.

Edge cases

• No room meets the size requirement: the sorted set is empty for that query. Return -1.
• Preferred id is an exact match: bisect_left lands directly on it. Difference is 0, so that room wins.
• Preferred id is larger than all room ids: only the left neighbor exists. Return the largest room id in the set.
• Preferred id is smaller than all room ids: only the right neighbor exists. Return the smallest room id in the set.
• Tie in distance: two rooms are equidistant from the preferred id. Return the one with the smaller room id.
• Single room, single query: the logic still works. The sorted set has one element, and you compare it directly.
• All queries have the same minSize: all rooms are added before the first query. Each query is just a binary search.

From understanding to recall

The algorithm has three moving parts: sorting rooms, sorting queries, and binary searching a growing sorted set. You probably follow the logic after one read. But try to write it from scratch in a week. Did you sort rooms ascending or descending? Did you use bisect_left or bisect_right? Do you check idx and idx - 1, or idx and idx + 1? These details matter, and they are exactly the kind of thing that slips under time pressure.

Spaced repetition locks it in. You write the solution today, again tomorrow, then in three days. By the fourth time, the offline processing pattern and the two-neighbor binary search check are automatic. You do not need to re-derive the approach. You just write it.

Related posts

• Find First and Last Position of Element in Sorted Array - Binary search to find boundaries in a sorted collection
• Kth Smallest Element in a Sorted Matrix - Combining sorting with targeted search
• Search a 2D Matrix - Binary search on structured data with multiple dimensions

Understanding algorithms is the first step. Retaining them is what makes the difference in interviews. CodeBricks uses spaced repetition to help you practice problems like Closest Room until the patterns are second nature, not something you have to re-learn each time.