Valid Sudoku

MEDIUM

Description

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.

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

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.

Constraints:

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

Approaches

Checkout 3 different approaches to solve Valid Sudoku. Click on different approaches to view the approach and algorithm in detail.

Grouped Validation (Rows, Columns, and Boxes)

This approach improves upon the brute-force method by validating all rows, then all columns, and finally all 3x3 sub-boxes in separate phases. This avoids the redundant checks of the previous method.

Algorithm

Validate Rows:
- For each row i from 0 to 8:
  - Use a HashSet to track seen digits.
  - Iterate through the row. If a digit is already in the set, return false. Otherwise, add it.
Validate Columns:
- For each column j from 0 to 8:
  - Use a new HashSet.
  - Iterate through the column. If a digit is already in the set, return false. Otherwise, add it.
Validate Sub-boxes:
- For each of the 9 sub-boxes:
  - Use a new HashSet.
  - Iterate through the 3x3 cells of the box. If a digit is already in the set, return false. Otherwise, add it.
If all checks pass, return true.

The validation is split into three distinct parts:

Row Validation: Iterate through each of the 9 rows. For each row, use a HashSet (or a boolean array) to keep track of the digits encountered. If a digit is seen more than once in the same row, the board is invalid.
Column Validation: Similarly, iterate through each of the 9 columns. Use a fresh HashSet for each column to check for duplicate digits.
Sub-box Validation: Iterate through each of the 9 3x3 sub-boxes. A HashSet is used for each sub-box to ensure no digit is repeated within it. The sub-boxes can be traversed by iterating their top-left corners, e.g., (0,0), (0,3), (0,6), .... If all three validation phases complete successfully, the board is valid. This method processes each cell three times in total.

import java.util.HashSet;
import java.util.Set;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // Check rows
        for (int i = 0; i < 9; i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                char current = board[i][j];
                if (current != '.') {
                    if (seen.contains(current)) {
                        return false;
                    }
                    seen.add(current);
                }
            }
        }

        // Check columns
        for (int j = 0; j < 9; j++) {
            Set<Character> seen = new HashSet<>();
            for (int i = 0; i < 9; i++) {
                char current = board[i][j];
                if (current != '.') {
                    if (seen.contains(current)) {
                        return false;
                    }
                    seen.add(current);
                }
            }
        }

        // Check 3x3 sub-boxes
        for (int boxRow = 0; boxRow < 3; boxRow++) {
            for (int boxCol = 0; boxCol < 3; boxCol++) {
                Set<Character> seen = new HashSet<>();
                int startRow = boxRow * 3;
                int startCol = boxCol * 3;
                for (int i = startRow; i < startRow + 3; i++) {
                    for (int j = startCol; j < startCol + 3; j++) {
                        char current = board[i][j];
                        if (current != '.') {
                            if (seen.contains(current)) {
                                return false;
                            }
                            seen.add(current);
                        }
                    }
                }
            }
        }

        return true;
    }
}

Complexity Analysis

Time Complexity: O(N^2)Space Complexity: O(N)

Pros and Cons

Pros:

Much more efficient than brute force with O(N^2) time complexity.
Code is well-structured and easy to follow.
Space efficient, using O(N) extra space.

Cons:

Iterates over the board three times, which can be slightly less performant than a single-pass approach due to loop overhead and potentially worse cache performance.

Code Solutions

Checking out 4 solutions in different languages for Valid Sudoku. Click on different languages to view the code.

class Solution { public boolean isValidSudoku ( char [][] board ) { boolean [][] row = new boolean [ 9 ][ 9 ]; boolean [][] col = new boolean [ 9 ][ 9 ]; boolean [][] sub = new boolean [ 9 ][ 9 ]; for ( int i = 0 ; i < 9 ; ++ i ) { for ( int j = 0 ; j < 9 ; ++ j ) { char c = board [ i ][ j ]; if ( c == '.' ) { continue ; } int num = c - '0' - 1 ; int k = i / 3 * 3 + j / 3 ; if ( row [ i ][ num ] || col [ j ][ num ] || sub [ k ][ num ]) { return false ; } row [ i ][ num ] = true ; col [ j ][ num ] = true ; sub [ k ][ num ] = true ; } } return true ; } }

Video Solution

Watch the video walkthrough for Valid Sudoku

Data Structures:

ArrayHash TableMatrix

Companies:

Adobe |Amazon |Apple |Bloomberg |