Valid Sudoku

Examples

Input: A 9x9 board where every filled row, column, and 3x3 box has no repeated digit
Output: true

Input: The same board, except the top-left 3x3 box now has two cells both containing '8'
Output: false

Two 8s inside the same 3x3 box violates the box rule, even though the rows and columns are otherwise fine.

Input: A board where row 0 contains the digit '3' twice
Output: false

A repeated digit in the same row is a direct violation, regardless of what the columns or boxes look like.

Constraints

• The board is always exactly 9x9.

• Each cell holds a digit '1'-'9' or the character '.'.

Approach

A natural first attempt is to check each rule separately: sweep across every row checking for duplicates, then sweep down every column, then check each of the nine 3x3 boxes. Each sweep uses a set to catch repeated digits. It's correct, but it looks at the whole board three separate times.

Since every cell belongs to exactly one row, one column, and one box all at once, you can fold every check into a single pass. Keep a small set for each row, each column, and each box (nine of each). Visit each filled cell exactly once, and check whether its digit already exists in that cell's row-set, column-set, or box-set - if it does, the board is invalid. Otherwise, record the digit in all three sets and move on.

The trick that makes box-tracking work is a small formula: for a cell at row r and column c, its box index is "Math.floor(r / 3) * 3 + Math.floor(c / 3)" - it maps every cell to one of the nine boxes, numbered left-to-right, top-to-bottom.

Solutions

Brute Force - Three Separate Sweeps

Check the board three times: once sweeping every row for duplicates, once sweeping every column, and once sweeping every 3x3 box. Each sweep uses a fresh set per group to spot a repeated digit.

function isValidSudoku(board) {
  // Check rows
  for (let r = 0; r < 9; r++) {
    const seen = new Set();
    for (let c = 0; c < 9; c++) {
      const val = board[r][c];
      if (val === ".") continue;
      if (seen.has(val)) return false;
      seen.add(val);
    }
  }

  // Check columns
  for (let c = 0; c < 9; c++) {
    const seen = new Set();
    for (let r = 0; r < 9; r++) {
      const val = board[r][c];
      if (val === ".") continue;
      if (seen.has(val)) return false;
      seen.add(val);
    }
  }

  // Check 3x3 boxes
  for (let boxRow = 0; boxRow < 3; boxRow++) {
    for (let boxCol = 0; boxCol < 3; boxCol++) {
      const seen = new Set();
      for (let i = 0; i < 3; i++) {
        for (let j = 0; j < 3; j++) {
          const val = board[boxRow * 3 + i][boxCol * 3 + j];
          if (val === ".") continue;
          if (seen.has(val)) return false;
          seen.add(val);
        }
      }
    }
  }

  return true;
}

Time: O(1) - the board is always a fixed 9x9 grid, so the work is bounded by a constant (it visits all 81 cells three separate times) · Space: O(1) - each set holds at most 9 digits

Optimal - Single Pass With Row, Column, and Box Sets

Keep one set per row, one per column, and one per 3x3 box. Sweep the board exactly once - for each filled cell, check its digit against that cell's row, column, and box sets before adding it to all three.

function isValidSudoku(board) {
  const rows = Array.from({ length: 9 }, () => new Set());
  const cols = Array.from({ length: 9 }, () => new Set());
  const boxes = Array.from({ length: 9 }, () => new Set());

  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      const val = board[r][c];
      if (val === ".") continue;

      const boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3);

      if (rows[r].has(val) || cols[c].has(val) || boxes[boxIndex].has(val)) {
        return false;
      }

      rows[r].add(val);
      cols[c].add(val);
      boxes[boxIndex].add(val);
    }
  }

  return true;
}

Time: O(1) - the board is always a fixed 9x9 grid, and this version visits each of the 81 cells only once · Space: O(1) - 27 sets total, each holding at most 9 digits