Difficulty: 🔴 Hard
Topics: Array, Binary Search, Sorting, Ordered Set

Solution

LeetCode 1847: Closest Room

Problem Understanding

We are given a list of hotel rooms, where each room has:

Problem Understanding

The problem gives us a collection of hotel rooms, where each room has two attributes:

A unique room ID
A room size

We are also given several queries. Each query contains:

preferred: the room ID we would like to stay in
minSize: the minimum acceptable room size

For each query, we must choose a room satisfying the size requirement:

room.size >= minSize

Among all valid rooms, we want the room whose ID is closest to preferred.

In other words, we minimize:

$$|roomId - preferred|$$

If multiple rooms have the same minimum distance, we choose the smaller room ID.

If no room satisfies the minimum size requirement, the answer is -1.

Example Interpretation

Suppose the valid room IDs are:

1, 5, 9

and:

preferred = 6

The distances are:

|1 - 6| = 5
|5 - 6| = 1
|9 - 6| = 3

The closest room is 5.

If the valid room IDs were:

4, 8

and:

preferred = 6

then:

|4 - 6| = 2
|8 - 6| = 2

Both are equally close, so we choose the smaller ID, which is 4.

What the Constraints Tell Us

Up to 10^5 rooms.
Up to 10^4 queries.
Room IDs and sizes can be as large as 10^7.

A brute-force solution that scans all rooms for every query would require:

$$O(nk)$$

operations.

In the worst case:

$$10^5 \times 10^4 = 10^9$$

which is far too slow.

Therefore we need an approach closer to:

$$O((n+k)\log n)$$

or similar.

Important Edge Cases

A few situations require special handling:

No room satisfies the minimum size requirement.
Only one valid room exists.
The preferred room ID itself exists and is valid.
Two candidate rooms are equally distant from the preferred ID.
All rooms satisfy the query.
Room IDs are not sorted.
Multiple queries have different minimum size requirements.

The uniqueness of room IDs guarantees that we never need to deal with duplicate IDs.

Approaches

Brute Force

For each query:

Iterate through every room.
Ignore rooms whose size is smaller than minSize.
Compute the distance to preferred.
Keep track of the best room seen so far.
Apply the tie-breaking rule when distances are equal.

This is correct because every valid room is examined.

However, for every query we scan all rooms.

Time complexity:

$$O(nk)$$

which is too slow for the given limits.

Key Insight

The difficult part is the minimum size constraint.

Suppose we process queries in descending order of minSize.

At the same time, sort rooms in descending order of room size.

When handling a query requiring size S, we can insert into a data structure all rooms whose size is at least S.

Because queries are processed from larger size requirements to smaller ones, once a room becomes eligible it remains eligible for all later queries.

This transforms the problem into:

Given a dynamically growing set of valid room IDs, find the ID closest to preferred.

If the room IDs are maintained in sorted order, we only need to examine:

The first ID greater than or equal to preferred
The ID immediately before it

These are the only candidates that can possibly be closest.

An ordered set with binary search supports exactly this operation.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nk)	O(1)	Scan all rooms for every query
Optimal	O((n + k) log n)	O(n)	Offline processing with ordered room IDs

Algorithm Walkthrough

Sort rooms in descending order by room size.
For each query, store:

preferred ID
minimum size
original query index

Sort queries in descending order by minSize.
Maintain a sorted collection of room IDs that currently satisfy the size requirement.
Use a pointer into the sorted room list.
Process queries from largest minSize to smallest.
For the current query, insert every room whose size is at least the query's minSize into the sorted collection.
If the collection is empty, answer -1.
Otherwise perform binary search for preferred.
Let:

right be the first room ID greater than or equal to preferred
left be the room ID immediately before right

Compare the distances from preferred.
If distances are equal, choose the smaller room ID.
Store the result using the query's original index.
Continue until all queries have been processed.
Return the answer array.

Why it Works

When processing a query with minimum size S, every room currently stored has size at least S, and every room not stored has size less than S.

Therefore the data structure contains exactly the valid rooms for that query.

Since the room IDs are sorted, the closest room to preferred must be either:

The predecessor of preferred
The successor of preferred

Any room farther left than the predecessor or farther right than the successor must have a larger distance.

Therefore examining only these two candidates always produces the correct answer. We are also given multiple queries. Each query contains:

A preferred room ID
A minimum required room size

For every query, we must find a room that satisfies the minimum size requirement and is closest to the preferred room ID.

The closeness is determined by:

abs(roomID - preferred)

Among all valid rooms, we choose the one with the smallest absolute difference. If multiple rooms have the same distance, we choose the smaller room ID.

If no room satisfies the minimum size requirement, the answer is -1.

The important detail is that the room IDs are not sequential and can be as large as 10^7. We cannot use arrays indexed by room ID. The constraints are also large:

Up to 10^5 rooms
Up to 10^4 queries

A naive approach that checks every room for every query would require up to:

10^5 * 10^4 = 10^9

operations, which is far too slow.

Another important observation is that the query condition has two independent parts:

Size filtering
Closest ID search

The challenge is efficiently maintaining the set of rooms that satisfy the current minimum size constraint while also being able to quickly find the nearest room ID.

Several edge cases matter here:

No room satisfies the minimum size
Multiple rooms are equally close to the preferred ID
The preferred ID itself may exist
Queries may ask for very large minimum sizes
Room IDs are sparse and unordered

The problem guarantees that room IDs are unique, which simplifies ordered lookups.

Approaches

Brute Force Approach

The most straightforward solution is to process each query independently.

For every query:

Iterate through all rooms
Keep only rooms whose size is at least minSize
Compute the absolute distance from the preferred room ID
Track the best candidate
Apply the tie-breaking rule by choosing the smaller room ID

This approach is correct because it explicitly checks every possible valid room and selects the optimal one according to the problem rules.

However, its performance is unacceptable for the given constraints. If we have k queries and n rooms, the total complexity becomes:

O(n * k)

With n = 10^5 and k = 10^4, this becomes too large.

Optimal Approach

The key insight is that queries with larger minimum size requirements form subsets of queries with smaller requirements.

Suppose we sort:

Rooms by size in descending order
Queries by minimum size in descending order

Then, while processing queries from largest minSize to smallest, we can incrementally add rooms that satisfy the current threshold.

At any moment, we maintain a data structure containing exactly the room IDs whose sizes are large enough for the current query.

Now the problem becomes:

Given a sorted set of room IDs, find the closest value to a target.

This can be solved efficiently using binary search.

The optimal strategy therefore combines:

Offline query processing
Sorting
Binary search on ordered room IDs

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nk)	O(1)	Checks every room for every query
Optimal	O((n + k) log n)	O(n)	Sort rooms and queries, then use binary search on valid room IDs

Algorithm Walkthrough

Sort all rooms in descending order of room size.

This allows us to process large rooms first. As query requirements become less strict, more rooms become eligible. 2. Attach original indices to queries and sort queries by minSize in descending order.

Since sorting changes the order of queries, we must remember each query's original position so we can place answers correctly in the result array. 3. Maintain a sorted list of valid room IDs.

As we process queries, we insert rooms whose size is large enough for the current query. 4. Use a pointer over the sorted rooms array.

For each query:

While the current room's size is at least the query's minSize
Insert its room ID into the sorted structure
Advance the pointer

This guarantees that the data structure always contains exactly the rooms valid for the current query. 5. Perform binary search to find the closest room ID.

Since room IDs are stored in sorted order:

Use binary search to find the insertion position of preferred
Check the candidate at that position
Check the candidate immediately before it

These are the only possible closest rooms. 6. Apply tie-breaking rules.

If two candidates have equal distance:

Choose the smaller room ID

Store the answer in the original query position.

Since queries were sorted earlier, we use the saved index to reconstruct the final output order.

Why it works

The algorithm maintains an important invariant:

Before processing a query with minimum size m, the ordered structure contains all and only rooms whose size is at least m.

Because queries are processed in descending order of minSize, rooms only need to be inserted once.

Binary search guarantees we examine the nearest room IDs around the preferred value. Since the room IDs are sorted, the closest valid room must be one of the immediate neighbors around the insertion point.

