LeetCode 1623 - All Valid Triplets That Can Represent a Country

The problem asks us to generate all valid triplets of students representing a country from three schools: SchoolA, Schoo

leetcodeeasydatabase

LeetCode Problem 1623

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem asks us to generate all valid triplets of students representing a country from three schools: SchoolA, SchoolB, and SchoolC. Each triplet consists of one student from each school, and the triplet is only valid if all three students have distinct names and distinct IDs.

The input consists of three database tables, each representing a school. Each table has unique student_id values and distinct student_name values within that school. There is no overlap of students across schools guaranteed, so the algorithm must check both name and ID collisions when forming triplets. The output is a list of valid triplets in any order, where each triplet contains the names of the students selected from SchoolA, SchoolB, and SchoolC.

Key constraints include:

  • Students are unique within a school.
  • A valid triplet requires pairwise distinct names and IDs.
  • The tables could be of varying sizes, so the solution should handle empty tables or tables with only one student correctly.

Important edge cases:

  • One or more schools having no students should produce no triplets.
  • Duplicate names or IDs across schools can disqualify many triplets.
  • Minimal input with only one student per school should be handled correctly if they are distinct.

Approaches

Brute Force

The brute force solution considers every combination of one student from each school. For each combination, it checks if all three names and all three IDs are distinct. If they are, the triplet is added to the result.

This approach is correct because it explicitly tests all possible triplets. However, its time complexity is $O(n \cdot m \cdot k)$ where n, m, and k are the sizes of SchoolA, SchoolB, and SchoolC, respectively. If each school has hundreds of students, this approach could generate millions of combinations, which may be inefficient.

Optimal Approach

Since we must check for pairwise uniqueness of both names and IDs across schools, there is no shortcut to completely avoid testing combinations. The brute-force combination approach is effectively optimal for correctness, but we can slightly optimize by filtering out students in one school who conflict with all students in another school before generating triplets. This reduces unnecessary checks but does not fundamentally change the complexity.

The key insight is that because the tables are generally not massive, generating all combinations and filtering by distinctness is both simple and efficient enough.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m * k) O(n * m * k) Check all triplets explicitly, filtering invalid ones.
Optimized Filtering O(n * m * k) O(n * m * k) Slight pre-filtering of conflicting students, still checks all triplets.

Algorithm Walkthrough

  1. Retrieve all students from SchoolA, SchoolB, and SchoolC.
  2. Initialize an empty result table for storing valid triplets.
  3. Iterate over each student from SchoolA as a.
  4. For each a, iterate over each student from SchoolB as b.
  5. Skip combinations where a.student_id == b.student_id or a.student_name == b.student_name.
  6. For each valid (a, b) pair, iterate over each student from SchoolC as c.
  7. Skip combinations where c conflicts with either a or b on student_id or student_name.
  8. If all three students are pairwise distinct in both ID and name, add (a.student_name, b.student_name, c.student_name) to the result.
  9. Return the result table.

Why it works: The algorithm explicitly checks all combinations and enforces the constraints on names and IDs. Because it tests every possible triplet, it guarantees that no valid triplet is missed and no invalid triplet is included.

Python Solution

# LeetCode uses SQL-style database problems, but we can simulate using Python
from typing import List, Dict

def all_valid_triplets(schoolA: List[Dict], schoolB: List[Dict], schoolC: List[Dict]) -> List[Dict]:
    result = []
    for a in schoolA:
        for b in schoolB:
            if a['student_id'] == b['student_id'] or a['student_name'] == b['student_name']:
                continue
            for c in schoolC:
                if (c['student_id'] in {a['student_id'], b['student_id']} or
                    c['student_name'] in {a['student_name'], b['student_name']}):
                    continue
                result.append({
                    'member_A': a['student_name'],
                    'member_B': b['student_name'],
                    'member_C': c['student_name']
                })
    return result

The implementation iterates over all combinations of students from the three schools. It uses simple if checks to enforce pairwise distinctness. The use of sets for checking c against (a, b) ensures correctness and readability.

Go Solution

package main

type Student struct {
    StudentID   int
    StudentName string
}

type Triplet struct {
    MemberA string
    MemberB string
    MemberC string
}

func AllValidTriplets(schoolA, schoolB, schoolC []Student) []Triplet {
    var result []Triplet
    for _, a := range schoolA {
        for _, b := range schoolB {
            if a.StudentID == b.StudentID || a.StudentName == b.StudentName {
                continue
            }
            for _, c := range schoolC {
                if c.StudentID == a.StudentID || c.StudentID == b.StudentID ||
                   c.StudentName == a.StudentName || c.StudentName == b.StudentName {
                    continue
                }
                result = append(result, Triplet{MemberA: a.StudentName, MemberB: b.StudentName, MemberC: c.StudentName})
            }
        }
    }
    return result
}

The Go implementation mirrors the Python logic. It uses slices for the input tables and a simple append for accumulating results. Go’s strong typing ensures we handle IDs and names explicitly without conversion.

Worked Examples

For the example in the problem statement:

a (SchoolA) b (SchoolB) c (SchoolC) Valid?
Alice Tom Tom No (name & ID conflict)
Alice Tom Jerry Yes
Alice Tom Alice No (name conflict)
Bob Tom Tom No (name & ID conflict)
Bob Tom Jerry No (ID conflict)
Bob Tom Alice Yes

Final result: [{"member_A":"Alice","member_B":"Tom","member_C":"Jerry"}, {"member_A":"Bob","member_B":"Tom","member_C":"Alice"}]

Complexity Analysis

Measure Complexity Explanation
Time O(n * m * k) Iterate over all combinations of students from three schools.
Space O(n * m * k) Store all valid triplets in the result list.

The algorithm’s time complexity is cubic relative to the number of students per school, but this is unavoidable for correctness without further constraints.

Test Cases

# Provided example
assert all_valid_triplets(
    [{'student_id': 1, 'student_name': 'Alice'}, {'student_id': 2, 'student_name': 'Bob'}],
    [{'student_id': 3, 'student_name': 'Tom'}],
    [{'student_id': 3, 'student_name': 'Tom'}, {'student_id': 2, 'student_name': 'Jerry'}, {'student_id': 10, 'student_name': 'Alice'}]
) == [
    {'member_A': 'Alice', 'member_B': 'Tom', 'member_C': 'Jerry'},
    {'member_A': 'Bob', 'member_B': 'Tom', 'member_C': 'Alice'}
]

# Edge case: one school empty
assert all_valid_triplets([], [{'student_id': 1, 'student_name': 'A'}], [{'student_id': 2, 'student_name': 'B'}]) == []

# Single valid triplet
assert all_valid_triplets([{'student_id': 1, 'student_name': 'X'}],
                          [{'student_id': 2, 'student_name': 'Y'}],
                          [{'student_id': 3, 'student_name': 'Z'}]) == [
                              {'member_A': 'X', 'member_B': 'Y', 'member_C': 'Z'}
                          ]

# Conflicting names across schools
assert all_valid_triplets([{'student_id': 1, 'student_name': 'X'}],
                          [{'student_id': 2, 'student_name': 'X'}],
                          [{'student_id': 3, 'student_name': 'Y'}]) == []
Test Why
Provided example Validates normal operation with multiple valid triplets
One school empty Ensures algorithm returns empty result when impossible
Single valid triplet Checks minimal non-empty case
Conflicting names Ensures name collisions across schools are handled

Edge Cases

  1. Empty schools: If any school table is empty, no triplets can be formed. The implementation naturally handles this because the loops will never enter the iteration for an empty list, returning an empty