612. Shortest Distance in a Plane
Model: qwen3.5:9b
Topics:
FAANG asked: 0
Acceptance rate: 61.7%
Problem Breakdown
We need to find the shortest (minimum) Euclidean distance between any two distinct points in a given set of coordinates on a plane.
Inputs: A list/array of 2D coordinate pairs, e.g., [[x1, y1], [x2, y2], ...].
Outputs: The minimum floating-point distance found among all unique point pairs.
Implicit Constraints & Edge Cases:
- Empty Input / Single Point: If the array has fewer than two points, no pair exists to calculate a distance between distinct entities (returning 0 or handling gracefully is standard defensive practice).
- Duplicates: Identical coordinates result in a Euclidean distance of 0. This is valid and should be handled naturally by the math formula.
- Coordinate Range: Coordinates can be negative, zero, or very large integers/floats. We must ensure no overflow occurs during squaring (Python handles arbitrary precision integers automatically).
- Performance: If is small (, typically on platforms like LeetCode), a brute-force approach works fine within time limits. For larger datasets, an optimized geometric algorithm or spatial indexing would be required to avoid Time Limit Exceeded (TLE).
Intuition
The core task is calculating Euclidean distance: .
Starting Point: The most straightforward approach is a brute-force iteration over every unique pair of points in the list, computing their distance and tracking the minimum.
- Why it’s insufficient for scale: This results in time complexity. If we have 50,000 points, that’s roughly 2.5 billion operations, which will likely TLE on standard interview platforms (usually ~1 second limit).
- Key Insight: To optimize beyond brute force for large datasets (), we need to prune the search space using spatial indexing or a Divide & Conquer strategy (like in the classic Closest Pair algorithm) which reduces complexity to but with higher constant factors and implementation overhead.
- Interview Strategy: In an interview, unless constraints specify massive inputs (), I would implement the brute force solution for clarity and correctness first. However, as a Senior Engineer, I must acknowledge that in production or high-scale scenarios, we’d use spatial indexes (like R-trees) or optimized libraries rather than raw loops to avoid reinventing complex geometry logic.
Approach
- Initialization: Initialize
min_distwith infinity (float('inf')). - Iteration: Loop through all unique pairs of points in the input list. To optimize slightly without full D&C, we can skip checking if a point is identical to another (distance becomes 0). The inner loop starts from to avoid comparing and then .
- Calculation: Use
math.hypot(dx, dy)for cleaner code and better numerical stability compared to manual squaring/roots (sqrtis slower than hypot in some implementations). - Update Minimum: If the current pair’s distance is less than
min_dist, update it immediately (greedy approach works here since we want global minimum). - Return: Return the final minimum value found (or handle empty input case by returning a sentinel like 0 or None depending on spec; usually constraints guarantee points).
Note: For this walkthrough, I will provide the clean implementation as it demonstrates the logic clearly without obscuring code with complex geometric partitioning details that are hard to debug in a text block. In production, one would use scipy.spatial.distance or spatial databases for large datasets.
Complexity Analysis
- Time: . We check every pair of points once ( pairs). This is acceptable for small-to-medium inputs typically found in standard online judge constraints (). For larger inputs, the complexity becomes prohibitive without Divide & Conquer or spatial indexing optimizations.
- Space: . We only store a few variables for distance calculation (
min_dist, loop indices), excluding input storage which is required by definition.
Solution
import math
def shortest_distance(points):
"""
Calculates the minimum Euclidean distance between any two points in the list.
Args:
points (List[List[int/float]]): List of [x, y] coordinates.
Returns:
float: The smallest distance found.
If fewer than 2 points exist or all are duplicates, returns 0.0.
"""
# Handle edge case where we cannot form a pair
if len(points) < 2:
return 0.0
min_dist = math.inf
n = len(points)
for i in range(n):
x1, y1 = points[i]
for j in range(i + 1, n): # Optimization: start from next point to avoid duplicates and self-checks
x2, y2 = points[j]
# Calculate Euclidean distance using hypot (handles sqrt(x^2+y^2) internally with better stability)
current_dist = math.hypot(x2 - x1, y2 - y1)
if current_dist < min_dist:
min_dist = current_dist
return min_dist
Edge Cases Handled
- Empty or Single Point List: The function checks
len(points) < 2and returns0.0, preventing index errors on the inner loop logic. - Duplicate Coordinates: If two points are identical,
math.hypot(0, 0)results in0.0. Since we initialize with infinity, this correctly updatesmin_distto0.0. - Negative Coordinates: The subtraction
(x2 - x1)handles negative numbers naturally (e.g.,-5 - (-3) = -2). Squaring/hypot ensures the result is positive regardless of sign direction. - Large Coordinate Values: Python’s arbitrary precision integers handle large inputs without overflow before conversion to float, and
math.hypotmanages floating-point limits reasonably well for standard interview constraints (though extreme values might lose machine epsilon precision).