LeetCode 612 - Shortest Distance in a Plane

This problem gives us a database table named Point2D, where every row represents a unique point on a 2D Cartesian plane. Each point contains two integer coordinates, x and y. The pair (x, y) is guaranteed to be unique because it is the primary key.

leetcodemediumdatabase

LeetCode Problem 612

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem gives us a database table named Point2D, where every row represents a unique point on a 2D Cartesian plane. Each point contains two integer coordinates, x and y. The pair (x, y) is guaranteed to be unique because it is the primary key.

We are asked to compute the shortest Euclidean distance between any two distinct points in the table. The Euclidean distance between two points:

  • p1(x1, y1)
  • p2(x2, y2)

is defined as:

$$\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$$

The final answer must be rounded to exactly two decimal places.

Although this is categorized as a database problem, the underlying algorithmic task is geometric. We must compare pairs of points and determine which pair has the minimum distance.

The input is conceptually a collection of points. The output is a single numeric value named shortest, representing the minimum pairwise distance.

One important detail is that a point cannot be compared with itself. Since the table contains unique coordinates, we never have duplicate points, which means the minimum distance will always be greater than zero.

The problem does not explicitly state the number of rows, but typical LeetCode database problems are small enough that an O(n²) pairwise comparison solution is acceptable. In SQL, this naturally translates into a self join.

Several edge cases are important to consider:

  • If two points share the same x coordinate or the same y coordinate, the distance formula still works correctly.
  • Negative coordinates must be handled properly because subtraction and squaring are involved.
  • Multiple pairs may share the same minimum distance, but we only need the distance value itself.
  • Since coordinates are unique, we never encounter a distance of 0.00.

Approaches

Brute Force Approach

The most direct approach is to compare every point with every other point. For each pair, we compute the Euclidean distance using the distance formula and keep track of the smallest value encountered.

In a traditional programming language, this would involve two nested loops. In SQL, this becomes a self join between the Point2D table and itself.

However, we must avoid comparing a point with itself. We also want to avoid counting the same pair twice. For example:

  • (A, B) and (B, A) represent the same pair.

To eliminate duplicates, we can enforce an ordering condition such as:

p1.x < p2.x OR (p1.x = p2.x AND p1.y < p2.y)

This ensures every unordered pair is considered exactly once.

This approach is correct because it exhaustively checks all possible point pairs. Since the minimum distance must belong to one of these pairs, the algorithm cannot miss the correct answer.

The downside is that the number of comparisons grows quadratically with the number of points.

Key Insight

The important observation is that this problem fundamentally requires pairwise comparison. Unlike advanced computational geometry problems that use divide-and-conquer optimizations, the SQL setting and expected constraints make the quadratic approach both practical and standard.

The real optimization is not reducing asymptotic complexity, but rather avoiding redundant comparisons:

  • Do not compare a point with itself.
  • Do not compare the same pair twice.

By carefully structuring the self join condition, we reduce unnecessary work while still guaranteeing correctness.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Compares every pair of points directly
Optimal O(n²) O(1) Uses a self join while avoiding duplicate pair comparisons

Algorithm Walkthrough

  1. Start with the Point2D table and create two aliases, typically p1 and p2. These aliases represent two different points being compared.
  2. Perform a self join between the table and itself. This allows every point to be paired with every other point.
  3. Add a condition to avoid invalid comparisons. Specifically:
  • A point should not be paired with itself.
  • Each unordered pair should appear only once.

A common condition is:

p1.x < p2.x OR (p1.x = p2.x AND p1.y < p2.y)

This creates a strict ordering between points. 4. For every valid pair, compute the Euclidean distance using:

$$\sqrt{(p1.x - p2.x)^2 + (p1.y - p2.y)^2}$$ 5. Use the SQL aggregate function MIN() to track the smallest distance across all pairs. 6. Round the result to two decimal places using ROUND(distance, 2). 7. Return the final value with the column name shortest.

Why it works

The algorithm examines every unique pair of distinct points exactly once. Since the shortest distance must belong to one of these pairs, taking the minimum over all computed distances guarantees the correct answer. The ordering condition prevents duplicate comparisons without excluding any valid pair.

Python Solution

Even though this is a database problem, we can still express the underlying logic in Python.

from typing import List
from math import sqrt

class Solution:
    def shortestDistance(self, points: List[List[int]]) -> float:
        n = len(points)
        minimum_distance = float("inf")

        for i in range(n):
            x1, y1 = points[i]

            for j in range(i + 1, n):
                x2, y2 = points[j]

                distance = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)

                minimum_distance = min(minimum_distance, distance)

        return round(minimum_distance, 2)

The implementation begins by initializing the minimum distance to infinity so that any computed distance will replace it.

The outer loop selects the first point in the pair, while the inner loop selects the second point. Notice that the inner loop starts at i + 1, which prevents:

  • self comparisons
  • duplicate pair comparisons

For every pair, the Euclidean distance formula is evaluated directly. The current minimum is updated whenever a smaller distance is found.

Finally, the answer is rounded to two decimal places before being returned.

Go Solution

package main

import (
	"math"
)

