Closest Room

Hard

#1687Time: O(N * K), where N is the number of rooms and K is the number of queries. For each of the K queries, we perform a linear scan of all N rooms.Space: O(K) or O(1). O(K) to store the answer array. If the output array is not considered part of the space complexity, it is O(1).

Algorithms

Binary Search Sorting

Data structures

Array Ordered Set

Prompt

There is a hotel with n rooms. The rooms are represented by a 2D integer array rooms where rooms[i] = [roomId_i, size_i] denotes that there is a room with room number roomId_i and size equal to size_i. Each roomId_i is guaranteed to be unique.

You are also given k queries in a 2D array queries where queries[j] = [preferred_j, minSize_j]. The answer to the j^th query is the room number id of a room such that:

The room has a size of at least minSize_j, and
abs(id - preferred_j) is minimized, where abs(x) is the absolute value of x.

If there is a tie in the absolute difference, then use the room with the smallest such id. If there is no such room, the answer is -1.

Return an array answer of length k where answer[j] contains the answer to the j^th query.

Example 1:

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:
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]
Explanation: 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 <= 10⁵
k == queries.length
1 <= k <= 10⁴
1 <= roomId_i, preferred_j <= 10⁷
1 <= size_i, minSize_j <= 10⁷

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves iterating through every room for each query. For a given query, we check every room to see if it meets the minimum size requirement. Among the valid rooms, we keep track of the one that has the minimum absolute difference in room ID compared to the preferred ID.

Algorithm

Initialize an answer array ans of size k.
Iterate through each query j from 0 to k-1.
For each query [preferred_j, minSize_j], initialize bestRoomId = -1 and minDiff = infinity.
Iterate through each room i from 0 to n-1.
Let the current room be [roomId_i, size_i].
Check if size_i >= minSize_j.
If the condition is met, calculate the difference diff = abs(roomId_i - preferred_j).
Compare diff with minDiff:
- If diff < minDiff, update minDiff = diff and bestRoomId = roomId_i.
- If diff == minDiff, update bestRoomId = min(bestRoomId, roomId_i) to handle the tie-breaking rule.
After iterating through all rooms, store the final bestRoomId in ans[j].
After iterating through all queries, return the ans array.

Walkthrough

The algorithm iterates through each of the k queries. For each query [preferred_j, minSize_j], it initializes a variable bestRoomId to -1 and minDiff to infinity. It then iterates through all n rooms [roomId_i, size_i]. Inside the inner loop, it checks if size_i >= minSize_j. If the size condition is met, it calculates the absolute difference diff = abs(roomId_i - preferred_j). It compares this diff with the current minDiff. If the new diff is smaller, the current room becomes the best candidate. If the diff is the same, the tie-breaking rule (smaller roomId) is applied. After checking all rooms, the best found room ID is the answer for the current query. This process is repeated for all queries.

1class Solution {2    public int[] closestRoom(int[][] rooms, int[][] queries) {3        int k = queries.length;4        int[] ans = new int[k];5 6        for (int j = 0; j < k; j++) {7            int preferred = queries[j][0];8            int minSize = queries[j][1];9            10            int bestRoomId = -1;11            int minDiff = Integer.MAX_VALUE;12 13            for (int[] room : rooms) {14                int roomId = room[0];15                int size = room[1];16 17                if (size >= minSize) {18                    int diff = Math.abs(roomId - preferred);19                    if (diff < minDiff) {20                        minDiff = diff;21                        bestRoomId = roomId;22                    } else if (diff == minDiff) {23                        bestRoomId = Math.min(bestRoomId, roomId);24                    }25                }26            }27            ans[j] = bestRoomId;28        }29        return ans;30    }31}

Complexity

Time

O(N * K), where N is the number of rooms and K is the number of queries. For each of the K queries, we perform a linear scan of all N rooms.

Space

O(K) or O(1). O(K) to store the answer array. If the output array is not considered part of the space complexity, it is O(1).

Trade-offs

Pros

Simple to understand and implement.
Requires minimal extra space.

Cons

Highly inefficient for large inputs.
Will likely result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms due to its quadratic time complexity.

