problemeasydatabaseleetcode-1623leetcode 1623leetcode1623

All Valid Triplets That Can Represent a Country

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

Problem

Table: SchoolA

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| student_id    | int     |
| student_name  | varchar |
+---------------+---------+
student_id is the column with unique values for this table.
Each row of this table contains the name and the id of a student in school A.
All student_name are distinct.

Table: SchoolB

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| student_id    | int     |
| student_name  | varchar |
+---------------+---------+
student_id is the column with unique values for this table.
Each row of this table contains the name and the id of a student in school B.
All student_name are distinct.

Table: SchoolC

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| student_id    | int     |
| student_name  | varchar |
+---------------+---------+
student_id is the column with unique values for this table.
Each row of this table contains the name and the id of a student in school C.
All student_name are distinct.

There is a country with three schools, where each student is enrolled in exactly one school. The country is joining a competition and wants to select one student from each school to represent the country such that:

  • member_A is selected from SchoolA,
  • member_B is selected from SchoolB,
  • member_C is selected from SchoolC, and
  • The selected students' names and IDs are pairwise distinct (i.e. no two students share the same name, and no two students share the same ID).

Write a solution to find all the possible triplets representing the country under the given constraints.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1:

Input: 
SchoolA table:
+------------+--------------+
| student_id | student_name |
+------------+--------------+
| 1          | Alice        |
| 2          | Bob          |
+------------+--------------+
SchoolB table:
+------------+--------------+
| student_id | student_name |
+------------+--------------+
| 3          | Tom          |
+------------+--------------+
SchoolC table:
+------------+--------------+
| student_id | student_name |
+------------+--------------+
| 3          | Tom          |
| 2          | Jerry        |
| 10         | Alice        |
+------------+--------------+
Output: 
+----------+----------+----------+
| member_A | member_B | member_C |
+----------+----------+----------+
| Alice    | Tom      | Jerry    |
| Bob      | Tom      | Alice    |
+----------+----------+----------+
Explanation: 
Let us see all the possible triplets.
- (Alice, Tom, Tom) --> Rejected because member_B and member_C have the same name and the same ID.
- (Alice, Tom, Jerry) --> Valid triplet.
- (Alice, Tom, Alice) --> Rejected because member_A and member_C have the same name.
- (Bob, Tom, Tom) --> Rejected because member_B and member_C have the same name and the same ID.
- (Bob, Tom, Jerry) --> Rejected because member_A and member_C have the same ID.
- (Bob, Tom, Alice) --> Valid triplet.

Solution

Method 1 – Using SQL Joins and Pairwise Distinct Checks

Intuition

The key idea is to generate all possible combinations of one student from each school, then filter out any triplet where two students share the same name or the same ID. Since all students are enrolled in only one school and names/IDs are unique within each school, we only need to check for pairwise distinctness across schools.

Approach

  1. Perform a cross join between SchoolA, SchoolB, and SchoolC to generate all possible triplets.
  2. For each triplet, ensure:
  • All three student_name values are distinct.
  • All three student_id values are distinct.
  1. Select the student_name from each school as member_A, member_B, and member_C.

Code

MySQL
SELECT
  a.student_name AS member_A,
  b.student_name AS member_B,
  c.student_name AS member_C
FROM
  SchoolA a
  CROSS JOIN SchoolB b
  CROSS JOIN SchoolC c
WHERE
  a.student_name <> b.student_name
  AND a.student_name <> c.student_name
  AND b.student_name <> c.student_name
  AND a.student_id <> b.student_id
  AND a.student_id <> c.student_id
  AND b.student_id <> c.student_id;

Complexity

  • ⏰ Time complexity: O(N_A * N_B * N_C) where N_A, N_B, N_C are the number of students in each school.
  • 🧺 Space complexity: O(1) (output space not counted).

Comments