All Valid Triplets That Can Represent a Country - Video Solutions
Leetcode 1623 - All Valid Triplets - Easiest Solution - Solved & Explained by Everyday Data Science
All Valid Triplets That Can Represent a Country - Video Solution
Watch 3 video solutions for All Valid Triplets That Can Represent a Country, a easy level problem involving Database. This walkthrough by Everyday Data Science has 719 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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_Ais selected fromSchoolA,member_Bis selected fromSchoolB,member_Cis selected fromSchoolC, 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.
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.
Approach Overview
Problem Overview: You are given three tables representing schools (SchoolA, SchoolB, and SchoolC). Each row stores how many students a school can send to represent a country. The goal is to list every triplet of schools (one from each table) whose combined student count does not exceed the allowed country limit.
Approach 1: Filtered CROSS JOIN (O(A Ă— B Ă— C) time, O(1) space)
The straightforward way is to generate every possible triplet of schools and then filter out the combinations that violate the student limit. In SQL, this is naturally expressed using a CROSS JOIN. A cross join pairs each row from SchoolA with every row from SchoolB and every row from SchoolC, producing all possible combinations. After generating these combinations, apply a WHERE condition to keep only rows where a.student_count + b.student_count + c.student_count is within the allowed limit.
This approach works because the problem explicitly requires evaluating combinations across three independent tables. SQL engines are optimized for join operations, so expressing the logic with joins keeps the query concise and readable. Each resulting row directly represents one valid triplet that can represent the country.
The time complexity is O(A Ă— B Ă— C) because every row in SchoolA is paired with every row in SchoolB and SchoolC. Space complexity is O(1) for the query itself since the database engine streams results without requiring additional data structures in the query logic. In practice, performance depends on table sizes and the database optimizer.
Implementation typically selects the identifiers from each table while applying the constraint directly in the WHERE clause. The structure looks like:
SELECT a.school_id, b.school_id, c.school_id FROM SchoolA a CROSS JOIN SchoolB b CROSS JOIN SchoolC c WHERE a.student_count + b.student_count + c.student_count <= limit;
This pattern—generate combinations and filter—is common in SQL and database interview problems where multiple independent datasets must be combined. Understanding how joins expand rows is the key insight.
Recommended for interviews: The filtered CROSS JOIN approach is exactly what interviewers expect. The problem mainly tests whether you recognize that each table contributes one element of the triplet and that SQL joins can generate combinations. Once you form the cross join, the constraint becomes a simple arithmetic filter. The logic is short, expressive, and aligns with how relational databases are designed to handle combinational queries.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Filtered CROSS JOIN | O(A Ă— B Ă— C) | O(1) | Standard SQL solution when you must evaluate all combinations across three independent tables |
| JOIN with WHERE Constraint | O(A Ă— B Ă— C) | O(1) | When writing production SQL where readability matters; logically identical to cross join but expressed with explicit filters |