Skip to main content
Talentd

Shortest Distance in a Plane - Solution & Explanation

MediumPremiumFree on FleetCodeDatabase3 min readAsked at: Meta
Practice this problem

Problem Statement

Table: Point2D

+-------------+------+
| Column Name | Type |
+-------------+------+
| x           | int  |
| y           | int  |
+-------------+------+
(x, y) is the primary key column (combination of columns with unique values) for this table.
Each row of this table indicates the position of a point on the X-Y plane.

 

The distance between two points p1(x1, y1) and p2(x2, y2) is sqrt((x2 - x1)2 + (y2 - y1)2).

Write a solution to report the shortest distance between any two points from the Point2D table. Round the distance to two decimal points.

The result format is in the following example.

 

Example 1:

Input: 
Point2D table:
+----+----+
| x  | y  |
+----+----+
| -1 | -1 |
| 0  | 0  |
| -1 | -2 |
+----+----+
Output: 
+----------+
| shortest |
+----------+
| 1.00     |
+----------+
Explanation: The shortest distance is 1.00 from point (-1, -1) to (-1, 2).

Approach Overview

Problem Overview: You have a table Point(x, y) representing coordinates on a 2D plane. The task is to compute the minimum Euclidean distance between any pair of distinct points and return the smallest value.

Approach 1: Cross Join All Point Pairs (O(n²) time, O(1) space)

The direct way is to compare every point with every other point. Use a self CROSS JOIN on the Point table and compute the Euclidean distance with SQRT(POW(x1-x2,2) + POW(y1-y2,2)). Filter out identical rows using a condition like p1.x != p2.x OR p1.y != p2.y. Then compute the minimum distance with MIN(). This approach is simple and works well when the dataset is small, but it generates duplicate comparisons (A→B and B→A), which doubles the number of calculated distances.

Approach 2: Self Join with Unique Pair Filtering (O(n²) time, O(1) space)

A better SQL formulation removes duplicate comparisons by enforcing a consistent ordering between points. Instead of comparing all pairs, restrict the join condition so each pair appears only once. A common trick is p1.x < p2.x OR (p1.x = p2.x AND p1.y < p2.y). This ensures the query evaluates only unique point pairs. The distance formula remains the same, and the result is aggregated with MIN() and rounded if required. This reduces redundant work while keeping the logic straightforward.

This problem is fundamentally a pairwise comparison task implemented with SQL joins. The key idea is that relational databases do not provide a built‑in geometric nearest‑neighbor operator for this schema, so you simulate it with a self join and a distance formula. The database engine evaluates every valid pair and keeps the smallest value.

Understanding how to structure self joins is essential for many SQL interview problems. You often join a table with itself to compare rows, compute differences, or detect relationships. This problem also reinforces how aggregation functions like MIN() work with derived calculations.

Conceptually, the solution combines three SQL ideas: a database self join, a computed expression for distance, and an aggregate function to select the smallest value. The join pattern is closely related to many classic SQL join interview questions where row‑to‑row comparisons are required.

Recommended for interviews: The unique pair self join approach is the expected solution. It shows you understand how to avoid duplicate comparisons while still evaluating all necessary point pairs. Starting with the naive cross join demonstrates the reasoning process, but the optimized join condition reflects stronger SQL problem‑solving skills.

Solution

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Cross Join All Point PairsO(n²)O(1)Simple implementation when dataset is small and duplicate comparisons are acceptable
Self Join with Unique Pair FilteringO(n²)O(1)Preferred SQL solution to avoid duplicate pair calculations

Video Solution

LeetCode Medium 612 “Shortest Distance in a Plane" Interview SQL Question Explanation | EDS • Everyday Data Science • 2,202 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Shortest Distance in a Plane easy or hard?
Shortest Distance in a Plane is rated Medium difficulty. The math is straightforward, but the challenge is writing the correct SQL self join and ensuring duplicate point pairs are not counted twice.
Shortest Distance in a Plane Python/Java solution
On LeetCode this problem is categorized under Database, so the expected solution is written in SQL (typically MySQL). In general programming languages like Python or Java, the equivalent approach would iterate over all point pairs and compute Euclidean distance, which also runs in O(n^2) time.
How to solve Shortest Distance in a Plane in O(n)?
An O(n) SQL solution is not feasible for this schema because the database must compare distances between pairs of points. Without spatial indexing or specialized geometric structures, the query requires evaluating all pairs, which leads to O(n^2) complexity.
What is the best approach for Shortest Distance in a Plane?
The best approach uses a self join that compares each point with only one ordered set of other points. By enforcing a condition such as p1.x < p2.x OR (p1.x = p2.x AND p1.y < p2.y), the query evaluates every unique pair once. The distance is computed using the Euclidean formula and the minimum value is returned with MIN().
Is Shortest Distance in a Plane asked at Google/Amazon/Meta?
SQL problems involving self joins, pair comparisons, and aggregation are common in database interview rounds at companies like Amazon and Meta. While this exact problem may vary, the join and aggregation pattern appears frequently in analytics and data engineering interviews.
What data structure is used in Shortest Distance in a Plane?
The problem operates directly on a relational database table. The main mechanism is a SQL self join that pairs rows from the same table and calculates distances using mathematical expressions.
What is the time complexity of Shortest Distance in a Plane?
The time complexity is O(n^2) because every pair of points must be compared to determine the smallest distance. Even with optimized join conditions that remove duplicates, the algorithm still evaluates roughly n*(n-1)/2 pairs.

Ready to solve this problem?

Practice Shortest Distance in a Plane with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary