Problem Statement
Proximity Point Finder
You're developing a mapping application that needs to find the closest points of interest to the user's current location.
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on a plane is the Euclidean distance: √((x1 - x2)² + (y1 - y2)²).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
Examples
Example 1:
Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation: The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:
Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.
Constraints
- 1 <= k <= points.length <= 10^4
- -10^4 < points[i][0], points[i][1] < 10^4
Problem Breakdown
To solve this problem, we need to:
- The Euclidean distance from a point (x, y) to the origin (0, 0) is sqrt(x² + y²)
- Since we only care about comparing distances, we can use x² + y² instead of sqrt(x² + y²) to avoid floating-point calculations
- We need to find the k points with the smallest distances to the origin
- A max heap of size k can efficiently maintain the k closest points
- Alternatively, we can sort all points by their distances and return the first k points
- The QuickSelect algorithm can find the k closest points in O(n) average time
String Problems
Learning Objective
Apply string manipulation concepts to solve a real-world problem.
Proximity Point Finder
You're developing a mapping application that needs to find the closest points of interest to the user's current location.
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on a plane is the Euclidean distance: √((x1 - x2)² + (y1 - y2)²).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
Examples
Example 1:
The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].
Example 2:
The answer [[-2,4],[3,3]] would also be accepted.
Problem Breakdown
Constraints:
- 1 <= k <= points.length <= 10^4
- -10^4 < points[i][0], points[i][1] < 10^4
Key Insights:
The Euclidean distance from a point (x, y) to the origin (0, 0) is sqrt(x² + y²)
Since we only care about comparing distances, we can use x² + y² instead of sqrt(x² + y²) to avoid floating-point calculations
We need to find the k points with the smallest distances to the origin
A max heap of size k can efficiently maintain the k closest points
Alternatively, we can sort all points by their distances and return the first k points
The QuickSelect algorithm can find the k closest points in O(n) average time
Real-World Application
This problem has several practical applications:
Mapping Applications
Finding nearby points of interest like restaurants, gas stations, or attractions.
Location-Based Services
Providing services based on proximity to the user's current location.
Recommendation Systems
Recommending items or places based on geographical proximity.
Route Planning
Finding the closest facilities or waypoints for efficient route planning.