How do you solve Closest Room on LeetCode?

Closest Room (LeetCode #1847) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n + k log k) time complexity and O(n) space complexity. Key insight: Sorting rooms by size helps in quickly filtering valid rooms for each query.

What is the brute force solution for Closest Room?

The brute force approach for Closest Room is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each room against every query to find the closest room that meets the size requirement. This is straightforward but inefficient, especially as the number of rooms and queries increases. The optimal Optimal Solution approach improves this to O(n log n + k log k).

What algorithm or data structure is used to solve Closest Room?

Closest Room uses the following concepts: Array, Binary Search, Sorting, Ordered Set. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Closest Room?

Always clarify the problem constraints and edge cases before diving into coding. Discuss your thought process and potential optimizations with the interviewer. Practice explaining your code as you write it, as this simulates the interview environment.

What are common mistakes when solving Closest Room?

Not considering the case where no room meets the size requirement. Failing to sort the rooms or queries appropriately before processing.

#1847

Closest Room

Hard

ArrayBinary SearchSortingOrdered SetHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n + k log k)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n + k log k)Space O(n)

By sorting the rooms by size and using a data structure to efficiently find the closest room, we can significantly reduce the time complexity. This approach leverages binary search and a sorted list to quickly find valid rooms.

⚙️

Algorithm

5 steps

1Step 1: Sort the rooms based on their size in descending order.
2Step 2: For each query, filter rooms that meet the minimum size requirement.
3Step 3: Use a sorted data structure (like a set) to store room IDs for efficient searching.
4Step 4: For each query, find the closest room ID using binary search on the sorted set of room IDs.
5Step 5: Return the closest room ID or -1 if no valid room exists.

solution.py21 lines

1def closestRoom(rooms, queries):
2    from sortedcontainers import SortedList
3    rooms.sort(key=lambda x: -x[1])  # Sort by size descending
4    result = [-1] * len(queries)
5    sorted_ids = SortedList()
6    query_indices = sorted(range(len(queries)), key=lambda x: queries[x][1], reverse=True)
7    j = 0
8    for idx in query_indices:
9        preferred, minSize = queries[idx]
10        while j < len(rooms) and rooms[j][1] >= minSize:
11            sorted_ids.add(rooms[j][0])
12            j += 1
13        pos = sorted_ids.bisect_left(preferred)
14        candidates = []
15        if pos < len(sorted_ids):
16            candidates.append(sorted_ids[pos])
17        if pos > 0:
18            candidates.append(sorted_ids[pos - 1])
19        if candidates:
20            result[idx] = min(candidates, key=lambda x: (abs(x - preferred), x))
21    return result

ℹ

Complexity note: The time complexity is O(n log n) for sorting the rooms and O(k log k) for processing the queries with a sorted set, making it efficient for larger inputs.

1Sorting rooms by size helps in quickly filtering valid rooms for each query.
2Using a sorted data structure allows efficient searching for the closest room ID.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.