LeetCode 2978 - Symmetric Coordinates

This problem asks us to identify symmetric coordinate pairs from a database table called Coordinates. Each row in the table represents a coordinate (X, Y), and duplicate rows are allowed.

leetcodemediumdatabase

LeetCode Problem 2978

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to identify symmetric coordinate pairs from a database table called Coordinates.

Each row in the table represents a coordinate (X, Y), and duplicate rows are allowed. Two coordinates are considered symmetric if they satisfy the following condition:

  • (X1, Y1) and (X2, Y2) are symmetric when X1 == Y2 and X2 == Y1

In simpler terms, one coordinate must be the reverse of the other. For example:

  • (20, 21) and (21, 20) are symmetric because swapping the values in one coordinate produces the other.
  • (23, 22) and (22, 23) are symmetric for the same reason.

There is one special case: coordinates where X == Y, such as (20, 20). These coordinates are symmetric with themselves, but they are only considered valid if they appear at least twice in the table. This requirement exists because the problem defines symmetry between two coordinates, meaning a single occurrence of (20, 20) does not form a pair.

The problem only wants unique coordinates in the output, and it imposes an additional constraint:

  • Return only coordinates satisfying X <= Y

This prevents duplicate symmetric representations. For example:

  • (20, 21) and (21, 20) are symmetric, but only (20, 21) is returned because 20 <= 21.
  • (23, 22) is excluded because 23 > 22, while (22, 23) is included.

Finally, the result must be sorted by:

  1. X in ascending order
  2. Y in ascending order

Since this is a database problem, the expected solution is an SQL query. The main challenge is correctly handling:

  • Regular symmetric pairs such as (a, b) and (b, a)
  • Duplicate entries
  • Self symmetric coordinates (x, x) that must appear at least twice
  • Removing duplicate output rows

A naive implementation can easily fail on duplicate handling or self symmetric coordinates. For example, if (20, 20) appears only once, it should not be included. Similarly, duplicate (20, 21) rows should still only produce one result.

Approaches

Brute Force Approach

A straightforward solution would compare every coordinate against every other coordinate in the table.

For each row (X1, Y1), we scan all rows again looking for (X2, Y2) such that:

  • X1 == Y2
  • Y1 == X2

If a symmetric partner exists, we include the coordinate only when X1 <= Y1 to avoid duplicates.

For self symmetric coordinates such as (20, 20), we must ensure that at least two matching rows exist, since one row alone does not form a valid symmetric pair.

This approach is correct because every possible pair of coordinates is examined. However, it is inefficient because every row is compared against every other row, resulting in quadratic work.

Optimal Approach

The key observation is that symmetry can be checked efficiently using a self join.

Instead of comparing every pair manually, we join the Coordinates table with itself:

  • One copy represents (X1, Y1)
  • Another copy represents (X2, Y2)

We match rows where:

  • c1.X = c2.Y
  • c1.Y = c2.X

This directly captures the symmetry definition.

We then handle two separate cases:

  1. Non self symmetric coordinates (X != Y)

A simple self join is enough. 2. Self symmetric coordinates (X == Y)

Since symmetry requires two coordinates, we must ensure duplicates exist. This can be done using GROUP BY and COUNT(*) > 1.

Finally, we enforce X <= Y to remove duplicate mirrored results and sort the final answer.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Compares every coordinate pair
Optimal O(n log n) O(n) Uses self join and grouping, database indexing may improve performance

Algorithm Walkthrough

Optimal SQL Algorithm

  1. Perform a self join on the Coordinates table.

We create two aliases of the same table, c1 and c2. This allows us to compare coordinates against each other. 2. Match symmetric coordinates.

During the join, enforce:

  • c1.X = c2.Y
  • c1.Y = c2.X

This guarantees that each matched pair satisfies the symmetry definition. 3. Handle self symmetric coordinates carefully.

For coordinates where X = Y, we only want them if multiple copies exist. To avoid matching a row to itself, require either:

  • Different row instances in the join, or
  • Use aggregation to ensure count > 1
  1. Restrict output to X <= Y.

This removes duplicate mirrored representations.

For example:

  • Keep (20, 21)
  • Skip (21, 20)
  1. Remove duplicate output rows.

Since duplicate coordinates may exist in the table, use DISTINCT. 6. Sort the result.

Order by X ASC, Y ASC.

Why it works

The algorithm works because the self join explicitly encodes the definition of symmetry. Every valid symmetric pair must satisfy:

(X1, Y1) = reverse(X2, Y2)

The X <= Y condition guarantees uniqueness by selecting only one representative from each symmetric pair. The duplicate check for (X, X) coordinates ensures a coordinate is only considered symmetric with itself if at least two rows exist. Together, these conditions exactly match the problem requirements.

Python Solution

Since this is a Database problem, the LeetCode solution is an SQL query rather than a Python class method.

# SQL solution represented as a Python multiline string

query = """
SELECT DISTINCT c1.X, c1.Y
FROM Coordinates c1
JOIN Coordinates c2
ON c1.X = c2.Y
AND c1.Y = c2.X
WHERE c1.X <= c1.Y
AND (
    c1.X != c1.Y
    OR EXISTS (
        SELECT 1
        FROM Coordinates c3
        WHERE c3.X = c1.X
        AND c3.Y = c1.Y
        GROUP BY c3.X, c3.Y
        HAVING COUNT(*) > 1
    )
)
ORDER BY c1.X, c1.Y;
"""

The implementation begins with a self join between Coordinates c1 and Coordinates c2. The join condition checks whether one coordinate is the reverse of the other.

The WHERE c1.X <= c1.Y condition ensures only one coordinate from each symmetric pair is included.

The additional conditional logic handles self symmetric coordinates. When X != Y, no special handling is needed because the coordinate must have a matching reverse row. When X == Y, an EXISTS subquery verifies that the coordinate appears more than once.

Finally, DISTINCT removes duplicate output rows, and ORDER BY ensures the required sorted result.

Go Solution

As a database problem, Go code is not applicable because LeetCode expects an SQL query submission.

-- MySQL Solution

SELECT DISTINCT c1.X, c1.Y
FROM Coordinates c1
JOIN Coordinates c2
ON c1.X = c2.Y
AND c1.Y = c2.X
WHERE c1.X <= c1.Y
AND (
    c1.X != c1.Y
    OR EXISTS (
        SELECT 1
        FROM Coordinates c3
        WHERE c3.X = c1.X
        AND c3.Y = c1.Y
        GROUP BY c3.X, c3.Y
        HAVING COUNT(*) > 1
    )
)
ORDER BY c1.X, c1.Y;

Unlike algorithmic LeetCode problems, this database problem does not require language specific handling for memory management, integer overflow, slices, or nil values. The same SQL query is submitted directly to the judge.

Worked Examples

Example 1

Input:

X Y
20 20
20 20
20 21
23 22
22 23
21 20

The algorithm first performs the self join.

Coordinate Reverse Exists? X ≤ Y? Included?
(20,20) Yes Yes Yes
(20,20) Yes Yes Yes
(20,21) Yes, via (21,20) Yes Yes
(21,20) Yes, via (20,21) No No
(23,22) Yes, via (22,23) No No
(22,23) Yes, via (23,22) Yes Yes

After applying DISTINCT:

X Y
20 20
20 21
22 23

The final result is sorted by X, then Y.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Self joins and grouping dominate runtime, sorting contributes logarithmic cost
Space O(n) Database engine may allocate temporary storage for joins and sorting

The precise runtime depends on database optimizations and indexing. Without indexes, joins may approach quadratic behavior in practice. However, relational databases typically optimize joins efficiently, making this substantially faster than manual pairwise comparisons.

Test Cases

def symmetric_coordinates(rows):
    from collections import Counter

    count = Counter(rows)
    result = set()

    for x, y in rows:
        if (y, x) in count:
            if x < y:
                result.add((x, y))
            elif x == y and count[(x, y)] > 1:
                result.add((x, y))
            elif x > y and (y, x) in count:
                continue

    return sorted(result)

# Example case
assert symmetric_coordinates([
    (20, 20),
    (20, 20),
    (20, 21),
    (23, 22),
    (22, 23),
    (21, 20)
]) == [(20, 20), (20, 21), (22, 23)]  # Provided example

# Single self symmetric coordinate
assert symmetric_coordinates([
    (10, 10)
]) == []  # Needs duplicate occurrence

# Duplicate self symmetric coordinate
assert symmetric_coordinates([
    (10, 10),
    (10, 10)
]) == [(10, 10)]  # Valid self symmetry

# Regular symmetric pair
assert symmetric_coordinates([
    (1, 2),
    (2, 1)
]) == [(1, 2)]  # Keep only x <= y

# No symmetric pair
assert symmetric_coordinates([
    (1, 2),
    (3, 4)
]) == []  # No reverse coordinates

# Multiple duplicates
assert symmetric_coordinates([
    (1, 2),
    (2, 1),
    (1, 2),
    (2, 1)
]) == [(1, 2)]  # DISTINCT behavior

# Mixed cases
assert symmetric_coordinates([
    (5, 5),
    (5, 5),
    (6, 7),
    (7, 6),
    (9, 8)
]) == [(5, 5), (6, 7)]  # Combination test
Test Why
Provided example Verifies expected output
Single (x, x) Ensures one occurrence is insufficient
Duplicate (x, x) Validates self symmetry logic
(a,b) and (b,a) Confirms symmetric matching
No reverse pair Ensures invalid rows are excluded
Duplicate rows Verifies uniqueness using DISTINCT
Mixed dataset Tests multiple scenarios together

Edge Cases

Self Symmetric Coordinates Appearing Only Once

A coordinate such as (10,10) may seem symmetric because reversing it produces itself. However, the problem requires two coordinates to form a symmetric relationship. A single occurrence should not qualify.

This is a common bug source because a naive self join may accidentally match a row to itself. The implementation avoids this by requiring COUNT(*) > 1.

Duplicate Symmetric Pairs

The table may contain multiple copies of both (1,2) and (2,1). A naive implementation could output duplicates.

The solution handles this correctly with DISTINCT, ensuring each coordinate appears only once in the final result.

Mirrored Output Duplication

When (1,2) and (2,1) both exist, returning both would violate the uniqueness requirement.

The condition X <= Y guarantees only one representation survives. The smaller lexicographic ordering is consistently chosen, eliminating duplicates deterministically.