Therefore, every query is answered correctly.

Python Solution

from typing import List
from sortedcontainers import SortedList

class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        rooms.sort(key=lambda x: -x[1])

        indexed_queries = [
            (min_size, preferred, idx)
            for idx, (preferred, min_size) in enumerate(queries)
        ]
        indexed_queries.sort(reverse=True)

        room_ids = SortedList()
        answers = [-1] * len(queries)

        room_idx = 0
        n = len(rooms)

        for min_size, preferred, query_idx in indexed_queries:
            while room_idx < n and rooms[room_idx][1] >= min_size:
                room_ids.add(rooms[room_idx][0])
                room_idx += 1

            if not room_ids:
                continue

            pos = room_ids.bisect_left(preferred)

            best_room = -1
            best_dist = float("inf")

            if pos < len(room_ids):
                candidate = room_ids[pos]
                best_room = candidate
                best_dist = abs(candidate - preferred)

            if pos > 0:
                candidate = room_ids[pos - 1]
                dist = abs(candidate - preferred)

                if (
                    dist < best_dist
                    or (dist == best_dist and candidate < best_room)
                ):
                    best_room = candidate
                    best_dist = dist

            answers[query_idx] = best_room
from bisect import bisect_left, insort
from typing import List

class Solution:
    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:
        # Sort rooms by size descending
        rooms.sort(key=lambda x: -x[1])

        # Add original indices to queries
        indexed_queries = [
            (preferred, min_size, index)
            for index, (preferred, min_size) in enumerate(queries)
        ]

        # Sort queries by min_size descending
        indexed_queries.sort(key=lambda x: -x[1])

        answers = [-1] * len(queries)

        valid_room_ids = []
        room_pointer = 0

        for preferred, min_size, query_index in indexed_queries:

            # Add all rooms that satisfy the size requirement
            while (
                room_pointer < len(rooms)
                and rooms[room_pointer][1] >= min_size
            ):
                room_id = rooms[room_pointer][0]
                insort(valid_room_ids, room_id)
                room_pointer += 1

            # No valid rooms
            if not valid_room_ids:
                continue

            # Find insertion position
            position = bisect_left(valid_room_ids, preferred)

            best_room = -1
            best_distance = float("inf")

            # Check right candidate
            if position < len(valid_room_ids):
                candidate = valid_room_ids[position]
                distance = abs(candidate - preferred)

                if (
                    distance < best_distance
                    or (
                        distance == best_distance
                        and candidate < best_room
                    )
                ):
                    best_room = candidate
                    best_distance = distance

            # Check left candidate
            if position > 0:
                candidate = valid_room_ids[position - 1]
                distance = abs(candidate - preferred)

                if (
                    distance < best_distance
                    or (
                        distance == best_distance
                        and candidate < best_room
                    )
                ):
                    best_room = candidate
                    best_distance = distance

            answers[query_index] = best_room

        return answers

Implementation Explanation

The rooms are sorted by size in descending order so that larger rooms are processed first.

Queries are also sorted by their minimum size requirement. This allows us to add rooms incrementally. The variable room_idx tracks which rooms have already been inserted into the ordered set.

SortedList maintains room IDs in sorted order and supports:

Insertion in O(log n)
Binary search in O(log n)

For each query, binary search locates the insertion position of preferred.

The room at that position is the successor candidate.

The room immediately before it is the predecessor candidate.

The closer of the two is selected, with the smaller ID winning ties.

Finally, results are written back to their original query positions. The implementation begins by sorting rooms in descending order of size. This ensures that as queries become less restrictive, we can continuously add more valid rooms without removing any.

The queries are augmented with their original indices before sorting. This is necessary because the output must preserve the original query order.

The valid_room_ids list maintains all currently eligible room IDs in sorted order. Python's bisect module allows efficient binary searches to locate the closest room to the preferred ID.

For each query, rooms are added until all rooms satisfying the current minimum size are included. Since both rooms and queries are sorted descending by size, each room is inserted exactly once.

After the valid room IDs are prepared, binary search finds where the preferred room ID would be inserted. The closest valid room must be either:

