LeetCode 612: Shortest Distance in a Plane Solution in Python – A Step-by-Step Guide

What Is LeetCode 612: Shortest Distance in a Plane?

In LeetCode 612: Shortest Distance in a Plane, you’re given a table point_2d with columns x and y, each row representing a point’s coordinates in a 2D plane. Your task is to find the shortest Euclidean distance between any two distinct points, where the distance between points (x1, y1) and (x2, y2) is sqrt((x1-x2)² + (y1-y2)²). For example, points [0,0] and [3,4] have a distance of 5. This problem tests your ability to handle geometric computations, typically posed as an SQL query with a self-join, but we’ll solve it in Python for a coding twist.

Problem Statement

• Input: A list of records (or table rows) with [x, y].
• Output: A float—the shortest Euclidean distance between any two distinct points.
• Rules:
• Euclidean distance: sqrt((x1-x2)² + (y1-y2)²).
• Points are distinct (no self-distance).
• Return exact or approximate value (within 10⁻⁵ precision).

Constraints

• Table has at least 2 rows.
• -10⁶ ≤ x, y ≤ 10⁶.
• Number of rows ≤ 10⁴.

Examples

• Input:
``` x | y 0 | 0 3 | 4 ```
• Output: 5.0 (Distance between [0,0] and [3,4])
• Input:
``` x | y 1 | 1 2 | 2 3 | 3 ```
• Output: 1.4142135623730951 (Distance between [1,1] and [2,2], sqrt(2))
• Input:
``` x | y 0 | 0 0 | 1 1 | 0 ```
• Output: 1.0 (Distance between [0,0] and [0,1] or [0,0] and [1,0])

These examples set the stage—let’s solve it!

Understanding the Problem: Measuring Distances

To solve LeetCode 612: Shortest Distance in a Plane in Python, we need to compute the Euclidean distance between every pair of distinct points and find the minimum. A naive approach might calculate all distances and sort them, but we can optimize. We’ll use:

• Best Solution (Brute-Force Pairwise): O(n²) time, O(1) space—simple and practical for given constraints.
• Alternative Solution (K-D Tree): O(n log n) average time, O(n) space—faster for large datasets but complex.

Let’s start with the brute-force solution, breaking it down for beginners.

Best Solution: Brute-Force Pairwise Distance Calculation

Why This Is the Best Solution

The brute-force pairwise approach is the top choice for LeetCode 612 under its constraints (up to 10⁴ points) because it’s straightforward—O(n²) time with O(1) space—and doesn’t require advanced data structures. It computes distances directly, making it easy to understand and implement, and is fast enough for the problem’s scale. It’s like measuring every pair with a ruler and picking the shortest!

How It Works

Think of this as a point-by-point check:

• Step 1: Process All Pairs:
• Use two nested loops to compare each point with every other point.
• Step 2: Calculate Distance:
• For points (x1, y1) and (x2, y2), compute sqrt((x1-x2)² + (y1-y2)²).
• Use math.sqrt for precision.
• Step 3: Track Minimum:
• Keep a running minimum distance, updating when a smaller one is found.
• Step 4: Return Result:
• Output the smallest distance found.

It’s like a distance sweep—check every pair and spot the closest!

Step-by-Step Example

Example:

Copy codex | y
0 | 0
3 | 4

• Pairs:
• [0,0] vs [3,4]:
• (0-3)² = 9, (0-4)² = 16.
• 9 + 16 = 25, sqrt(25) = 5.
• Min Distance: 5.0 (only one pair).
• Output: 5.0.

Example:

Copy codex | y
1 | 1
2 | 2
3 | 3

• Pairs:
• [1,1] vs [2,2]: sqrt((1-2)² + (1-2)²) = sqrt(2) ≈ 1.414.
• [1,1] vs [3,3]: sqrt((1-3)² + (1-3)²) = sqrt(8) ≈ 2.828.
• [2,2] vs [3,3]: sqrt((2-3)² + (2-3)²) = sqrt(2) ≈ 1.414.
• Min Distance: 1.414 (between [1,1] and [2,2] or [2,2] and [3,3]).
• Output: 1.4142135623730951.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codeimport math

