# Validate Sudoku - Leet Code Solution

September 03, 2020

## Problem Statement

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.

## Solution

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.

### Check for each Row and Column

• 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.

### Code Snippet for this

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

### Check for each 3x3 matrix

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

## Final Code

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

## Complexity

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.

## Leet code submission result

``````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.
``````

## Similar Posts

### Min Priority Queue Implementation with Heap Data structure

Min Priority Queue is a data structure which manage a list of keys(values). And…

### Remove Duplicates from Sorted Array - Leet Code Solution

Problem Statement Given a sorted array nums, remove the duplicates in-place such…

### Longest Substring without repeating characters - Leet Code Solution

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

### Remove nth Node from Last - Leet Code Solution

Problem Statement Given a linked list, remove the n-th node from the end of list…

### Rotate Array - Leet Code Solution

Problem Statement Given an array, rotate the array to the right by k steps…

### Reverse digits of a signed integer - Leet Code Solution

Problem Statement Given a signed integer, reverse digits of an integer. Return…

## Latest Posts

### Jenkins Pipeline with Jenkinsfile - How To Schedule Job on Cron and Not on Code Commit

Introduction In this post we will see following: How to schedule a job on cron…

### How to Git Clone Another Repository from Jenkin Pipeline in Jenkinsfile

Introduction There are some cases, where I need another git repository while…

### How to Fetch Multiple Credentials and Expose them in Environment using Jenkinsfile pipeline

Introduction In this post, we will see how to fetch multiple credentials and…

### Jenkins Pipeline - How to run Automation on Different Environment (Dev/Stage/Prod), with Credentials

Introduction I have an automation script, that I want to run on different…

### Jenkinsfile - How to Create UI Form Text fields, Drop-down and Run for Different Conditions

Introduction I had to write a CICD system for one of our project. I had to…

### Java Log4j Logger - Programmatically Initialize JSON logger with customized keys in json logs

Introduction Java log4j has many ways to initialize and append the desired…