69 / 75
Medium
K Closest Points to Origin
#69arraymathheapquickselectsortinggeometry
Use max-heap of size k tracking distances; maintain k closest points by comparing squared distances.
Example:
Input:
points=[[1,3],[-2,2]], k=1Output:
[[-2,2]] (distance 8 < distance 10)Common Mistakes:
- Calculating actual distance with sqrt (unnecessary and slower)
- Using min-heap instead of max-heap (makes size maintenance harder)
- Integer overflow with distance calculation (use long for large values)
- Not understanding why max-heap of size k works
Notes:
Max-heap approach: O(n log k), Space O(k). Can optimize to O(n) average with quickselect. No need for sqrt, use squared distance.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Use max-heap of size k tracking distances; maintain k closest points by comparing squared distances.
Example:
Input:
points=[[1,3],[-2,2]], k=1Output:
[[-2,2]] (distance 8 < distance 10)Common Mistakes:
- Calculating actual distance with sqrt (unnecessary and slower)
- Using min-heap instead of max-heap (makes size maintenance harder)
- Integer overflow with distance calculation (use long for large values)
- Not understanding why max-heap of size k works
Notes:
Max-heap approach: O(n log k), Space O(k). Can optimize to O(n) average with quickselect. No need for sqrt, use squared distance.
69/75
K Closest Points to Origin