The first room greater than or equal to the preferred ID
The room immediately smaller than the preferred ID

The implementation checks both candidates and applies the tie-breaking rule correctly.

Go Solution

package main

import (
	"sort"

	"github.com/emirpasic/gods/trees/redblacktree"
)

func closestRoom(rooms [][]int, queries [][]int) []int {
	n := len(rooms)

	"math"
	"sort"
)

func closestRoom(rooms [][]int, queries [][]int) []int {
	sort.Slice(rooms, func(i, j int) bool {
		return rooms[i][1] > rooms[j][1]
	})

	type Query struct {
		minSize  int
		preferred int
		index    int
	}

	qs := make([]Query, len(queries))

	for i, q := range queries {
		qs[i] = Query{
			minSize:  q[1],
			preferred: q[0],
			index:    i,
		}
	}

	sort.Slice(qs, func(i, j int) bool {
		return qs[i].minSize > qs[j].minSize
	})

	ans := make([]int, len(queries))

	tree := redblacktree.NewWithIntComparator()

	roomIdx := 0

	for _, q := range qs {
		for roomIdx < n && rooms[roomIdx][1] >= q.minSize {
			tree.Put(rooms[roomIdx][0], nil)
			roomIdx++
		}

		if tree.Size() == 0 {
			ans[q.index] = -1
			continue
		}

		bestRoom := -1
		bestDist := int(^uint(0) >> 1)

		if node, found := tree.Ceiling(q.preferred); found {
			id := node.Key.(int)
			bestRoom = id
			bestDist = abs(id - q.preferred)
		}

		if node, found := tree.Floor(q.preferred); found {
			id := node.Key.(int)
			dist := abs(id - q.preferred)

			if dist < bestDist || (dist == bestDist && id < bestRoom) {
				bestRoom = id
				bestDist = dist
			}
		}

		ans[q.index] = bestRoom
	}

	return ans
		preferred int
		minSize  int
		index     int
	}

	indexedQueries := make([]Query, len(queries))

	for i, q := range queries {
		indexedQueries[i] = Query{
			preferred: q[0],
			minSize:  q[1],
			index:     i,
		}
	}

	sort.Slice(indexedQueries, func(i, j int) bool {
		return indexedQueries[i].minSize > indexedQueries[j].minSize
	})

	answers := make([]int, len(queries))

	for i := range answers {
		answers[i] = -1
	}

	validRoomIDs := []int{}
	roomPointer := 0

	for _, query := range indexedQueries {

		for roomPointer < len(rooms) &&
			rooms[roomPointer][1] >= query.minSize {

			roomID := rooms[roomPointer][0]

			position := sort.SearchInts(validRoomIDs, roomID)

			validRoomIDs = append(validRoomIDs, 0)

			copy(
				validRoomIDs[position+1:],
				validRoomIDs[position:],
			)

			validRoomIDs[position] = roomID

			roomPointer++
		}

		if len(validRoomIDs) == 0 {
			continue
		}

		position := sort.SearchInts(
			validRoomIDs,
			query.preferred,
		)

		bestRoom := -1
		bestDistance := math.MaxInt32

		if position < len(validRoomIDs) {
			candidate := validRoomIDs[position]
			distance := abs(candidate - query.preferred)

			if distance < bestDistance ||
				(distance == bestDistance &&
					candidate < bestRoom) {

				bestRoom = candidate
				bestDistance = distance
			}
		}

		if position > 0 {
			candidate := validRoomIDs[position-1]
			distance := abs(candidate - query.preferred)

			if distance < bestDistance ||
				(distance == bestDistance &&
					candidate < bestRoom) {

				bestRoom = candidate
				bestDistance = distance
			}
		}

		answers[query.index] = bestRoom
	}

	return answers
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

Go-Specific Notes

The algorithm is identical to the Python version.

A balanced binary search tree is used to support:

Insertion of room IDs
Floor queries
Ceiling queries

Both operations run in O(log n) time.

The logic for choosing between predecessor and successor remains unchanged. The Go implementation follows the same algorithmic structure as the Python solution.