func shortestDistance(points [][]int) float64 {
	n := len(points)
	minimumDistance := math.Inf(1)

	for i := 0; i < n; i++ {
		x1, y1 := points[i][0], points[i][1]

		for j := i + 1; j < n; j++ {
			x2, y2 := points[j][0], points[j][1]

			dx := float64(x2 - x1)
			dy := float64(y2 - y1)

			distance := math.Sqrt(dx*dx + dy*dy)

			if distance < minimumDistance {
				minimumDistance = distance
			}
		}
	}

	return math.Round(minimumDistance*100) / 100
}

The Go version follows the same logic as the Python implementation. One important difference is explicit type conversion. Since math.Sqrt operates on float64, the coordinate differences must be converted from integers to floating-point values before squaring.

The result is rounded manually using:

math.Round(value * 100) / 100

because Go does not provide a built-in two-decimal formatting function for numeric return values.

SQL Solution

SELECT
    ROUND(
        MIN(
            SQRT(
                POW(p1.x - p2.x, 2) +
                POW(p1.y - p2.y, 2)
            )
        ),
        2
    ) AS shortest
FROM Point2D p1
JOIN Point2D p2
ON p1.x < p2.x
OR (p1.x = p2.x AND p1.y < p2.y);

This query performs a self join between the table aliases p1 and p2.

The join condition ensures:

  • no point is matched with itself
  • no duplicate pair is counted twice

For each valid pair, the Euclidean distance is computed using SQRT and POW. The MIN aggregate finds the smallest distance, and ROUND(..., 2) formats the answer correctly.

Worked Examples

Example 1

Input:

x y
-1 -1
0 0
-1 -2

We enumerate all unique pairs.

Pair Distance Calculation Distance
(-1, -1) and (0, 0) √((0+1)² + (0+1)²) √2 ≈ 1.41
(-1, -1) and (-1, -2) √((0)² + (-1)²) 1.00
(0, 0) and (-1, -2) √((-1)² + (-2)²) √5 ≈ 2.24

The minimum distance is:

1.00

Internal State Trace

Step Current Pair Current Distance Minimum So Far
1 (-1,-1), (0,0) 1.41 1.41
2 (-1,-1), (-1,-2) 1.00 1.00
3 (0,0), (-1,-2) 2.24 1.00

Final answer:

1.00

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Every unique pair of points is examined
Space O(1) Only a few variables are maintained

The quadratic time complexity comes from pairwise comparison. If there are n points, then there are approximately:

$$\frac{n(n-1)}{2}$$

unique pairs. Each pair requires constant work to compute the distance.

The algorithm uses constant extra space because it only stores the current minimum distance and temporary coordinate values.

Test Cases

from math import isclose

solution = Solution()

# Basic example from the problem statement
assert isclose(
    solution.shortestDistance([[-1, -1], [0, 0], [-1, -2]]),
    1.00
)

# Two points only
assert isclose(
    solution.shortestDistance([[0, 0], [3, 4]]),
    5.00
)

# Horizontal alignment
assert isclose(
    solution.shortestDistance([[1, 2], [4, 2], [10, 2]]),
    3.00
)

# Vertical alignment
assert isclose(
    solution.shortestDistance([[5, 1], [5, 6], [5, 8]]),
    2.00
)

# Negative coordinates
assert isclose(
    solution.shortestDistance([[-3, -4], [-1, -1], [2, 2]]),
    3.61,
    abs_tol=0.01
)

# Multiple pairs with same minimum distance
assert isclose(
    solution.shortestDistance([[0, 0], [1, 0], [0, 1], [1, 1]]),
    1.00
)

# Larger coordinate values
assert isclose(
    solution.shortestDistance([[1000, 1000], [1003, 1004], [2000, 2000]]),
    5.00
)

# Minimum distance not involving first point
assert isclose(
    solution.shortestDistance([[0, 0], [100, 100], [101, 101]]),
    1.41,
    abs_tol=0.01
)

Test Case Summary

Test Why
Problem statement example Validates standard functionality
Two points only Smallest valid input size
Horizontal alignment Ensures x-axis handling works
Vertical alignment Ensures y-axis handling works
Negative coordinates Verifies subtraction and squaring correctness
Multiple equal minimums Confirms algorithm handles ties
Large coordinates Tests arithmetic stability
Closest pair appears later Ensures full traversal occurs

Edge Cases

One important edge case occurs when points share the same x coordinate. In this situation, the horizontal difference becomes zero, and only the vertical difference contributes to the distance. Incorrect implementations sometimes mishandle zero differences or accidentally divide by zero when using slope-based logic. Our implementation directly applies the Euclidean formula, so zero coordinate differences are naturally handled.

Another critical edge case involves negative coordinates. Since subtraction between negative values can be error-prone, especially when manually manipulating formulas, implementations may accidentally compute incorrect differences. By using the standard squared distance formula exactly as defined, the implementation handles negative values correctly because squaring removes sign issues.

A third edge case appears when multiple point pairs share the same shortest distance. Some implementations incorrectly stop after finding the first minimum or overwrite values improperly. Our algorithm compares every unique pair and continuously updates the global minimum using min(), ensuring the correct minimum distance is preserved regardless of how many pairs share it.