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 by X and Y (respectively) in ascending order.
The result format is in the following example.
Example 1:
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.
Problem Overview: You are given a table of coordinates. A pair of rows is considered symmetric if one row contains (x, y) and another row contains (y, x). The task is to return these symmetric coordinate pairs without duplicates.
Approach 1: Basic Self Join (O(n²) time, O(1) extra space)
Join the coordinates table with itself and look for rows where a.x = b.y and a.y = b.x. To avoid pairing a row with itself incorrectly, use a condition such as a.id < b.id or another unique column. This ensures each symmetric pair appears once. The database engine performs a comparison between rows, which conceptually behaves like O(n²) comparisons, though indexes can improve real performance.
This approach works well when the dataset is small and the schema already includes a unique identifier. The logic is straightforward: match reversed coordinates directly with a join condition.
Approach 2: Window Function + Self Join (O(n²) time, O(n) space)
Duplicate coordinate values can create tricky cases, especially when x = y. A coordinate like (5,5) is symmetric with itself only if it appears more than once. Window functions help here. First compute a frequency or row number using a window function such as COUNT(*) OVER(PARTITION BY x, y) or ROW_NUMBER(). Then perform the self join on reversed coordinates and filter duplicates using ordering conditions.
This method cleanly handles edge cases. When x = y, require the count of that coordinate to be greater than one. For general symmetric pairs, ensure you only return one direction by enforcing a consistent ordering condition such as a.x <= a.y or by comparing IDs.
Window functions reduce ambiguity when multiple identical rows exist. Modern SQL engines like MySQL 8+ optimize these operations efficiently, making this approach reliable for production queries involving moderate datasets.
Recommended for interviews: The window function + self join approach is the safest answer. The simple self join shows you understand the symmetry condition, but handling duplicates and x = y cases demonstrates deeper SQL skill. Interviewers expect candidates to combine joins with analytical functions when working with relational data. Review related concepts such as SQL, database querying, and window functions.
We can use the window function ROW_NUMBER() to add an auto-incrementing sequence number to each row. Then, we perform a self join on the two tables, with the join conditions being p1.x = p2.y AND p1.y = p2.x AND p1.x <= p1.y AND p1.id != p2.id. Finally, we sort and remove duplicates.
MySQL
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Basic Self Join | O(n²) | O(1) | Small datasets or when a unique row identifier allows easy duplicate filtering |
| Window Function + Self Join | O(n²) | O(n) | Best for handling duplicate coordinates and cases where x = y using analytic functions |
Search in rotated sorted array - Leetcode 33 - Python • NeetCode • 413,348 views views
Watch 9 more video solutions →Practice Symmetric Coordinates with our built-in code editor and test cases.
Practice on FleetCode