Valid Sudoku

35 min · isValidSudoku()

An unfinished Sudoku grid can already contradict itself. You don't need to solve it to spot that contradiction.

Given a 9-by-9 board, return true when its filled cells obey all three Sudoku rules; otherwise return false:

No row contains the same digit twice.
No column contains the same digit twice.
No 3-by-3 sub-box — one of the nine smaller regions — contains the same digit twice.

Only filled cells matter. A '.' marks an empty cell, and a board may be valid even if it has no solution or isn't complete.

The judge supplies board as an array of 9 arrays. Each inner array contains 9 single-character strings.

Constraints

board.length == 9
board[i].length == 9
Every cell is one of '1' through '9', or '.'.

Hints

Write three honest checks

Start by checking all rows, then all columns, then each 3-by-3 sub-box. Ignore '.' and reject a unit as soon as a digit appears twice.

Track all three rules together

During one row-by-row scan, a filled cell belongs to exactly one row, one column, and one sub-box. Keep a separate seen set for each of those units.

Name the box

For a cell at (row, col), its sub-box is determined by (row // 3, col // 3). In zero-based code, Math.floor(row / 3) * 3 + Math.floor(col / 3) gives one box index from 0 through 8.

Follow-up

How would you generalize the same validation idea to an n²-by-n² board whose sub-boxes are n by n?

Visible cases

Examples

Example 1

ready

Input: board = [ [ "5", ".", ".", "6", ".", ".", "9", ".", "." ], [ ".", "7", ".", ".", "9", ".", ".", "4", "." ], [ ".", ".", "8", ".", "4", ".", ".", "6", "." ], [ "8", ".", ".", ".", "6", ".", ".", ".", "3" ], [ ".", "2", ".", "8", ".", "3", ".", "9", "." ], [ "7", ".", ".", ".", "2", ".", ".", ".", "6" ], [ ".", "6", ".", ".", "3", ".", ".", "8", "." ], [ ".", ".", "7", ".", "1", ".", "6", ".", "." ], [ "3", ".", ".", "2", ".", ".", "1", ".", "9" ] ]
Expected: true
Why: every filled digit is unique in its row, column, and box

Example 2

ready

Input: board = [ [ ".", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", "7", ".", ".", ".", ".", ".", "7", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ] ]
Expected: false
Why: the third row contains 7 twice

Example 3

ready

Input: board = [ [ "4", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", "4", ".", ".", ".", ".", ".", ".", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ], [ ".", ".", ".", ".", ".", ".", ".", ".", "." ] ]
Expected: false
Why: the top-left 3-by-3 box contains 4 twice

Interview signal

Asked at

AmazonAppleUber

Validity is local: each filled cell must be unique inside three small groups. You never need to guess a missing digit or decide whether the puzzle can be solved.

Check every unit separately

The direct version gives rows, columns, and boxes their own scans. A helper ignores empty cells and rejects the first repeated digit.

def is_valid_sudoku(board: list[list[str]]) -> bool:
    def has_duplicate(cells: list[str]) -> bool:
        seen: set[str] = set()
        for cell in cells:
            if cell == ".":
                continue
            if cell in seen:
                return True
            seen.add(cell)
        return False
 
    for row in board:
        if has_duplicate(row):
            return False
 
    for col in range(9):
        if has_duplicate([board[row][col] for row in range(9)]):
            return False
 
    for box_row in range(0, 9, 3):
        for box_col in range(0, 9, 3):
            cells = [
                board[row][col]
                for row in range(box_row, box_row + 3)
                for col in range(box_col, box_col + 3)
            ]
            if has_duplicate(cells):
                return False
    return True

Time O(1) — the board always has 81 cells, even though this makes three families of scans. Space O(1) — a unit's set holds at most nine digits.

One pass with seen sets

You can enforce all three rules as each cell arrives. Keep nine row sets, nine column sets, and nine box sets. A cell at (row, col) belongs to box (row // 3) * 3 + col // 3.

def is_valid_sudoku(board: list[list[str]]) -> bool:
    rows = [set() for _ in range(9)]
    columns = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
 
    for row in range(9):
        for col in range(9):
            digit = board[row][col]
            if digit == ".":
                continue
 
            box = (row // 3) * 3 + col // 3
            if digit in rows[row] or digit in columns[col] or digit in boxes[box]:
                return False
 
            rows[row].add(digit)
            columns[col].add(digit)
            boxes[box].add(digit)
    return True

When you reach a filled cell, its sets contain exactly the earlier digits from its row, column, and box. Finding the digit in any set proves a repeated value; otherwise adding it preserves all three rules for the next cell.

Time O(1) — one scan over a fixed 9-by-9 board. Space O(1) — the 27 sets can hold only a fixed number of digits.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON array

[
  [
    [
      "5",
      ".",
      ".",
      "6",
      ".",
      ".",
      "9",
      ".",
      "."
    ],
    [
      ".",
      "7",
      ".",
      ".",
      "9",
      ".",
      ".",
      "4",
      "."
    ],
    [
      ".",
      ".",
      "8",
      ".",
      "4",
      ".",
      ".",
      "6",
      "."
    ],
    [
      "8",
      ".",
      ".",
      ".",
      "6",
      ".",
      ".",
      ".",
      "3"
    ],
    [
      ".",
      "2",
      ".",
      "8",
      ".",
      "3",
      ".",
      "9",
      "."
    ],
    [
      "7",
      ".",
      ".",
      ".",
      "2",
      ".",
      ".",
      ".",
      "6"
    ],
    [
      ".",
      "6",
      ".",
      ".",
      "3",
      ".",
      ".",
      "8",
      "."
    ],
    [
      ".",
      ".",
      "7",
      ".",
      "1",
      ".",
      "6",
      ".",
      "."
    ],
    [
      "3",
      ".",
      ".",
      "2",
      ".",
      ".",
      "1",
      ".",
      "9"
    ]
  ]
]

board: char[][]

Expected

true

Run: visible + custom · Submit: full suite