Given a board of size 9 * 9 representing a sudoku game , find out if it is valid.
It is valid if :
- Each row contains elements from 1 to 9 and they are not repeated
- Each column contains elements from 1 to 9 and they are not repeated
- Each box contains elements from 1 to 9 and they are not repeated
For example,
The below sudoku:
represented by the array:
Input: board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[".","9","8",".",".",".",".","6","."] ,["8",".",".",".","6",".",".",".","3"] ,["4",".",".","8",".","3",".",".","1"] ,["7",".",".",".","2",".",".",".","6"] ,[".","6",".",".",".",".","2","8","."] ,[".",".",".","4","1","9",".",".","5"] ,[".",".",".",".","8",".",".","7","9"]]
is valid since it obeys all the three conditions.
Try out the solution here:
https://leetcode.com/problems/valid-sudoku/
Solution:
Approach 1 : Using Hash Set
You can iterate through each row or column using for loops.
While doing so you can validate if the same element is present in the same row or column or not.
This is fairly straightforward.
Use a set to store the elements along a single row and another to store the elements along a single column.
Each time you scan an element add that to the corresponding row and column.
If it already contains that element return false.
We will use a set instead of a list because searching for an element in a set is faster compared to list.
Here is the check for the rows and columns:
Set<Character> rows = new HashSet<>();
Set<Character> columns = new HashSet<>();
for(int i=0;i<9;i++){
rows.clear();
columns.clear();
for(int j=0;j<9;j++){
char row = board[i][j];
char col = board[j][i];
if(row != '.'){
if(rows.contains(row)) return false;
rows.add(row);
}
if(col != '.'){
if(columns.contains(col)) return false;
columns.add(col);
}
}
}
As you see for horizontal scanning (scanning the rows) we check board[i][j]
And for vertical scanning (scanning the columns we interchange i and j – board[j][i].
We can do horizontal and vertical scanning at the same time !
And at the start of each scan we clear the rows and columns so that we can start a fresh check (check those elements in that particular row or column).
We also make sure that we are not considering dot ( . ) character.
The difficulty arises when we check if a particular box contains duplicate elements or not.
For this we will assign the rows and columns into separate boxes.
We can use the below formula for that:
boxNo = (rowNo /3) * 3 + (colNo/3)
So if the row no is 0 and the column no is 0 , then it will be part of box 0.
boxNo = (0/3) * 3 + (0/3) = 0
If row no is 8 and column no is 8 , then it will be part of box 8.
boxNo = (8/3) * 3 + (8/3) = 6 + 2 = 8
This formula takes care of assigning the rows and columns into the appropriate box.
Now we just need to check if that box contains duplicates by adding the values to the corresponding box.
Here is the code:
Set<Character>[] groups = new HashSet[9];
if(board[i][j] != '.'){
int box = ( i / 3 ) * 3 + (j / 3);
if(groups[box] == null){
groups[box] = new HashSet<>();
}
if(groups[box].contains(board[i][j])) return false;
groups[box].add(board[i][j]);
}
To validate the boxes you create an array of set , for each box.
So for each character ,
You check the box no.
Then you check if the character already exists in the box , if so you return false.
Else you add the character to the particular box.
Here is the entire code:
class Solution {
public boolean isValidSudoku(char[][] board) {
Set<Character> rows = new HashSet<>();
Set<Character> columns = new HashSet<>();
Set<Character>[] groups = new HashSet[9];
for(int i=0;i<9;i++){
rows.clear();
columns.clear();
for(int j=0;j<9;j++){
char row = board[i][j];
char col = board[j][i];
if(row != '.'){
if(!rows.add(row)) return false;
}
if(col != '.'){
if(!columns.add(col)) return false;
}
if(board[i][j] != '.'){
int box = ( i / 3 ) * 3 + (j / 3);
if(groups[box] == null){
groups[box] = new HashSet<>();
}
if(!groups[box].add(row)) return false;
}
}
}
return true;
}
}
Time complexity:
We iterate through each element in each row and column so time complexity is O(n2 )
Space complexity:
We use a set of size n to store the rows
a set of size n to store the columns
an array of size n , whose each element contains a set of size n , so time complexity is O(n2)
Approach 2: Using Bitmasking
In this approach,
We will use the bits of an integer to indicate whether a number is present in a row /column/box or not.
We will use three integer arrays, one for representing the 9 rows,
One for representing the 9 columns,
And one for representing the 9 boxes.
Each integer in the array represents one row/column/box.
So if number 1 is present in a row we will set the first bit in the integer (index 0), number 2 means second bit ( index 1) and so on for the 9 numbers(up to index 8)
To check if a number is already present, we will just check if the corresponding bit is already set or not.
How to validate ?
We will do & operation between the integer representing the row/column/box and number one shifted left by the index position of the number.
int c = board[i][j] - 1;// we do -1 because index starts from 0
int pos = 1 << c; //left shift number 1 by the index position
if((rows[i] & pos) > 0) return false;
How to set a bit ?
By doing OR operation between the integer representing the row/column/box and the number one left shifted by the index position of the number
rows[i] |= pos;
Here is the entire code:
class Solution {
public boolean isValidSudoku(char[][] board) {
int[] rows = new int[9];
int[] cols = new int[9];
int[] boxes = new int[9];
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j] != '.'){
int c = board[i][j] - 1;
int pos = 1 << c;
if((rows[i] & pos) > 0) return false;
rows[i] |= pos;
if((cols[j] & pos) > 0 ) return false;
cols[j] |= pos;
int box = (i/3) * 3 + (j/3);
if((boxes[box] & pos) > 0) return false;
boxes[box] |= pos;
}
}
}
return true;
}
}
Time complexity:
We iterate through all the elements in the board , so time complexity is O(n2)
Space complexity:
We use an integer array of size n for the rows/columns and boxes.
So space complexity is O(3n) which is O(n)
that’s it!
Leave a Reply