A fulfillment map is a 9×9 bin grid. Occupied bins hold a SKU class 1–9. Empty bins are '.'. Last quarter a nightly job tried to place the remaining classes — a solver. Then two pallets of class 7 left the same 3×3 zone on the same shift. Operations needed a cheaper question first: is the current fill legal? A duplicate in a row, a column, or a zone is already a bad board. Filling the dots is a different ticket.

Valid Sudoku asks whether filled digits already conflict. An array of rows is the board. Empty cells skip the check. This is not a solver: a later backtracking prompt owns completions. Here we only walk the three fans around each filled cell — its row, its column, and its 3×3 box.

The problem

Given a 9×9 char[][] board whose cells are '1'–'9' or '.', return whether every filled digit is unique in its row, unique in its column, and unique in its 3×3 box. Do not place digits in the empty cells. A board can be valid and still have no completion; that is allowed.

row [5, '.', '.', '.', '5', '.', '.', '.', '.']  →  false
    two 5s share the row; the rest of the board can be empty.

3×3 box
8 . .
. 3 8
. . 1
→  false   two 8s share the box.

empty 9×9 of '.'  →  true

Note: Validation is not search. If they ask you to fill the '.' cells, that is a different prompt with backtracking. Stay on membership.

Rescan the row, column, and box

For each filled cell, walk its eight row-mates, eight column-mates, and the other cells of its 3×3 box. A matching digit is a conflict. Correct. Wasteful: every filled cell re-reads fans you will read again from a neighbor.

boolean validSudokuNested(char[][] board) {
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            char d = board[r][c];
            if (d == '.') {
                continue;
            }
            for (int k = 0; k < 9; k++) {
                if (k != c && board[r][k] == d) {
                    return false;
                }
                if (k != r && board[k][c] == d) {
                    return false;
                }
            }
            int br = (r / 3) * 3;
            int bc = (c / 3) * 3;
            for (int i = br; i < br + 3; i++) {
                for (int j = bc; j < bc + 3; j++) {
                    if ((i != r || j != c) && board[i][j] == d) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

The board is fixed 9×9, so this is still constant work. The complaint is not asymptotics on a 9-row grid. It is that you re-walk the same fans instead of recording what you already saw: have I already seen this digit in this row, column, or box?

One scan: three membership tests per filled cell

Keep nine sets of seen digits for rows, nine for columns, nine for boxes. Box index is (r / 3) * 3 + (c / 3): row-band first, then column-band. Skip '.'. Set.add returning false is the duplicate.

cell (0, 0) = '5'   row0, col0, box0  miss, record 5
cell (0, 4) = '5'   row0 already holds 5  →  false

The Java is that walk:

boolean isValidSudoku(char[][] board) {
    List<Set<Character>> rows = new ArrayList<>(9);
    List<Set<Character>> cols = new ArrayList<>(9);
    List<Set<Character>> boxes = new ArrayList<>(9);
    for (int i = 0; i < 9; i++) {
        rows.add(new HashSet<>());
        cols.add(new HashSet<>());
        boxes.add(new HashSet<>());
    }
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            char d = board[r][c];
            if (d == '.') {
                continue;
            }
            int b = (r / 3) * 3 + (c / 3);
            if (!rows.get(r).add(d) || !cols.get(c).add(d) || !boxes.get(b).add(d)) {
                return false;
            }
        }
    }
    return true;
}

Time is O(1) on a 9×9 board — 81 cells, expected-O(1) add per filled cell. Space is O(1) — at most nine digits in each of 27 sets. If they grow the board to n² × n² with n × n boxes, the same scan is linear in the cell count.

Note: Do not try to complete the grid. A valid partial board is a yes. An empty board is a yes. One duplicate is a no, even if a solver could have avoided that fill.

What interviewers usually poke next

  • Bitmasks instead of sets. Nine bits per row, column, and box. int bit = 1 << (d - '1'); test, then OR. Same scan, no HashSet.
  • Boolean tables. boolean[9][9] for row/digit, col/digit, box/digit. Same membership, no hashing.
  • Solve the puzzle. Backtracking from the first '.'. Say that is a different question and stop unless they switch prompts.
  • Characters other than '1'–'9' and '.'. The prompt promised a well-formed board. In production you would reject; at the board, ask.

You are done with this problem when you can say, out loud, why a solver is the wrong tool, how the box index is built from r / 3 and c / 3, and why one pass with three membership tests replaces the nested fan scans.