Closest Room - Practice Coding Problems

Closest Room - Problem

You're managing a luxury hotel booking system where guests have specific room preferences. Your hotel has n rooms, each with a unique room number and size. You need to efficiently handle k guest queries, where each guest specifies their preferred room number and minimum room size requirement.

For each query, find the room that:

Has a size of at least the guest's minimum requirement
Has a room number closest to their preferred number
In case of ties in distance, choose the room with the smaller room number

If no suitable room exists, return -1 for that query.

Example: If rooms are [[2,130],[3,120],[4,110]] and a guest queries [3,125], only room 2 meets the size requirement (130 ≥ 125), so return 2.

Input & Output

example_1.py — Basic Hotel Query

$ Input: rooms = [[2,130],[3,120],[4,110]], queries = [[3,125]]

› Output: [2]

💡 Note: Guest prefers room 3 with minimum size 125. Only room 2 (size 130) meets the requirement. Distance from 3 to 2 is |2-3| = 1.

example_2.py — Multiple Queries

$ Input: rooms = [[1,100],[2,200],[3,150]], queries = [[2,100],[2,180]]

› Output: [2,2]

💡 Note: Query 1: Rooms 1,2,3 all meet size 100. Room 2 is exact match for preferred 2. Query 2: Only rooms 2,3 meet size 180. Room 2 (distance 0) is closer than room 3 (distance 1).

example_3.py — No Valid Room

$ Input: rooms = [[1,50],[2,60]], queries = [[3,100]]

› Output: [-1]

💡 Note: No room has size ≥ 100, so return -1 for this query.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ k ≤ 10⁴
1 ≤ roomId_i, preferred_j ≤ 10⁷
1 ≤ size_i, minSize_j ≤ 10⁷
All room IDs are unique

Visualization

Tap to expand

Understanding the Visualization

Initial Setup

Sort rooms by size and queries by minimum size requirement (descending)

Process High Requirements First

Start with queries needing largest rooms, building valid room set incrementally

Binary Search Magic

For each query, binary search the sorted valid rooms to find closest room number

Optimal Result

Return the best room for each guest with minimal computational overhead

Key Takeaway

🎯 Key Insight: By processing queries in descending order of size requirement and maintaining a sorted set of valid rooms, we transform an O(k×n) problem into an O(n log n) solution using the power of binary search!

Asked in

G Google 45 a Amazon 38 ⊞ Microsoft 32 f Meta 28

The optimal solution uses sorting and binary search to efficiently handle multiple queries. By processing queries in descending order of minimum size and maintaining a sorted set of valid room IDs, we can use binary search to quickly find the closest room number. This reduces time complexity from O(k×n) to O(n log n + k log k + (n+k) log n).

Common Approaches

Approach	Time	Space	Notes
✓ Sorting + Binary Search (Optimal)	O(n log n + k log k + (n + k) log n)	O(n + k)	Sort queries by size, process in descending order with binary search for closest room ID
Brute Force (Check All Rooms)	O(k × n)	O(1)	For each query, check every room and find the closest valid one

Sorting + Binary Search (Optimal) — Algorithm Steps

Sort rooms by size in ascending order
Create query indices sorted by minimum size in descending order
Process queries in sorted order, maintaining a sorted set of valid room IDs
For each query, add newly valid rooms to the sorted set
Use binary search on the sorted set to find the closest room ID

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Setup

Sort rooms by size, sort query indices by minSize descending

Process Queries

For each query in order, add newly valid rooms to sorted set

Binary Search

Use binary search to find closest room ID efficiently

Optimal Selection

Compare candidates and select best room with tie-breaking

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int compareRooms(const void* a, const void* b) {
    int* roomA = *(int**)a;
    int* roomB = *(int**)b;
    return roomA[1] - roomB[1];
}

int compareQueries(const void* a, const void* b) {
    int idxA = *(int*)a;
    int idxB = *(int*)b;
    extern int** globalQueries;
    return globalQueries[idxB][1] - globalQueries[idxA][1];
}

int** globalQueries;

int* closestRoom(int** rooms, int roomsSize, int** queries, int queriesSize, int* returnSize) {
    *returnSize = queriesSize;
    globalQueries = queries;
    
    // Sort rooms by size
    qsort(rooms, roomsSize, sizeof(int*), compareRooms);
    
    // Create and sort query indices
    int* queryIndices = (int*)malloc(queriesSize * sizeof(int));
    for (int i = 0; i < queriesSize; i++) queryIndices[i] = i;
    qsort(queryIndices, queriesSize, sizeof(int), compareQueries);
    
    int* result = (int*)malloc(queriesSize * sizeof(int));
    int* validRooms = (int*)malloc(roomsSize * sizeof(int));
    int validCount = 0;
    int roomIdx = roomsSize - 1;
    
    for (int q = 0; q < queriesSize; q++) {
        int i = queryIndices[q];
        int preferred = queries[i][0];
        int minSize = queries[i][1];
        
        // Add all rooms with size >= minSize
        while (roomIdx >= 0 && rooms[roomIdx][1] >= minSize) {
            int roomId = rooms[roomIdx][0];
            // Insert in sorted order
            int pos = validCount;
            while (pos > 0 && validRooms[pos-1] > roomId) {
                validRooms[pos] = validRooms[pos-1];
                pos--;
            }
            validRooms[pos] = roomId;
            validCount++;
            roomIdx--;
        }
        
        if (validCount == 0) {
            result[i] = -1;
            continue;
        }
        
        // Find closest room using binary search
        int left = 0, right = validCount;
        while (left < right) {
            int mid = (left + right) / 2;
            if (validRooms[mid] < preferred) left = mid + 1;
            else right = mid;
        }
        
        int bestRoom = validRooms[0];
        int bestDistance = abs(bestRoom - preferred);
        
        // Check room at position
        if (left < validCount) {
            int distance = abs(validRooms[left] - preferred);
            if (distance < bestDistance) {
                bestRoom = validRooms[left];
                bestDistance = distance;
            }
        }
        
        // Check room before position
        if (left > 0) {
            int distance = abs(validRooms[left-1] - preferred);
            if (distance < bestDistance || (distance == bestDistance && validRooms[left-1] < bestRoom)) {
                bestRoom = validRooms[left-1];
            }
        }
        
        result[i] = bestRoom;
    }
    
    free(queryIndices);
    free(validRooms);
    return result;
}

int main() {
    // Input parsing and function call would be implemented here
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + k log k + (n + k) log n)

Sorting rooms and queries, plus binary search operations

⚡ Linearithmic

Space Complexity

O(n + k)

Space for sorted structures and result array

⚡ Linearithmic Space

23.6K Views

Medium-High Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sorting + Binary Search (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler