Maximum Length of Subarray With Positive Product - Leet Code Solution
Problem Statement Maximum Length of Subarray With Positive Product. Given an…
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.
Problem Statement Maximum Length of Subarray With Positive Product. Given an…
Problem Statement Given an array of integers, find if the array contains any…
Problem Statement Given a sorted array nums, remove the duplicates in-place such…
Problem Statement Implement atoi which converts a string to an integer…
Problem Statement Given a string s, return the maximum number of unique…
This problem is a simple mathematical calculation. Lets start deriving some…
Introduction Strapi is a backend system provides basic crud operations with…
Introduction I had to create many repositories in an Github organization. I…
Introduction I was trying to download some youtube videos for my kids. As I have…
Introduction In this post, we will explore some useful command line options for…
Introduction In this post, we will see how we can apply a patch to Python and…
Introduction We will introduce a Package Manager for Windows: . In automations…