Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

1847. Closest Room - Leetcode Solution

Problem Description

You are given a list of rooms, where each room is represented as [roomId, size]. You are also given a list of queries, each as [preferred, minSize]. For each query, you need to find the roomId of the room that:

  • Has a size greater than or equal to minSize
  • Has a roomId as close as possible to preferred (absolute difference minimized)
  • If there are multiple such rooms, return the one with the smallest roomId
  • If no such room exists, return -1 for that query

Constraints:
  • Each room can be used for multiple queries (no "reuse" restriction)
  • Room IDs and sizes can be large, so efficiency is important
  • One answer per query

Thought Process

The naive approach is to, for each query, scan all rooms and filter those with sufficient size, then pick the roomId closest to the preferred value. However, this brute-force method is inefficient for large inputs.

To optimize, we notice:

  • We can sort rooms by size, so that we only consider rooms large enough for each query
  • For fast lookups of the closest roomId to a preferred value, we can use a data structure that supports efficient "find closest" operations, such as a balanced BST or a sorted list with binary search
  • By sorting queries by decreasing minSize, we can process rooms in decreasing size order, adding eligible rooms as we go, and answer each query efficiently
This approach shifts from brute-force to an efficient, event-driven method using sorting and binary search.

Solution Approach

Here's how we can solve the problem efficiently:

  1. Sort rooms by size (descending):
    • This allows us to quickly find all rooms that are large enough for each query by iterating from largest to smallest.
  2. Sort queries by minSize (descending), keeping track of their original indices:
    • We process the "hardest" queries (largest minSize) first, so we only add rooms that are big enough as we go.
  3. Use a sorted list or BST to keep track of eligible roomIds:
    • As we process each query, we add all rooms whose size is at least the query's minSize to our data structure.
    • We then use binary search to find the closest roomId to the preferred value.
  4. For each query:
    • If there are no eligible rooms, return -1
    • Otherwise, use binary search to find the roomId closest to the preferred value; if there's a tie, pick the smaller roomId.
  5. Restore the original order of queries for the result.

Design choices:

  • We use a sorted list (or TreeSet/TreeMap in Java/C++) for efficient insertion and "find closest" operations.
  • Sorting both rooms and queries allows us to process only necessary data and avoid repeated work.

Example Walkthrough

Input:
rooms = [[2,3],[1,5],[3,7]]
queries = [[3,5],[3,3],[5,2]]

Step-by-step:

  • Sort rooms by size: [[3,7],[1,5],[2,3]]
  • Sort queries by minSize (descending): [(0,[3,5]), (1,[3,3]), (2,[5,2])]
Processing queries:
  • Query 0: preferred=3, minSize=5
    - Add rooms with size >= 5: room 3 (size 7), room 1 (size 5).
    - Eligible roomIds: [1,3]
    - Closest to 3: roomId 3 (abs(3-3)=0), roomId 1 (abs(1-3)=2).
    - Pick roomId 3.
  • Query 1: preferred=3, minSize=3
    - Add rooms with size >= 3: already added above, plus room 2 (size 3).
    - Eligible roomIds: [1,2,3]
    - Closest to 3: roomId 3 (abs(3-3)=0), roomId 2 (abs(2-3)=1), roomId 1 (abs(1-3)=2).
    - Pick roomId 3.
  • Query 2: preferred=5, minSize=2
    - All rooms eligible.
    - Eligible roomIds: [1,2,3]
    - Closest to 5: roomId 3 (abs(3-5)=2), roomId 2 (abs(2-5)=3), roomId 1 (abs(1-5)=4).
    - Pick roomId 3.
Result: [3, 3, 3]

Time and Space Complexity

Brute-force:

  • For each query, scan all rooms: O(Q * N), where Q is number of queries and N is number of rooms.
  • Not efficient for large inputs.
Optimized approach:
  • Sort rooms: O(N log N)
  • Sort queries: O(Q log Q)
  • For each query, insert eligible rooms (overall O(N log N)), and for each query, binary search for closest roomId (O(log N) per query)
  • Total: O(N log N + Q log Q + Q log N)
  • Space: O(N) for storing eligible roomIds

This is much more efficient and suitable for large datasets.

Summary

The Closest Room problem can be solved efficiently by sorting both rooms and queries, and using a sorted data structure to maintain eligible roomIds as we process each query. This allows us to quickly insert new rooms and find the closest roomId to the preferred value using binary search, resulting in a scalable and elegant solution. The key insight is to process queries in order of decreasing minSize, so we only need to add each room once and always have the correct set of eligible rooms for each query.

Code Implementation

from bisect import bisect_left, insort

def closestRoom(rooms, queries):
    rooms.sort(key=lambda x: -x[1])
    indexed_queries = sorted([(i, q[0], q[1]) for i, q in enumerate(queries)], key=lambda x: -x[2])
    res = [-1] * len(queries)
    room_ids = []
    i = 0
    n = len(rooms)
    for idx, preferred, minSize in indexed_queries:
        while i < n and rooms[i][1] >= minSize:
            insort(room_ids, rooms[i][0])
            i += 1
        if not room_ids:
            res[idx] = -1
            continue
        pos = bisect_left(room_ids, preferred)
        candidates = []
        if pos < len(room_ids):
            candidates.append(room_ids[pos])
        if pos > 0:
            candidates.append(room_ids[pos-1])
        # Find the closest
        best = min(candidates, key=lambda x: (abs(x - preferred), x))
        res[idx] = best
    return res
      
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

vector<int> closestRoom(vector<vector<int>>& rooms, vector<vector<int>>& queries) {
    sort(rooms.begin(), rooms.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] > b[1];
    });
    vector<tuple<int,int,int>> indexed_queries;
    for (int i = 0; i < queries.size(); ++i)
        indexed_queries.push_back({i, queries[i][0], queries[i][1]});
    sort(indexed_queries.begin(), indexed_queries.end(), [](const tuple<int,int,int>& a, const tuple<int,int,int>& b){
        return get<2>(a) > get<2>(b);
    });
    set<int> room_ids;
    vector<int> res(queries.size(), -1);
    int i = 0, n = rooms.size();
    for (auto& q : indexed_queries) {
        int idx = get<0>(q), preferred = get<1>(q), minSize = get<2>(q);
        while (i < n && rooms[i][1] >= minSize)
            room_ids.insert(rooms[i++][0]);
        if (room_ids.empty()) continue;
        auto it = room_ids.lower_bound(preferred);
        int best = -1;
        if (it != room_ids.end()) best = *it;
        if (it != room_ids.begin()) {
            int cand = *prev(it);
            if (best == -1 || abs(cand - preferred) < abs(best - preferred) || (abs(cand - preferred) == abs(best - preferred) && cand < best))
                best = cand;
        }
        res[idx] = best;
    }
    return res;
}
      
import java.util.*;

class Solution {
    public int[] closestRoom(int[][] rooms, int[][] queries) {
        Arrays.sort(rooms, (a, b) -> b[1] - a[1]);
        int n = queries.length;
        int[][] q = new int[n][3];
        for (int i = 0; i < n; ++i) {
            q[i][0] = queries[i][0];
            q[i][1] = queries[i][1];
            q[i][2] = i;
        }
        Arrays.sort(q, (a, b) -> b[1] - a[1]);
        TreeSet<Integer> roomIds = new TreeSet<>();
        int[] res = new int[n];
        Arrays.fill(res, -1);
        int i = 0, m = rooms.length;
        for (int[] query : q) {
            int preferred = query[0], minSize = query[1], idx = query[2];
            while (i < m && rooms[i][1] >= minSize) {
                roomIds.add(rooms[i][0]);
                i++;
            }
            if (roomIds.isEmpty()) continue;
            Integer higher = roomIds.ceiling(preferred);
            Integer lower = roomIds.floor(preferred);
            int best = -1;
            if (higher != null) best = higher;
            if (lower != null) {
                if (best == -1 || Math.abs(lower - preferred) < Math.abs(best - preferred) || (Math.abs(lower - preferred) == Math.abs(best - preferred) && lower < best))
                    best = lower;
            }
            res[idx] = best;
        }
        return res;
    }
}
      
function closestRoom(rooms, queries) {
    rooms.sort((a, b) => b[1] - a[1]);
    let indexedQueries = queries.map((q, i) => [i, q[0], q[1]]);
    indexedQueries.sort((a, b) => b[2] - a[2]);
    let res = Array(queries.length).fill(-1);
    let roomIds = [];
    let i = 0;
    for (const [idx, preferred, minSize] of indexedQueries) {
        while (i < rooms.length && rooms[i][1] >= minSize) {
            // Insert in sorted order (binary search)
            let left = 0, right = roomIds.length;
            while (left < right) {
                let mid = (left + right) >> 1;
                if (roomIds[mid] < rooms[i][0]) left = mid + 1;
                else right = mid;
            }
            roomIds.splice(left, 0, rooms[i][0]);
            i++;
        }
        if (roomIds.length === 0) continue;
        // Binary search for closest
        let left = 0, right = roomIds.length - 1;
        while (left < right) {
            let mid = (left + right) >> 1;
            if (roomIds[mid] < preferred) left = mid + 1;
            else right = mid;
        }
        let candidates = [];
        if (left < roomIds.length) candidates.push(roomIds[left]);
        if (left > 0) candidates.push(roomIds[left - 1]);
        let best = candidates[0];
        for (let cand of candidates) {
            if (Math.abs(cand - preferred) < Math.abs(best - preferred) ||
                (Math.abs(cand - preferred) === Math.abs(best - preferred) && cand < best)) {
                best = cand;
            }
        }
        res[idx] = best;
    }
    return res;
}