How hard is LeetCode 612. Shortest Distance in a Plane?

LeetCode 612. Shortest Distance in a Plane is rated Medium on LeetCode.

What topics does LeetCode 612. Shortest Distance in a Plane cover?

LeetCode 612. Shortest Distance in a Plane is tagged Database on LeetCode.

Is LeetCode 612. Shortest Distance in a Plane a premium problem?

Yes. LeetCode 612. Shortest Distance in a Plane is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Shortest Distance in a Plane — LeetCode 612 Python Solution

MediumLeetCode PremiumDatabase

Problem: #612
Reading time: 2 min
Source: leetcode.com

The problem

Report the shortest Euclidean distance between any two distinct points in the table, rounded to two decimals, in a column named shortest. The Point2D table has one row per point: x (int) and y (int), with the pair (x, y) as the primary key.

Example

Point2D table:

| x  | y |
| -- | - |
| 0  | 0 |
| 3  | 4 |
| 1  | 1 |
| -2 | 2 |

Result:

| shortest |
| -------- |
| 1.41     |

The closest pair is (0, 0) and (1, 1), one unit apart on each axis, so the distance is the square root of 2, which rounds to 1.41.

Python solution

Python

import pandas as pd

def shortest_distance(point2d: pd.DataFrame) -> pd.DataFrame:
    pairs = point2d.merge(point2d, how='cross', suffixes=('_1', '_2'))
    pairs = pairs[(pairs['x_1'] != pairs['x_2']) | (pairs['y_1'] != pairs['y_2'])]
    dist = ((pairs['x_1'] - pairs['x_2']) ** 2 + (pairs['y_1'] - pairs['y_2']) ** 2) ** 0.5
    return pd.DataFrame({'shortest': [round(float(dist.min()), 2)]})

Complexity

Measure	Complexity
Time	O(n log n) (typical)
Space	O(n) auxiliary

Frequently asked questions

How hard is LeetCode 612. Shortest Distance in a Plane?: LeetCode 612. Shortest Distance in a Plane is rated Medium on LeetCode.
What topics does LeetCode 612. Shortest Distance in a Plane cover?: LeetCode 612. Shortest Distance in a Plane is tagged Database on LeetCode.
Is LeetCode 612. Shortest Distance in a Plane a premium problem?: Yes. LeetCode 612. Shortest Distance in a Plane is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.