Leetcode 36: Valid Sudoku - Cse Nerd Leetcode Detailed Solutions

Category: Medium

Problem

Determine if a 9 x 9 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 nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

https://leetcode.com/problems/valid-sudoku/

Examples

Example 1:

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"]]
Output: true

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"]]

Output: true

Example 2:

Input: board = 
[["8","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"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Input: board =

[["8","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"]]

Output: false

Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints

board.length == 9
board[i].length == 9
board[i][j] is a digit or '.'.

Solution Approach

In this problem, we have to determine that random 9 rows and 9 columns are of valid sudoku or not. Valid sudoku has non-repeating numbers in every row, column and 3*3 sub-block.

The approach to solving this problem is pretty straight forward, we just have to determine if all the cells follow sudoku’s rules or not. Even if one cell doesn’t comply with the rule we have will return that the sudoku in the problem is not valid. There are 81 cells to check and this checking will be done cell by cell in a matrix hence the complexity is O(n^2).

Now to the solution of the problem, we iterate each row and check for the validity in a row, column and sub-block manner.

For achieving this we can use a helper method in our case isValid method. Inside the method, we initialise an array of 9 boolean variables. Then we start checking each cell and if they don’t contain .(period) then we have to check if that number is already present in the boolean array and if it is present then we straightaway return false. If the number is not present in the array then we mark that position as visited or true so that if we encounter it next time we can return false. At the end when all the elements are unique we return true to the main method.

If we encounter any false response from any helper method then I straightaway return false without checking any further.

Solution code

class Solution {
  public boolean isValidSudoku(char[][] board) {
    for (int i = 0; i < 9; i++) {
      if (!isValid(board, i, i, 0, 8)) return false;
      if (!isValid(board, 0, 8, i, i)) return false;
      if (!isValid(board, (i / 3) * 3, (i / 3) * 3 + 2, (i % 3) * 3, (i % 3) * 3 + 2)) return false;
    }
  return true;
  }

  public boolean isValid(char[][] board, int rStart, int rEnd, int cStart, int cEnd){
    boolean[] contain = new boolean[9];
    for (int row = rStart; row <= rEnd; row++) {
      for (int col = cStart; col <= cEnd; col++) {
        char c = board[row][col];
          if(c != '.'){
            if(contain[c - '1']) return false;
            else contain[c - '1'] = true;
        }
      }
    }
  return true;
  }
}

class Solution {

public boolean isValidSudoku(char[][] board) {

for (int i = 0; i < 9; i++) {

if (!isValid(board, i, i, 0, 8)) return false;

if (!isValid(board, 0, 8, i, i)) return false;

if (!isValid(board, (i / 3) * 3, (i / 3) * 3 + 2, (i % 3) * 3, (i % 3) * 3 + 2)) return false;

}

return true;

}

public boolean isValid(char[][] board, int rStart, int rEnd, int cStart, int cEnd){

boolean[] contain = new boolean[9];

for (int row = rStart; row <= rEnd; row++) {

for (int col = cStart; col <= cEnd; col++) {

char c = board[row][col];

if(c != '.'){

if(contain[c - '1']) return false;

else contain[c - '1'] = true;

}

return true;

}

For more Leetcode explained solutions visit Leetcode Solutions.

If you like capture the flag challenges visit here.

For Computer Science Quotes visit here and for more computer science-related topic visit my blog on Computer Science.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via Contact page I will surely respond. Happy Leetcoding 🙂