One important difference is that Go does not provide a built-in ordered multiset structure. To maintain sorted room IDs, the implementation manually inserts elements into the correct position using sort.SearchInts and slice shifting with copy.

Unlike Python, Go requires explicit struct definitions for the query metadata.

The algorithm still guarantees that every room is inserted exactly once and every query performs only logarithmic binary searches.

Worked Examples

Example 1

Input:

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

After sorting rooms:

Step 1: Sort Rooms

Room ID	Size
2	2
1	2
3	2

Sorted queries:

Min Size	Preferred	Original Index
3	3	1
2	5	2
1	3	0

Query: [3,3]

No room has size ≥ 3.

Room set:

{}

Answer:

-1

Query: [5,2]

Insert all rooms:

{1,2,3}

Binary search for 5:

left = 3
right = none

Choose:

Query: [3,1]

Room set remains:

{1,2,3}

Binary search for 3:

left = 3
right = 3

Distance:

|3 - 3| = 0

Choose:

Final answer:

Step 2: Sort Queries by minSize

Preferred	minSize	Original Index
3	3	1
5	2	2
3	1	0

Query: [3,3]

No room has size ≥ 3.

Valid Rooms	Answer
[]	-1

Query: [5,2]

Add all rooms.

Added Room	Valid Room IDs
2	[2]
1	[1,2]
3	[1,2,3]

Binary search for preferred = 5:

Candidate	Distance
3	2

Answer = 3

Query: [3,1]

All rooms already valid.

Binary search for preferred = 3:

Candidate	Distance
3	0

Answer = 3

Final output:

[3, -1, 3]

Example 2

Input:

rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]]
queries = [[2,3],[2,4],[2,5]]

Sorted rooms:

Step 1: Sort Rooms

Room ID	Size
3	5
1	4
2	3
5	2
4	1

Sorted queries:

Min Size	Preferred
5	2
4	2
3	2

Query: [2,5]

Insert:

{3}

Answer:

Query: [2,4]

Insert:

{1,3}

Distances:

|1 - 2| = 1
|3 - 2| = 1

Tie, choose smaller ID:

Query: [2,3]

Insert:

{1,2,3}

Exact match:

Final answer:

Step 2: Sort Queries

Preferred	minSize	Original Index
2	5	2
2	4	1
2	3	0

Query: [2,5]

Add room 3.

Valid Room IDs
[3]

Closest room to 2 is 3.

Answer = 3

Query: [2,4]

Add room 1.

Valid Room IDs
[1,3]

Distances:

Candidate	Distance
1	1
3	1

Tie resolved by smaller ID.

Answer = 1

Query: [2,3]

Add room 2.

Valid Room IDs
[1,2,3]

Closest room is 2.

Answer = 2

Final output in original query order:

[2,1,3]

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + k) log n)	Each room inserted once, each query performs logarithmic operations
Space	O(n + k)	Ordered set plus indexed queries and answer array

The rooms are sorted once, costing O(n log n). Queries are sorted once, costing O(k log k).

Each room is inserted exactly once into the ordered structure, contributing O(n log n) total work.

Each query performs a constant number of binary search operations, contributing O(k log n).

Combining all terms yields:

$$O((n+k)\log n)$$

The sorting of rooms and queries requires:

O(n log n + k log k)

Each room is inserted once, and each query performs binary searches.

The total complexity therefore becomes:

O((n + k) log n)

The auxiliary space consists mainly of:

The sorted valid room ID structure
The indexed query array
The result array

All together, this requires linear extra space.

Test Cases

from typing import List

s = Solution()

assert s.closestRoom(
    [[2,2],[1,2],[3,2]],
    [[3,1],[3,3],[5,2]]
) == [3,-1,3]  # example 1

assert s.closestRoom(
    [[1,4],[2,3],[3,5],[4,1],[5,2]],
    [[2,3],[2,4],[2,5]]
) == [2,1,3]  # example 2

assert s.closestRoom(
    [[10,5]],
    [[10,5]]
) == [10]  # single room exact match

assert s.closestRoom(
    [[10,5]],
    [[1,6]]
) == [-1]  # no valid room

