Closest Room — LeetCode 1847 Python Solution
HardArrayBinary SearchOrdered SetSorting
- Problem
- #1847
- Pattern
- Monotonic Stack
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- 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:
Python solution
Python
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log n + k \times \log k) |
| Space | O(n + k) auxiliary |
Pattern: Monotonic Stack
Answer "what is the next greater element" for every position in one pass. LeetCode 1847. Closest Room is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1847. Closest Room?
- LeetCode 1847. Closest Room is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1847. Closest Room?
- The Python solution on this page runs in O(n \times \log n + k \times \log k).
- What is the space complexity of LeetCode 1847. Closest Room?
- The Python solution on this page uses O(n + k) auxiliary space.
- What topics does LeetCode 1847. Closest Room cover?
- LeetCode 1847. Closest Room is tagged Array, Binary Search, Ordered Set and Sorting on LeetCode.