2dbi
Home/Dynatrace/Find the K Closest Points / Heap
DDynatrace·DSAEngineerTechnical Phone Screen

Find the K Closest Points / Heap

Problem

Given points and a target, return the k closest (by distance).

Example

points, k=2 -> two nearest

Constraints

  • 1 ≤ k ≤ n ≤ 10^5

Approach

Max-heap of size k or quickselect. O(n log k).

added 6 days ago
LeadersAccount