This is a much more efficient approach that avoids re-evaluating rooms for every query. The core idea is to process queries "offline". We sort both the rooms and the queries based on size in descending order. This allows us to consider rooms in a way that once a room is available for a high minSize query, it remains available for all subsequent (lower minSize) queries. We use a TreeSet to maintain the IDs of available rooms, which allows for efficient searching of the closest ID.

Algorithm

Preprocessing:
- Augment the queries array to store the original index of each query: [preferred, minSize, original_index].
- Sort the rooms array in descending order of size.
- Sort the augmented queries array in descending order of minSize.
Processing:
- Initialize an empty TreeSet<Integer> named availableRoomIds to store IDs of rooms that meet the size criteria.
- Initialize an answer array ans of size k.
- Initialize a pointer roomIndex = 0 for the sorted rooms array.
Iterate through sorted queries:
- For each query [preferred, minSize, originalIndex]: a. Add newly available rooms: While roomIndex < n and rooms[roomIndex][1] >= minSize, add rooms[roomIndex][0] to availableRoomIds and increment roomIndex. b. Find the closest room ID in availableRoomIds: - If availableRoomIds is empty, the answer is -1. - Otherwise, find the two best candidates using floor(preferred) and ceiling(preferred) methods of the TreeSet. - Compare these two candidates to find the one with the minimum absolute difference from preferred, respecting the tie-breaking rule (smaller ID). c. Store the result in ans[originalIndex].
Return ans.

Walkthrough

This optimized approach hinges on processing queries offline. First, we sort the rooms by size in descending order. We also augment the queries to include their original index and then sort them by their minSize requirement, also in descending order. This sorting strategy is key: as we process queries with decreasing minSize, the set of available rooms only grows.

We iterate through the sorted queries. For each query, we add all rooms that now meet the minSize requirement into a TreeSet. A TreeSet is a balanced binary search tree that stores elements in sorted order and allows for efficient lookups. Since both rooms and queries are sorted by size, we can do this with a single pass over the rooms array across all queries.

Once the TreeSet contains all valid room IDs for the current query, we find the closest ID to the preferred ID. The two potential candidates are the floor (largest ID <= preferred) and ceiling (smallest ID >= preferred). We compare these two candidates, find the one with the minimum absolute difference, handle the tie-breaking rule, and store the result in an answer array at its original index. This avoids the O(N) scan for each query, leading to a much better time complexity.

1import java.util.Arrays;2import java.util.TreeSet;3 4class Solution {5    public int[] closestRoom(int[][] rooms, int[][] queries) {6        int n = rooms.length;7        int k = queries.length;8 9        // Sort rooms by size in descending order10        Arrays.sort(rooms, (a, b) -> Integer.compare(b[1], a[1]));11 12        // Augment queries with original index13        int[][] indexedQueries = new int[k][3];14        for (int i = 0; i < k; i++) {15            indexedQueries[i][0] = queries[i][0]; // preferred16            indexedQueries[i][1] = queries[i][1]; // minSize17            indexedQueries[i][2] = i;             // original index18        }19 20        // Sort queries by minSize in descending order21        Arrays.sort(indexedQueries, (a, b) -> Integer.compare(b[1], a[1]));22 23        int[] ans = new int[k];24        TreeSet<Integer> availableRoomIds = new TreeSet<>();25        int roomIndex = 0;26 27        for (int[] query : indexedQueries) {28            int preferred = query[0];29            int minSize = query[1];30            int originalIndex = query[2];31 32            // Add all rooms with size >= minSize to the TreeSet33            while (roomIndex < n && rooms[roomIndex][1] >= minSize) {34                availableRoomIds.add(rooms[roomIndex][0]);35                roomIndex++;36            }37 38            // Find the closest room ID from the available ones39            if (availableRoomIds.isEmpty()) {40                ans[originalIndex] = -1;41                continue;42            }43 44            Integer floor = availableRoomIds.floor(preferred);45            Integer ceil = availableRoomIds.ceiling(preferred);46 47            int bestRoomId = -1;48            int minDiff = Integer.MAX_VALUE;49 50            if (floor != null) {51                int diff = preferred - floor;52                if (diff < minDiff) {53                    minDiff = diff;54                    bestRoomId = floor;55                }56            }57 58            if (ceil != null) {59                int diff = ceil - preferred;60                if (diff < minDiff) {61                    minDiff = diff;62                    bestRoomId = ceil;63                } else if (diff == minDiff) {64                    bestRoomId = Math.min(bestRoomId, ceil);65                }66            }67            68            ans[originalIndex] = bestRoomId;69        }70 71        return ans;72    }73}

Complexity

Time

O(N log N + K log K). Sorting rooms takes O(N log N) and sorting queries takes O(K log K). The main processing loop involves O(N) insertions into the `TreeSet` (each O(log N)) and O(K) lookups (each O(log N)). The total time is dominated by the initial sorting steps, resulting in O(N log N + K log K).

Space

O(N + K). We need O(K) space for the augmented queries array and the answer array. The `TreeSet` can store up to N room IDs in the worst case, requiring O(N) space.

Trade-offs

Pros

Highly efficient and passes the given constraints.
The offline processing technique is a powerful and generalizable pattern for similar problems.

Cons

More complex to implement compared to the brute-force approach.
Requires modifying the query structure and careful handling of pointers and data structures.

Solutions

Solution

1class Solution { public int [] closestRoom ( int [][] rooms , int [][] queries ) { int n = rooms . length ; int k = queries . length ; Arrays . sort ( rooms , ( a , b ) -> a [ 1 ] - b [ 1 ]); Integer [] idx = new Integer [ k ]; for ( int i = 0 ; i < k ; i ++) { idx [ i ] = i ; } Arrays . sort ( idx , ( i , j ) -> queries [ i ][ 1 ] - queries [ j ][ 1 ]); int i = 0 ; TreeMap < Integer , Integer > tm = new TreeMap <>(); for ( int [] room : rooms ) { tm . merge ( room [ 0 ], 1 , Integer: : sum ); } int [] ans = new int [ k ]; Arrays . fill ( ans , - 1 ); for ( int j : idx ) { int prefer = queries [ j ][ 0 ], minSize = queries [ j ][ 1 ]; while ( i < n && rooms [ i ][ 1 ] < minSize ) { if ( tm . merge ( rooms [ i ][ 0 ], - 1 , Integer: : sum ) == 0 ) { tm . remove ( rooms [ i ][ 0 ]); } ++ i ; } if ( i == n ) { break ; } Integer p = tm . ceilingKey ( prefer ); if ( p != null ) { ans [ j ] = p ; } p = tm . floorKey ( prefer ); if ( p != null && ( ans [ j ] == - 1 || ans [ j ] - prefer >= prefer - p )) { ans [ j ] = p ; } } return ans ; } }

1class Solution { public: vector < int > closestRoom ( vector < vector < int >>& rooms , vector < vector < int >>& queries ) { int n = rooms . size (); int k = queries . size (); sort ( rooms . begin (), rooms . end (), []( const vector < int >& a , const vector < int >& b ) { return a [ 1 ] < b [ 1 ]; }); vector < int > idx ( k ); iota ( idx . begin (), idx . end (), 0 ); sort ( idx . begin (), idx . end (), [ & ]( int i , int j ) { return queries [ i ][ 1 ] < queries [ j ][ 1 ]; }); vector < int > ans ( k , - 1 ); int i = 0 ; multiset < int > s ; for ( auto & room : rooms ) { s . insert ( room [ 0 ]); } for ( int j : idx ) { int prefer = queries [ j ][ 0 ], minSize = queries [ j ][ 1 ]; while ( i < n && rooms [ i ][ 1 ] < minSize ) { s . erase ( s . find ( rooms [ i ][ 0 ])); ++ i ; } if ( i == n ) { break ; } auto it = s . lower_bound ( prefer ); if ( it != s . end ()) { ans [ j ] = * it ; } if ( it != s . begin ()) { -- it ; if ( ans [ j ] == - 1 || abs ( * it - prefer ) <= abs ( ans [ j ] - prefer )) { ans [ j ] = * it ; } } } return ans ; } };

1from 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 ]) 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem