Valid Sudoku

You are given a partly filled 9 × 9 Sudoku grid board. Each cell is a one-character string: a digit '1' to '9', or '.' for an empty cell.

Return true if the filled cells break none of these rules, and false otherwise:

• No digit appears more than once in any row.
• No digit appears more than once in any column.
• No digit appears more than once in any of the nine 3 × 3 boxes that tile the grid.

Only the digits already on the board are checked. A board can be valid even if it could never be completed into a full solution.

Example 1

Example 2

Example 3

Constraints

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

Pattern Path · Hashing & Counting · problem 7 of 169

Start simple

Check the 9 rows, then the 9 columns, then the 9 boxes in three separate passes with a fresh set per group: also O(81), just more code and three scans instead of one.

The key idea

A digit is a problem only if it repeats inside a row, a column or a box. So the task is duplicate detection across 27 overlapping groups, and every filled cell belongs to exactly three of them: its row, its column and its box.

Walk over all 81 cells once, keeping three arrays of sets: rows[9], cols[9] and boxes[9]. For a filled cell (r, c) with digit d, compute its box number b = (r // 3) * 3 + c // 3. Integer division by 3 maps rows 0-2, 3-5 and 6-8 to bands 0, 1, 2 (and likewise for columns), and the formula numbers the boxes 0 to 8 from left to right, top to bottom.

If d is already in rows[r], cols[c] or boxes[b], a rule is broken, so return false immediately. Otherwise add it to all three. If the scan finishes, every group held distinct digits.

Note that validity is not solvability: the rules only concern digits that are present, so there is no need to search for a solution.

Complexity

• Time: O(1) (81 cells)
• Space: O(1) (27 small sets)

Python

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]
        for r in range(9):
            for c in range(9):
                digit = board[r][c]
                if digit == ".":
                    continue
                b = (r // 3) * 3 + c // 3
                if digit in rows[r] or digit in cols[c] or digit in boxes[b]:
                    return False
                rows[r].add(digit)
                cols[c].add(digit)
                boxes[b].add(digit)
        return True

JavaScript

var isValidSudoku = function(board) {
  const makeSets = () => Array.from({ length: 9 }, () => new Set());
  const rows = makeSets(), cols = makeSets(), boxes = makeSets();
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const digit = board[r][c];
      if (digit === '.') continue;
      const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);
      if (rows[r].has(digit) || cols[c].has(digit) || boxes[b].has(digit)) return false;
      rows[r].add(digit);
      cols[c].add(digit);
      boxes[b].add(digit);
    }
  }
  return true;
};

What the interviewer is checking

This checks whether you can express grid structure cleanly, especially the box index arithmetic, and organise the bookkeeping so a single pass does all the checks.

Mistakes to avoid

• Getting the box index wrong, for example r // 3 + c // 3, which maps different boxes to the same number.
• Counting '.' as a value and reporting duplicates of empty cells.
• Trying to solve the puzzle, when only the existing digits need checking.

Follow-ups to expect

• How would you solve the Sudoku? (Backtracking with these same sets.)
• Can you use bitmasks instead of sets? (Nine-bit integer per group.)
• How does this generalise to n² × n² boards? (Box index (r//n)*n + c//n.)

In real software

Constraint checks like this validate timetables, seat maps and spreadsheet uniqueness rules, where each entry belongs to several groups that must each stay duplicate-free.

Practice next