Magical usage of Bitwise operators - Get optimized solutions for many arithmatic problems
Introduction I will list some of the interesting usage of bitwise operators…
September 03, 2020
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
Its a simple solution where we need to verify on two parts:
3x3
board inside the big 9x9
board for the unique value.
//char[][] board
for (int i=0; i<board[0].length; i++) {
boolean checkRow[] = new boolean[9];
boolean checkCol[] = new boolean[9];
for (int j=0; j<board.length; j++) {
if (board[i][j] != '.') {
//check row
if (checkRow[board[i][j] - '1']) {
return false;
}
else {
checkRow[board[i][j] - '1'] = true;
}
}
if (board[j][i] != '.') {
//check col
if (checkCol[board[j][i] - '1']) {
return false;
}
else {
checkCol[board[j][i] - '1'] = true;
}
}
}
}
See the image below for more understanding:
Lets look at the code:
//char[][] board
for (int i=0; i<board[0].length; i+=3) {
for (int j=0; j<board.length; j+=3) {
boolean check3x3[] = new boolean[9];
for (int k=i; k<i+3; k++) {
for (int l=j; l<j+3; l++) {
if (board[k][l] == '.') continue;
if (check3x3[board[k][l] - '1']) {
return false;
}
else {
check3x3[board[k][l] - '1'] = true;
}
}
}
}
}
public boolean isValidSudoku(char[][] board) {
for (int i=0; i<board[0].length; i++) {
boolean checkRow[] = new boolean[9];
boolean checkCol[] = new boolean[9];
for (int j=0; j<board.length; j++) {
if (board[i][j] != '.') {
//check row
if (checkRow[board[i][j] - '1']) {
return false;
}
else {
checkRow[board[i][j] - '1'] = true;
}
}
if (board[j][i] != '.') {
//check col
if (checkCol[board[j][i] - '1']) {
return false;
}
else {
checkCol[board[j][i] - '1'] = true;
}
}
}
}
for (int i=0; i<board[0].length; i+=3) {
for (int j=0; j<board.length; j+=3) {
boolean check3x3[] = new boolean[9];
for (int k=i; k<i+3; k++) {
for (int l=j; l<j+3; l++) {
if (board[k][l] == '.') continue;
if (check3x3[board[k][l] - '1']) {
return false;
}
else {
check3x3[board[k][l] - '1'] = true;
}
}
}
}
}
return true;
}
The complexity is O(mxn)
We are iterating over whole matrix 2 times. If you are confused for last loop where you can see three nested loops. We are actually iterating over matrix only once.
Runtime: 1 ms, faster than 100.00% of Java online submissions for Valid Sudoku.
Memory Usage: 39.5 MB, less than 80.98% of Java online submissions for Valid Sudoku.
Introduction I will list some of the interesting usage of bitwise operators…
Problem Statement Given a non-empty array of digits representing a non-negative…
Counting sort runs on relatively smaller set of input. Counting sort calculates…
Problem Statement Determine whether an integer is a palindrome. An integer is a…
This algorithm is very efficient one, and is classic example of Divide and…
A Binary tree is a data structure which has two children nodes attached to it…
In this post, we will see some of the frequently used concepts/vocabulary in…
System design interview is pretty common these days, specially if you are having…
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement Given an array nums of n integers and an integer target, are…