### 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:

- Each row must contain the digits 1-9 without repetition.
- Each column must contain the digits 1-9 without repetition.
- Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Its a simple solution where we need to verify on two parts:

- Each row and column must have unique value (1-9).
- Each
`3x3`

board inside the big`9x9`

board for the unique value.

- We can iterate over matrix and can check a row and column in one iteration pass. Let me try to depict it in the form of some images:

- So in first iteration, we will cover single row and single column like this.
- After first iteration, complete matrix will be checked.
- We need to keep track of values for each row and col, for one iteration. So that, we can check if we got a same number or not.
- We can have an array of length-9, since we have numbers from 1-9. Index-0 will be kept unused.

```
//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;
}
}
}
}
```

- Similarly, while iterating over matrix. We need to check for each 3x3 matrix.

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…

Introduction You are given an array of integers with size N, and a number K…

Problem Statement The string “PAYPALISHIRING” is written in a zigzag pattern on…

Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…

Problem Statement Write a function that reverses a string. The input string is…

Problem Statement Given a string, find the length of the longest substring…

Introduction Lets assume we have a csv something similar to following: Python…

Introduction In last post, we saw How to read CSV with Headers into Dictionary…

Introduction Power BI is a wonderful tool to give life to your data, by…

Problem Statement You are given an array prices where prices[i] is the price of…

Introduction In this post we will see: How to prepare a docker image for your…

Introduction We have a page, for example a . And, upon submission we would want…