K Closest Hotels

Problem

You are building a hotel recommendation feature for a travel app. Given a user's current GPS coordinate and a list of hotels (each with their own GPS coordinates), return the K closest hotels to the user.

Distance is measured using the standard Euclidean distance formula:

distance = sqrt((x2 - x1)² + (y2 - y1)²)

You do not need to return the results sorted by distance — any valid set of K closest hotels is acceptable.

Input Format

• hotels: A list of [id, x, y] where id is a unique integer hotel identifier, and x, y are GPS coordinates (floats).
• target: A list [x, y] representing the user's current GPS location.
• k: An integer representing the number of closest hotels to return.

Output Format

Return a list of hotel ids (integers) representing the K closest hotels. The order does not matter.

Examples

Example 1

Input:

hotels = [[1, 1.0, 2.0], [2, 5.0, 4.0], [3, 3.0, 3.0], [4, -1.0, -1.0]]
target = [0.0, 0.0]
k = 2

Output: [1, 4]

Explanation: Distances from (0, 0):

• Hotel 1: sqrt(1² + 2²) = sqrt(5) ≈ 2.24
• Hotel 2: sqrt(5² + 4²) = sqrt(41) ≈ 6.40
• Hotel 3: sqrt(3² + 3²) = sqrt(18) ≈ 4.24
• Hotel 4: sqrt(1² + 1²) = sqrt(2) ≈ 1.41

The 2 closest are Hotel 4 (≈1.41) and Hotel 1 (≈2.24).

Example 2

Input:

hotels = [[10, 0.0, 1.0], [20, 0.0, -1.0], [30, 1.0, 0.0]]
target = [0.0, 0.0]
k = 1

Output: [10] or [20] or [30] (any one is valid)

Explanation: All hotels are at distance 1.0. Any single hotel is a valid answer.

Example 3

Input:

hotels = [[1, 2.0, 3.0]]
target = [5.0, 7.0]
k = 1

Output: [1]

Explanation: Only one hotel exists, so it must be returned.

Approach Hints

• Naive approach: Compute distances for all hotels, sort them, and pick the top K. This is O(N log N) — fine for small N but slow for 10 million hotels.
• Optimal approach: Use a max-heap of size K. Iterate through all hotels; maintain a max-heap storing the K smallest distances seen so far. If a new hotel is closer than the farthest hotel in the heap, replace it. This runs in O(N log K) time and O(K) space — critical when N = 10,000,000.
• Bonus: Think about how a K-D tree could preprocess the hotel data for repeated queries in O(log N + K) per query.