Given an array of points [[x1, y1], [x2, y2], ...] and an integer K, return the K closest points to the origin (0, 0) based on Euclidean distance.
✅ Swift Solution Using Sorting (Simple & Effective)
func kClosest(_ points: [[Int]], _ k: Int) -> [[Int]] {
// Sort points by distance to origin (0, 0)
let sortedPoints = points.sorted {
let d1 = $0[0] * $0[0] + $0[1] * $0[1]
let d2 = $1[0] * $1[0] + $1[1] * $1[1]
return d1 < d2
}
return Array(sortedPoints.prefix(k))
}
// Example usage
let points = [[1,3],[-2,2],[5,8],[0,1]]
let k = 2
let result = kClosest(points, k)
print("K closest points to origin:", result) // Output: [[-2, 2], [0, 1]]
🧠 Explanation:
Compute the squared distance to avoid unnecessary square roots.
Sort all points based on this squared distance.
Return the first K points.
⏱️ Time Complexity:
O(n log n) for sorting
If you want O(n log k), use a max-heap (priority queue) — more
efficient for large n.
Top comments (0)