612 Shortest Distance in a Plane

Description

Table: Point2D

• (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).

Problem Statement

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:

Output:

Explanation:

• The shortest distance is 1.00 from point (-1, -1) to (-1, 2).

Solution

In order to find the distance between two points, you can use which type of join? You can use CROSS JOIN to find the cartesian product of the two tables. Now, if you simply use the CROSS join, you might find the same point and end up getting distance as 0 which will be incorrect.In order to ensure that you’re not calculating the distance between the same points, you have to check based on two points where the x or y values are different. It’s possible that one of the values can be the same but the other value will be different for two different points.

1SELECT * FROM Point2D p1
2    CROSS JOIN Point2D p2
3    WHERE p1.x != p2.x OR p1.y != p2.y;

Next, you need to calculate the distance between the two points. This you can find using below formula.

1SELECT SQRT(POWER(p1.x - p2.x, 2) + POWER(p1.y - p2.y, 2))

The last point is that you need to find the shortest distance between two points from this table. For this you can use the MIN() function. You also need to round the distance to two decimal places.

The final solution would look like below.

1SELECT 
2    ROUND(MIN(SQRT(POW(p1.x - p2.x, 2) + POW(p1.y - p2.y, 2))), 2) AS shortest
3    FROM Point2D p1
4    JOIN Point2D p2
5    ON p1.x != p2.x OR p1.y != p2.y;