Algorithm to Determine a Latin Square using a Hash Table

Given an N by N matrix of letters matrix, return whether there are exactly N different letters that appear in the matrix and each letter appears exactly once in each row and exactly once in each column.

Example 1
Input

1 2 3 4 5

matrix = [     ["a", "b", "c"],     ["c", "a", "b"],     ["b", "c", "a"] ]

matrix = [
    ["a", "b", "c"],
    ["c", "a", "b"],
    ["b", "c", "a"]
]

Output
true
Explanation
There are 3 different letters and each letter appears exactly once in each row and column.

Example 2
Input

1 2 3 4 5

matrix = [     ["a", "b", "c"],     ["d", "a", "a"],     ["b", "b", "a"] ]

matrix = [
    ["a", "b", "c"],
    ["d", "a", "a"],
    ["b", "b", "a"]
]

Output
false
Explanation
There are 4 different letters, and also “a” and “b” appear twice in the same row.

Check if a Matrix is a Latin Square using a Hash Table

So there are three requirements for a matrix/square to be a Latin Square. The number of unique elements should be exactly N. The number of unique elements in each row should be N, and the number of distinct elements in each column is also N.

Therefore, we can use three hash tables to store the unqiue numbers and then check each column, row and all respectively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

bool solve(vector<vector<string>>& matrix) {
    int rows = matrix.size();
    if (0 == rows) return 0;
    int cols = matrix[0].size();
    vector<unordered_set<char>> r(rows);
    vector<unordered_set<char>> c(cols);
    unordered_set<char> all;
    for (int i = 0; i < rows; ++ i) {
        for (int j = 0; j < cols; ++ j) {
            r[i].insert(matrix[i][j][0]);
            c[j].insert(matrix[i][j][0]);
            all.insert(matrix[i][j][0]);
        }
    }
    for (int i = 0; i < rows; ++ i) {
        if (r[i].size() != rows) {
            return false;
        }
    }
    for (int i = 0; i < cols; ++ i) {
        if (c[i].size() != cols) {
            return false;
        }
    }
    return all.size() == rows;
}

bool solve(vector<vector<string>>& matrix) {
    int rows = matrix.size();
    if (0 == rows) return 0;
    int cols = matrix[0].size();
    vector<unordered_set<char>> r(rows);
    vector<unordered_set<char>> c(cols);
    unordered_set<char> all;
    for (int i = 0; i < rows; ++ i) {
        for (int j = 0; j < cols; ++ j) {
            r[i].insert(matrix[i][j][0]);
            c[j].insert(matrix[i][j][0]);
            all.insert(matrix[i][j][0]);
        }
    }
    for (int i = 0; i < rows; ++ i) {
        if (r[i].size() != rows) {
            return false;
        }
    }
    for (int i = 0; i < cols; ++ i) {
        if (c[i].size() != cols) {
            return false;
        }
    }
    return all.size() == rows;
}

The complexity is O(N^2) where N is the dimension of the square. And the space requirement is also O(N^2) as in the worst case, there could be N^2 unique elements in the square.

–EOF (The Ultimate Computing & Technology Blog) —