Problem

Table: Coordinates

+-------------+------+
| Column Name | Type |
+-------------+------+
| X           | int  |
| Y           | int  |
+-------------+------+
Each row includes X and Y, where both are integers. Table may contain duplicate values.

Two coordindates (X1, Y1) and (X2, Y2) are said to be symmetric coordintes if X1 == Y2 and X2 == Y1.

Write a solution that outputs, among all these symmetric coordintes , only those unique coordinates that satisfy the condition X1 <= Y1.

Return the result table ordered byX and Y (respectively) inascending order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Input: 
Coordinates table:
+----+----+
| X  | Y  |
+----+----+
| 20 | 20 |
| 20 | 20 |
| 20 | 21 |
| 23 | 22 |
| 22 | 23 |
| 21 | 20 |
+----+----+
Output: 
+----+----+
| x  | y  |
+----+----+
| 20 | 20 |
| 20 | 21 |
| 22 | 23 |
+----+----+
Explanation: 
- (20, 20) and (20, 20) are symmetric coordinates because, X1 == Y2 and X2 == Y1. This results in displaying (20, 20) as a distinctive coordinates.
- (20, 21) and (21, 20) are symmetric coordinates because, X1 == Y2 and X2 == Y1. However, only (20, 21) will be displayed because X1 <= Y1.
- (23, 22) and (22, 23) are symmetric coordinates because, X1 == Y2 and X2 == Y1. However, only (22, 23) will be displayed because X1 <= Y1.
The output table is sorted by X and Y in ascending order.

Solution

Approach

We join the table with itself to find symmetric pairs (X1, Y1) and (X2, Y2) such that X1 = Y2 and X2 = Y1. We only keep unique pairs where X1 <= Y1 and order the result as required.

Code

MySQL
1
2
3
4
5

SELECT DISTINCT a.X AS x, a.Y AS y
FROM Coordinates a
JOIN Coordinates b ON a.X = b.Y AND a.Y = b.X
WHERE a.X <= a.Y
ORDER BY a.X, a.Y;
Oracle
1
2
3
4
5

SELECT DISTINCT a.X AS x, a.Y AS y
FROM Coordinates a
JOIN Coordinates b ON a.X = b.Y AND a.Y = b.X
WHERE a.X <= a.Y
ORDER BY a.X, a.Y;
PostgreSQL
1
2
3
4
5

SELECT DISTINCT a.X AS x, a.Y AS y
FROM Coordinates a
JOIN Coordinates b ON a.X = b.Y AND a.Y = b.X
WHERE a.X <= a.Y
ORDER BY a.X, a.Y;

Explanation

We self-join the table to find symmetric pairs, filter for X <= Y, and use DISTINCT to ensure uniqueness. The result is ordered as required.

Complexity

  • ⏰ Time complexity: O(N^2) in the worst case due to the self-join, where N is the number of rows.
  • 🧺 Space complexity: O(N) for storing the result set.