Valid Sudoku

NeetCode: Valid Sudoku · LeetCode: 36. Valid Sudoku · Difficulty: Medium

Determine whether a partially filled 9x9 board is valid. Each row, each column, and each of the nine 3x3 boxes may contain the digits 1-9 at most once. Empty cells are .. The board need not be solvable.

Example

Text

A board with two 5s in the same row -> false
A board with no repeated digit in any row, column, or box -> true

Brute force: check each unit separately

Make three passes: one over every row, one over every column, one over every 3x3 box. Each check collects the digits of that unit in a HashSet<Character> and fails on a repeat: Set.add returns false when the element is already present. The board is a char[][], and main builds it from row strings with a small parse helper.

Java

import java.util.HashSet;
import java.util.Set;

public class Main {
    static class Solution {
        public boolean isValidSudoku(char[][] board) {
            for (int r = 0; r < 9; r++) {
                Set<Character> seen = new HashSet<>();
                for (int c = 0; c < 9; c++) {
                    if (!fresh(seen, board[r][c])) return false;
                }
            }
            for (int c = 0; c < 9; c++) {
                Set<Character> seen = new HashSet<>();
                for (int r = 0; r < 9; r++) {
                    if (!fresh(seen, board[r][c])) return false;
                }
            }
            for (int boxR = 0; boxR < 3; boxR++) {
                for (int boxC = 0; boxC < 3; boxC++) {
                    Set<Character> seen = new HashSet<>();
                    for (int i = 0; i < 9; i++) {
                        if (!fresh(seen, board[boxR * 3 + i / 3][boxC * 3 + i % 3])) return false;
                    }
                }
            }
            return true;
        }

        // False when the digit was already in the set. Empty cells are ignored.
        private boolean fresh(Set<Character> seen, char ch) {
            return ch == '.' || seen.add(ch);
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] good = parse(
            "53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
            "7...2...6", ".6....28.", "...419..5", "....8..79");
        char[][] bad = parse(
            "53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
            "7...2...6", ".6....28.", "...419..5", "....8..75");
        System.out.println(sol.isValidSudoku(good));
        System.out.println(sol.isValidSudoku(bad));
    }

    // Builds the char[][] board from nine row strings.
    static char[][] parse(String... rows) {
        char[][] board = new char[rows.length][];
        for (int i = 0; i < rows.length; i++) {
            board[i] = rows[i].toCharArray();
        }
        return board;
    }
}

Output

true
false

Time: O(81), which is constant for a fixed board size. Space: O(9).

Optimal: one pass with bitmasks

Visit each cell once. Keep 9 integers for rows, 9 for columns, and 9 for boxes, where bit d of an int records that digit d has appeared. 1 << (ch - '1') turns the character '1' to '9' into a bit from 0 to 8. A cell's box number is (r / 3) * 3 + c / 3. If the digit's bit is already set in its row, column, or box, the board is invalid.

Java

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

    public static void main(String[] args) {
        Solution sol = new Solution();
        char[][] good = parse(
            "53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
            "7...2...6", ".6....28.", "...419..5", "....8..79");
        char[][] bad = parse(
            "53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1",
            "7...2...6", ".6....28.", "...419..5", "....8..75");
        System.out.println(sol.isValidSudoku(good));
        System.out.println(sol.isValidSudoku(bad));
    }

    // Builds the char[][] board from nine row strings.
    static char[][] parse(String... rows) {
        char[][] board = new char[rows.length][];
        for (int i = 0; i < rows.length; i++) {
            board[i] = rows[i].toCharArray();
        }
        return board;
    }
}

Output

true
false

Time: O(81), a single pass. Space: O(1): 27 int values.

Both versions are constant time for a 9x9 board; the single pass does a third of the work and generalizes to n x n boards.