assert s.closestRoom(
    [[1,10],[5,10]],
    [[3,1]]
) == [1]  # tie, smaller id wins

assert s.closestRoom(
    [[1,10],[100,10]],
    [[50,1]]
) == [1]  # equal distance tie

assert s.closestRoom(
    [[1,5],[2,6],[3,7]],
    [[2,1]]
) == [2]  # exact preferred room exists

assert s.closestRoom(
    [[1,3],[10,3],[20,3]],
    [[15,3]]
) == [10]  # predecessor closer

assert s.closestRoom(
    [[1,3],[10,3],[20,3]],
    [[18,3]]
) == [20]  # successor closer

assert s.closestRoom(
    [[5,1],[10,2],[15,3]],
    [[7,2],[12,3],[1,4]]
) == [10,15,-1]  # mixed constraints

Test Summary

Test	Why
Example 1	Validates official sample
Example 2	Validates tie-breaking and size filtering
Single room exact match	Smallest possible valid instance
No valid room	Ensures `-1` is returned correctly
Tie between two rooms	Tests smaller-ID tie-breaking
Large distance tie	Confirms tie rule independent of values
Exact preferred room	Tests zero-distance match
Predecessor closer	Tests floor candidate selection
Successor closer	Tests ceiling candidate selection
Mixed constraints	Verifies incremental room insertion logic

Edge Cases

No Room Meets the Minimum Size Requirement

A query may require a room size larger than every available room. In this situation the ordered set remains empty when the query is processed. The algorithm immediately returns -1 for that query. This avoids any invalid binary search operations.

Equal Distance on Both Sides

Suppose valid room IDs are 1 and 3, while preferred = 2. Both rooms are distance 1 away. The problem requires choosing the smaller room ID. The implementation explicitly checks for equal distances and selects the smaller ID, ensuring correct tie-breaking behavior.

Preferred ID Outside the Range of Valid Rooms

If every valid room ID is smaller than preferred, there will be no ceiling candidate. Similarly, if every valid room ID is larger than preferred, there will be no floor candidate. The implementation independently checks whether each candidate exists before comparing distances, correctly handling both situations.

Exact Room ID Match

If a valid room has ID equal to preferred, the binary search locates it directly. Its distance is zero, which is the minimum possible distance. The algorithm naturally selects it without requiring any special-case code.

Multiple Queries with Different Size Requirements

Queries may have very different minimum size thresholds. Processing them in descending order of minSize ensures that rooms are added only once. This is the key invariant that keeps the algorithm efficient while still guaranteeing correctness for every query. class Solution: def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]: from bisect import bisect_left, insort

    rooms.sort(key=lambda x: -x[1])

    indexed_queries = [
        (preferred, min_size, index)
        for index, (preferred, min_size) in enumerate(queries)
    ]

    indexed_queries.sort(key=lambda x: -x[1])

    answers = [-1] * len(queries)

    valid_room_ids = []
    room_pointer = 0

    for preferred, min_size, query_index in indexed_queries:

        while (
            room_pointer < len(rooms)
            and rooms[room_pointer][1] >= min_size
        ):
            insort(valid_room_ids, rooms[room_pointer][0])
            room_pointer += 1

        if not valid_room_ids:
            continue

        position = bisect_left(valid_room_ids, preferred)

        best_room = -1
        best_distance = float("inf")

        if position < len(valid_room_ids):
            candidate = valid_room_ids[position]
            distance = abs(candidate - preferred)

            if distance < best_distance:
                best_room = candidate
                best_distance = distance

        if position > 0:
            candidate = valid_room_ids[position - 1]
            distance = abs(candidate - preferred)

            if (
                distance < best_distance
                or (
                    distance == best_distance
                    and candidate < best_room
                )
            ):
                best_room = candidate

        answers[query_index] = best_room

    return answers

sol = Solution()

Provided example 1

assert sol.closestRoom( [[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]] ) == [3,-1,3]

Provided example 2

assert sol.closestRoom( [[1,4],[2,3],[3,5],[4,1],[5,2]], [[2,3],[2,4],[2,5]] ) == [2,1,3]

Single room exact match

