Valid Sudoku

Medium Problem 32 of 151 Java and Python

Problem

Determine whether a partly filled 9 × 9 Sudoku board is valid. Only the filled cells need to follow the rules:

Each row, each column and each of the nine 3 × 3 boxes must contain the digits 1–9 without repetition. Empty cells are written as ".". A valid board does not have to be solvable.

Example 1

Input: The classic example board (row 1: 5 3 . . 7 . . . .)
Output: true
Why: No row, column or box repeats a digit.

Example 2

Input: The same board with the top-left 5 changed to 8
Output: false
Why: The first column and the top-left box now contain two 8s.

Constraints

board is 9 × 9.
board[i][j] is a digit 1–9 or ".".

Explanation

Every filled cell belongs to one row, one column and one box. The box index for cell (r, c) is (r / 3) × 3 + c / 3.

Keep a set of seen digits for each of the 27 units. A digit already in any of its three sets means the board is invalid.

Approach 1 · Naive

Check rows, columns and boxes separately

Time O(81 · 3) = O(1) for a fixed board
Space O(9)

Make three passes: one checking each row, one each column, one each box, using a fresh set for every unit.

For each row, collect its digits; fail on a repeat.
Do the same for each column and each 3 × 3 box.

Java

import java.util.*;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            Set<Character> row = new HashSet<>();
            Set<Character> col = new HashSet<>();
            Set<Character> box = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                char r = board[i][j];
                char c = board[j][i];
                char b = board[3 * (i / 3) + j / 3][3 * (i % 3) + j % 3];
                if ((r != '.' && !row.add(r)) || (c != '.' && !col.add(c)) || (b != '.' && !box.add(b))) {
                    return false;
                }
            }
        }
        return true;
    }
}

Python

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        def unique(cells):
            digits = [c for c in cells if c != "."]
            return len(digits) == len(set(digits))

        for i in range(9):
            row = board[i]
            col = [board[r][i] for r in range(9)]
            box = [board[3 * (i // 3) + r][3 * (i % 3) + c] for r in range(3) for c in range(3)]
            if not (unique(row) and unique(col) and unique(box)):
                return False
        return True

Approach 2 · Optimal

One pass with 27 sets

Time O(81) = O(1)
Space O(81) = O(1)

Visit each cell once and check its digit against the sets for its row, column and box at the same time.

Create 9 row sets, 9 column sets and 9 box sets.
For each filled cell (r, c) with digit d, compute b = (r / 3) * 3 + c / 3.
If d is already in rows[r], cols[c] or boxes[b], return false; otherwise add it to all three.

Java

class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] boxes = new boolean[9][9];
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') {
                    continue;
                }
                int d = board[r][c] - '1';
                int b = (r / 3) * 3 + c / 3;
                if (rows[r][d] || cols[c][d] || boxes[b][d]) {
                    return false;
                }
                rows[r][d] = cols[c][d] = boxes[b][d] = true;
            }
        }
        return true;
    }
}

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):
                d = board[r][c]
                if d == ".":
                    continue
                b = (r // 3) * 3 + c // 3
                if d in rows[r] or d in cols[c] or d in boxes[b]:
                    return False
                rows[r].add(d)
                cols[c].add(d)
                boxes[b].add(d)
        return True

Complexity compared

Approach	Time	Space
Naive Check rows, columns and boxes separately	O(81 · 3) = O(1) for a fixed board	O(9)
Optimal One pass with 27 sets	O(81) = O(1)	O(81) = O(1)

Key takeaways

Memorise the box index formula (r / 3) * 3 + c / 3; it shows up in every grid-of-boxes problem.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem