Valid Sudoku

Valid Sudoku

What is this problem about?

The "Valid Sudoku" interview question asks you to validate a 9x9 Sudoku board. You only need to check if the currently filled cells follow the three Sudoku rules: each row must contain the digits 1-9 without repetition, each column must contain digits 1-9 without repetition, and each of the nine 3x3 sub-boxes must contain digits 1-9 without repetition. You do NOT need to solve the Sudoku.

Why is this asked in interviews?

This "Valid Sudoku" coding problem is a favorite at companies like Uber, Microsoft, and Meta. It tests your ability to manipulate 2D arrays (matrices) and use hash sets or boolean arrays to track seen values. It's an excellent measure of a candidate's ability to translate multi-part rules into efficient code.

Algorithmic pattern used

The primary pattern is the "Matrix/Hash Table interview pattern." You iterate through the 9x9 board once. For each cell that contains a digit, you record its presence in three sets: one for its row, one for its column, and one for its 3x3 box. If you try to add a digit to a set where it already exists, the board is invalid.

Example explanation

Suppose we encounter digit '5' at row 0, column 2.

1. Check row 0 set: '5' not present. Add it.
2. Check column 2 set: '5' not present. Add it.
3. Determine box index: (row/3) * 3 + (col/3). For (0,2), the box index is 0*3 + 0 = 0.
4. Check box 0 set: '5' not present. Add it.
5. If we later find another '5' in row 0, column 5, the "row 0 set" will already have '5', and we return false.

Common mistakes candidates make

One common mistake is overcomplicating the box index calculation. Another is using 27 different sets (9 for rows, 9 for cols, 9 for boxes) and not organizing them efficiently, leading to messy code. Candidates also sometimes forget that empty cells (often denoted by '.') should be ignored.

Interview preparation tip

To write high-quality code for the "Valid Sudoku" coding problem, try using a single set of strings like "row_0_digit_5", "col_2_digit_5", and "box_0_digit_5". While using separate boolean arrays might be slightly faster, the string-based set approach is very readable and often easier to implement quickly during an interview.