assert sol.closestRoom( [[10,5]], [[10,5]] ) == [10]

No valid room

assert sol.closestRoom( [[1,1],[2,2]], [[5,10]] ) == [-1]

Tie case chooses smaller ID

assert sol.closestRoom( [[1,5],[3,5]], [[2,5]] ) == [1]

Preferred room exists

assert sol.closestRoom( [[4,10],[8,10]], [[8,5]] ) == [8]

Multiple queries different thresholds

assert sol.closestRoom( [[1,1],[2,2],[3,3],[4,4]], [[3,1],[3,2],[3,3],[3,4]] ) == [3,3,3,4]

Large preferred value

assert sol.closestRoom( [[1,5],[10000000,5]], [[9999999,5]] ) == [10000000]

Minimum boundary

assert sol.closestRoom( [[1,1]], [[1,1]] ) == [1]

Closest smaller neighbor

assert sol.closestRoom( [[1,5],[10,5],[20,5]], [[12,5]] ) == [10]


| Test | Why |
| --- | --- |
| Example 1 | Validates basic functionality and no-match handling |
| Example 2 | Validates tie-breaking behavior |
| Single room exact match | Ensures exact preferred match works |
| No valid room | Ensures `-1` is returned correctly |
| Tie case chooses smaller ID | Verifies tie-breaking rule |
| Preferred room exists | Confirms zero-distance selection |
| Multiple thresholds | Tests incremental room insertion |
| Large preferred value | Validates handling of large IDs |
| Minimum boundary | Tests smallest valid input |
| Closest smaller neighbor | Verifies binary search neighbor logic |

## Edge Cases

### No Rooms Satisfy the Minimum Size

A query may require a room size larger than every available room. This is a common source of bugs because binary search structures may be empty.

For example:

rooms = [[1,2]] queries = [[5,10]]


No room satisfies the size requirement.

The implementation explicitly checks whether the valid room structure is empty before performing binary search. If it is empty, the answer remains `-1`.

### Tie Between Two Equally Close Rooms

Suppose two rooms are equally distant from the preferred ID:

rooms = [[1,5],[3,5]] query = [2,5]


Both room IDs are distance `1` away.

The problem requires choosing the smaller room ID. This is easy to mishandle if the implementation only updates the answer when a strictly smaller distance is found.

The solution explicitly compares room IDs when distances are equal and selects the smaller candidate.

### Preferred Room Does Not Exist

The preferred room ID may not actually exist among valid rooms.

For example:

rooms = [[1,5],[10,5]] query = [6,5]


The closest room could be either neighbor around the insertion point.

This is why the algorithm checks both:

- The first room ID greater than or equal to the preferred value
- The room immediately before it

Checking only one side would produce incorrect answers in many cases.

LeetCode 1847 - Closest Room

Solution

LeetCode 1847: Closest Room

Problem Understanding

Problem Understanding

Example Interpretation

What the Constraints Tell Us

Important Edge Cases

Approaches

Brute Force

Key Insight

Approach Comparison

Algorithm Walkthrough

Why it Works

Approaches

Brute Force Approach

Optimal Approach

Algorithm Walkthrough

Why it works

Python Solution

Implementation Explanation

Go Solution

Go-Specific Notes

Worked Examples

Example 1

Step 1: Sort Rooms

Query: [3,3]

Query: [5,2]

Query: [3,1]

Step 2: Sort Queries by minSize

Query: [3,3]

Query: [5,2]

Query: [3,1]

Example 2

Step 1: Sort Rooms

Query: [2,5]

Query: [2,4]

Query: [2,3]

Step 2: Sort Queries

Query: [2,5]

Query: [2,4]

Query: [2,3]

Complexity Analysis

Test Cases

Test Summary

Edge Cases

No Room Meets the Minimum Size Requirement

Equal Distance on Both Sides

Preferred ID Outside the Range of Valid Rooms

Exact Room ID Match

Multiple Queries with Different Size Requirements

Provided example 1

Provided example 2

Single room exact match

No valid room

Tie case chooses smaller ID

Preferred room exists

Multiple queries different thresholds

Large preferred value

Minimum boundary

Closest smaller neighbor