[Amazon Question][LeetCode] Valid Sudoku

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.

Example:

Input: (Above image)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 = 
[["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.

Approach: We can use three hashsets here to validate if a number is repeated in the same row or column or in the box. The only problem here is how to calculate the box index. Here is how we can get it:

box_index = (row / 3) * 3 + col / 3

 That's all!

Implementation in C#:

    public bool IsValidSudoku(char[][] board)

    {

        HashSet<char>[] rowNums = new HashSet<char>[9];

        HashSet<char>[] colNums = new HashSet<char>[9];

        HashSet<char>[] boxNums = new HashSet<char>[9];

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

        {

            rowNums[i] = new HashSet<char>();

            colNums[i] = new HashSet<char>();

            boxNums[i] = new HashSet<char>();

        }

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

        {

            for (int j = 0; j < 9; ++j)

            {

                char num = board[i][j];

                if (num != '.')

                {

                    int boxIndex = (i / 3) * 3 + j / 3;                    

                    if (!rowNums[i].Add(num) ||

                        !colNums[j].Add(num) ||

                        !boxNums[boxIndex].Add(num))

                    {

                        return false;

                    }

                }

            }

        }        

        return true;    

    }

Complexity: O(n^2) where n is number of rows and column. We can say it is constant complexity too as n is always 9 here.