C++ Solution using 3 Hash tables


#1

The idea is to use three different hash tables for row, column and sector.

int Solution::isValidSudoku(const vector<string> &A) {
    unordered_map<int, unordered_set<char>> row, col, sec;
    for(int i=0; i<A.size(); i++){
        for(int j=0; j<A[i].length(); j++){
            if(A[i][j] != '.'){
                if(row[i].find(A[i][j]) != row[i].end() || col[j].find(A[i][j]) != col[j].end())
                    return 0;
                int s = (j/3)+10*(i/3);
                if(sec[s].find(A[i][j]) != sec[s].end())
                    return 0;
                row[i].insert(A[i][j]);
                col[j].insert(A[i][j]);
                sec[s].insert(A[i][j]);
            }
        }
    }
    row.clear(); col.clear(); sec.clear();
    return 1;
}

#2

hii your solution is really good .
can you please tell me about this…

int s = (j/3)+10*(i/3);

how many sectors did you make and how did you come up with this formula.


#3

Hey, the formula is just to differentiate between the nine sectors. Multiplying it either i/3 or j/3 will give a different result for the sectors.


#4

Nice Solution . Specially the sector formula.


#5

Even i liked your approach, especially the sector logic


#6

Kinda same logic but different approach

int Solution::isValidSudoku(const vector &A) {

set<pair<char,int>> s1;
set<pair<char,int>> s2;
set<pair<char,int>> s3;
int c=0;
for(int i=0;i<A.size();i++)
{
    for(int j=0;j<A[i].size();j++)
    {
        if(A[i][j]!='.')
        {
            s1.insert({A[i][j],i});
            s2.insert({A[i][j],j});
            int k=i/3 + 3*(j/3);
            s3.insert({A[i][j],k});
            c++;
        }
    }
}
if(s1.size()==s2.size() && s1.size()==s3.size() && s1.size()==c)
    return 1;

return 0;    

}


#7

Whats the point of using hash table here when we have to map only integers from 1 to 9, multi-dimensional arrays are sufficient.


#8

OP bro great solution hats off to you