NeetCode 150: Valid Sudoku

Table of contents

The Problem

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.

2. Each column must contain the digits 1-9 without repetition.

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

A Visual Example

Image taken from LeetCode.

The Approach

The goal is to “log” every filled entry, along with its position in its respective row, column, & 3 x 3 sub-box.

I had attempted to do this iteratively, by checking each 3 x 3 sub-box using nested for-loop, but it sadly became too complex.

However, a better approach I found is to log each filled entry using a Set as each number can only appear once in a row, column, & 3 x 3 sub-box (thus unique).

My Solution

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // Create a HashSet to store "seen" values.
        Set seen = new HashSet();

        // Loop over all values in the board.
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char character = board[i][j];
                
                // If the char is not unfilled (ie: '.'), add this to the HashSet as a string which includes the row, column & block it was seen in.
                // Note: Each 3x3 sub-box can be identified by its unique top-left coordinate, by dividing the current set of coordinates by 3.
                if (character != '.') {
                    boolean rowAddResult = seen.add(character + " in row " + i);
                    boolean colAddResult = seen.add(character + " in column " + j);
                    boolean blockAddResult = seen.add(character + " in block: " + (i/3) + "," + (j/3));
                    
                    // If the above returns false, means that it is already present & the board is invalid.
                    if (!(rowAddResult) || !(colAddResult) || !(blockAddResult)) {
                        return false;
                    }
            }
            }
        }
        return true;
    }
}

Firstly, we initialize seen which is a HashSet.

We then loop over every entry in the 2D sudoku array. For each character we “log” (by inserting a String) into seen using the boolean add(E e) method, which returns false if it was already present in the Set;

• The row it was filled in.
• The column it was filled in.
• The 3 x 3 sub-box it was filled in, by logging the x & y coordinate (row and column number) of its 3 x 3 sub-box.

After collating the boolean values for each insertion, we check if any of them returned false (i.e. present in seen), which means it is an invalid Sudoku board (thus false is returned).

If every entry is unique, (i.e. no false is returned for any of the checks), true is returned.