Problem

Table: Coordinates

1
2
3
4
5
6
7

+-------------+------+
| 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

Method 1 - Self-Join with Filter

Intuition

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.

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.

Complexity

  • ⏰ Time complexity: O(N^2) – In the worst case the self-join compares each row with every other row; grouping/lookup dominates.
  • 🧺 Space complexity: O(N) – We may materialize intermediate result sets or distinct pairs (one per unique symmetric pair).

Code

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;
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;
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;