class Solution:
    def shortestDistance(self, points: List[List[int]]) -> float:
        # Step 1: Initialize variables
        n = len(points)
        min_dist = float('inf')  # Start with infinity

        # Step 2: Compare all pairs
        for i in range(n):
            for j in range(i + 1, n):  # Avoid self and duplicates
                x1, y1 = points[i]
                x2, y2 = points[j]

                # Step 3: Calculate Euclidean distance
                dist = math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)

                # Step 4: Update minimum
                min_dist = min(min_dist, dist)

        # Step 5: Return result
        return min_dist

• Line 1: Import math for sqrt.
• Lines 6-7: Setup:
• n: Number of points.
• min_dist: Track smallest distance.
• Lines 10-15: Nested loops:
• i + 1 avoids self-comparison and repeats (e.g., [i,j] same as [j,i]).
• Compute distance with formula.
• Line 17: Update min_dist.
• Time Complexity: O(n²)—check all pairs.
• Space Complexity: O(1)—just a variable.

This is like a distance checker—simple and effective!

Alternative Solution: K-D Tree Approach

Why an Alternative Approach?

The k-d tree approach builds a spatial tree to find nearest neighbors—O(n log n) average time for construction and querying, O(n) space. It’s faster for large datasets (beyond this problem’s constraints) and showcases advanced techniques, but it’s overkill for 10⁴ points and harder to grasp. It’s like using a GPS to map closest points!

How It Works

Picture this as a spatial search:

• Step 1: Build a k-d tree from points.
• Step 2: For each point, query nearest neighbor.
• Step 3: Track the smallest distance found.
• Step 4: Return the minimum.

It’s like a smart distance locator—complex but quick for big data!

Step-by-Step Example

Example:

Copy codex | y
0 | 0
3 | 4

• Build K-D Tree:
• Root: [0,0], split on x.
• Right: [3,4].
• Query:
• [0,0]: Nearest [3,4], dist = 5.
• [3,4]: Nearest [0,0], dist = 5.
• Min Distance: 5.0.
• Output: 5.0.

Code for K-D Tree Approach

(Note: For simplicity, we’ll use scipy.spatial.KDTree, a built-in implementation.)

Copy codefrom scipy.spatial import KDTree
import math

class Solution:
    def shortestDistance(self, points: List[List[int]]) -> float:
        # Step 1: Build k-d tree
        tree = KDTree(points)

        # Step 2: Query nearest neighbor for each point
        min_dist = float('inf')
        for i, point in enumerate(points):
            # Query returns distance and index of nearest neighbor
            dist, idx = tree.query(point, k=2)  # k=2 to skip self
            if idx[1] != i:  # Ensure not self
                min_dist = min(min_dist, dist[1])  # Second closest (first is self)

        # Step 3: Return result
        return min_dist

• Line 1: Import KDTree.
• Line 7: Build tree from points.
• Lines 10-14: Query:
• k=2 gets self and nearest, use second distance.
• Time Complexity: O(n log n)—tree build and queries.
• Space Complexity: O(n)—tree storage.

It’s a spatial shortcut—advanced but fast!

Comparing the Two Solutions

• Brute-Force (Best):
• Pros: O(n²) time, O(1) space, simple for small n.
• Cons: Slow for very large n.
• K-D Tree (Alternative):
• Pros: O(n log n) average time, O(n) space, scalable.
• Cons: Complex, library-dependent.

Brute-force wins for this problem’s scale.

Additional Examples and Edge Cases

• Input: [[0,0], [1,1]]
• Output: 1.4142135623730951.
• Input: [[1,2], [1,2]]
• Output: 0.0 (if duplicates allowed, but problem assumes distinct).

Brute-force handles well; k-d tree needs distinctness.

Complexity Breakdown

• Brute-Force: Time O(n²), Space O(1).
• K-D Tree: Time O(n log n), Space O(n).

Brute-force is practical here.

Key Takeaways

• Brute-Force: Simple distance check—smart!
• K-D Tree: Spatial efficiency—clear!
• Geometry: Distances are fun.
• Python Tip: Math rocks—see Python Basics.

Final Thoughts: Measure That Distance

LeetCode 612: Shortest Distance in a Plane in Python is a cool geometry challenge. Brute-force offers simplicity for this scale, while k-d trees shine for bigger tasks. Want more? Try LeetCode 149: Max Points on a Line or LeetCode 973: K Closest Points to Origin. Ready to map? Head to Solve LeetCode 612 on LeetCode and find that shortest distance today!