AlgoMaster Logo

Valid Sudoku

mediumFrequencyUpdated August 29, 2026

Understanding the Problem

We have a 9x9 Sudoku grid, and we need to check whether the current state of the board violates any of the three Sudoku rules. We are not solving the puzzle or checking if it can be solved. We only verify that no digit appears twice in the same row, the same column, or the same 3x3 sub-box.

The board may have empty cells (represented by '.'), and those are ignored. The question is whether, among the filled cells, any digit repeats inside a row, a column, or a box.

The 3x3 sub-box check needs more care than the other two. Rows and columns are indexed directly by r and c, but each box covers a 3x3 block of cells, so we need a way to map a cell at (r, c) to the box that contains it.

Key Constraints

  • board.length == 9 and board[i].length == 9 means the board is always a fixed 9x9 grid, so there are always 81 cells. The input size is a constant, which means every approach below has the same asymptotic cost. The comparison between them is about practical overhead and code clarity, not Big-O.
  • board[i][j] is a digit 1-9 or '.', so we never have to handle invalid characters. Empty cells are marked with '.'.

Approach 1: Three Separate Passes

Intuition

Validate each constraint on its own. First scan every row and confirm no digit repeats, then scan every column, then scan every 3x3 sub-box. This matches how a person checks a Sudoku board by hand: read across one row looking for a repeat, move to the next row, and later repeat the process for columns and boxes.

To detect a repeat inside a single row, we walk the row and keep a set of digits seen so far. If a digit is already in the set when we reach it, the row has a duplicate and the board is invalid. The same set-based check works for columns and boxes.

Algorithm

  1. For each of the 9 rows, walk the row with a fresh set. Skip empty cells. If a digit is already in the set, return false; otherwise add it.
  2. For each of the 9 columns, do the same with a fresh set per column.
  3. For each of the 9 sub-boxes (identified by box-row 0-2 and box-column 0-2), iterate over its 3x3 region with a fresh set and apply the same check.
  4. If no pass finds a duplicate, return true.

Visualization and Code

Loading animation...

The three-pass approach is correct, and since the board is fixed at 9x9 there is no performance penalty. The drawback is repetition: the same duplicate-checking logic is written three times, and the board is read three times. The next approach folds all three checks into a single pass.

Approach 2: Single Pass with Hash Sets

Intuition

Check all three constraints during one walk over the board. Maintain a set for every row, every column, and every 3x3 box (27 sets in all). For each filled cell, check whether its digit already appears in its row's set, its column's set, or its box's set. If it appears in any of them, the board is invalid; otherwise add the digit to all three.

The row and column lookups are direct, but the box check needs a way to find which box a cell belongs to. The 9 boxes form a 3x3 grid of blocks. A cell's block row is r / 3 (integer division): rows 0-2 give 0, rows 3-5 give 1, rows 6-8 give 2. Its block column is c / 3 by the same logic. To store the 27 sets in flat arrays, flatten that (blockRow, blockCol) pair into a single index with the standard row-major formula blockRow * 3 + blockCol, which is (r / 3) * 3 + (c / 3). The * 3 is the number of block columns per block row, so the formula maps the nine (blockRow, blockCol) pairs to the distinct integers 0 through 8. For example, cell (5, 7) has block row 5 / 3 = 1 and block column 7 / 3 = 2, giving box index 1 * 3 + 2 = 5.

Algorithm

  1. Create 9 sets for rows, 9 for columns, and 9 for boxes.
  2. Iterate through every cell (r, c) on the board.
  3. If the cell is empty ('.'), skip it.
  4. Compute the box index as (r / 3) * 3 + (c / 3).
  5. If the digit is already in the row set, column set, or box set, return false.
  6. Otherwise, add the digit to all three sets.
  7. If the walk finishes without a duplicate, return true.

Visualization and Code

Loading animation...

Maintaining 27 separate sets works but takes a few lines of setup. A common variation collapses them into one set by encoding each constraint as a distinct string key, so a single container tracks rows, columns, and boxes at once.

Approach 3: Single HashSet with Composite Keys

Intuition

Three separate sets per group exist only to keep the row, column, and box namespaces from colliding. A 5 in row 0 and a 5 in column 0 are unrelated facts, so they must not be confused. Instead of using three containers, give each fact a label that makes it unique inside one set.

When we reach a cell (r, c) with digit d, it produces three facts: digit d is in row r, in column c, and in box (r/3)*3 + (c/3). Encode each as a string such as "row 0-5", "col 0-5", and "box 0-5". Because the prefix distinguishes the three namespaces and the numbers distinguish which row, column, or box, every string is unique to one fact. Add all three to a single set; if any of the three is already present, that fact has been recorded before, which means a duplicate. The logic is identical to Approach 2, with the namespace baked into the key instead of into the choice of container.

Algorithm

  1. Create one set to hold all keys.
  2. Iterate through every cell (r, c) on the board.
  3. If the cell is empty, skip it.
  4. Build three keys for the digit d: "row r-d", "col c-d", and "box (r/3)*3+(c/3)-d".
  5. If any of the three keys is already in the set, return false.
  6. Otherwise, add all three keys.
  7. If the walk finishes without a duplicate, return true.

Visualization and Code

Loading animation...

This packs the bookkeeping into one container, at the cost of building and hashing a string for every fact. Approach 2 avoids the string work, and the next approach removes the hashing entirely by replacing each set with a single integer used as a bitmask, turning the membership check into one bitwise operation.

Approach 4: Bitmask (Optimal Space Efficiency)

Intuition

With only nine possible digits, the set of digits seen in any row, column, or box fits in a single integer used as a bitmask. Each digit owns one bit. Setting a bit marks its digit as seen, and testing a bit checks whether the digit has appeared.

We want nine bits, one per digit, and the cheapest mapping packs them into the lowest nine bits. The character '1' should map to bit 0, '2' to bit 1, and so on through '9' to bit 8. Subtracting the character '1' from a digit character yields that 0-based offset directly: '1' - '1' = 0, '5' - '1' = 4, '9' - '1' = 8. So the mask for a digit is 1 << (digit - '1'). Subtracting '0' instead would map '1' to bit 1 and '9' to bit 9, wasting bit 0 and needing ten bits; subtracting '1' keeps the masks in bits 0 through 8.

To test whether a digit is already present, AND the group's integer with the digit's mask: a non-zero result means the bit is set and the digit is a duplicate. To record the digit, OR the mask into the integer. Both operations are single instructions, with no hashing or allocation.

Algorithm

  1. Create three arrays of 9 integers: rows, cols, and boxes, all initialized to 0.
  2. Iterate through every cell (r, c) on the board.
  3. If the cell is empty, skip it.
  4. Compute mask = 1 << (digit - '1') for this digit.
  5. Compute the box index as (r / 3) * 3 + (c / 3).
  6. If rows[r] & mask, cols[c] & mask, or boxes[boxIdx] & mask is non-zero, the digit is a duplicate. Return false.
  7. Otherwise, set the bit in all three: rows[r] |= mask, cols[c] |= mask, boxes[boxIdx] |= mask.
  8. If the walk finishes without a duplicate, return true.

Visualization and Code

Loading animation...