Skip to main content
CodePeetCodePeet
CodePeet 250

Valid Sudoku

MEDIUMProblemSolveExternal Links

Description

You are given a 9×9 Sudoku board represented as a two-dimensional array of characters. Each cell in the board contains either a single digit from '1' to '9' or a '.' character, which represents an empty cell.

Your task is to determine whether the current board configuration is valid. A Sudoku board is considered valid if and only if all three of the following rules hold true for the digits that are already filled in:

  1. Each row must contain the digits 1 through 9 with no repetitions among the filled cells.
  2. Each column must contain the digits 1 through 9 with no repetitions among the filled cells.
  3. Each of the nine 3×3 sub-boxes (non-overlapping regions that tile the board) must contain the digits 1 through 9 with no repetitions among the filled cells.

Important clarifications:

  • Only the filled cells need to be validated. Empty cells (.) are simply ignored.
  • The board does not need to be fully solved or even solvable. You are only checking that no rule is violated by the numbers that are already placed.
  • A partially filled board that follows the rules is considered valid.
A 9×9 Sudoku grid divided into nine 3×3 sub-boxes, with rows, columns, and sub-boxes highlighted
A 9×9 Sudoku grid divided into nine 3×3 sub-boxes, with rows, columns, and sub-boxes highlighted

Examples

Example 1

Input:

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

Output: true

Explanation: Every row, every column, and every 3×3 sub-box contains no repeated digits among the filled cells. For instance, row 0 contains {5, 3, 7} — all distinct. Column 0 contains {5, 6, 8, 4, 7} — all distinct. The top-left 3×3 sub-box (rows 0-2, cols 0-2) contains {5, 3, 6, 9, 8} — all distinct. Since no rule is violated anywhere on the board, the configuration is valid.

Example 2

Input:

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

Output: false

Explanation: This board is nearly identical to Example 1, but the top-left cell has been changed from '5' to '8'. Now column 0 contains the digit '8' at both row 0 and row 3, violating the column uniqueness rule. Additionally, the top-left 3×3 sub-box (rows 0-2, cols 0-2) now contains '8' at position (0,0) and '8' at position (2,2) — but wait, position (2,2) already had '8' from the original board. So the sub-box also has a duplicate '8'. Either violation alone is enough to make the board invalid.

Example 3

Input:

board = [
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."],
  [".",".",".",".",".",".",".",".","."]
]

Output: true

Explanation: An entirely empty board is valid because there are no filled cells at all, so no rule can possibly be violated. Validity only checks existing digits, and there are none.

Constraints

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit '1'-'9' or '.'

Editorial

Brute Force

Intuition

The most straightforward way to validate a Sudoku board is to check each constraint separately, one at a time.

Imagine you are a teacher grading a student's Sudoku attempt. You would naturally:

  1. Go through each of the 9 rows and verify no digit appears twice.
  2. Go through each of the 9 columns and verify no digit appears twice.
  3. Go through each of the 9 sub-boxes and verify no digit appears twice.

For each group (row, column, or sub-box), you collect all the filled-in digits and check whether any digit is repeated. If you find a duplicate anywhere, the board is invalid. If you complete all 27 checks (9 rows + 9 columns + 9 sub-boxes) without finding a duplicate, the board is valid.

This approach performs three separate passes over the board — one for rows, one for columns, and one for sub-boxes — which is conceptually simple but does more work than necessary.

Step-by-Step Explanation

Let's trace through a small portion of Example 2's board to see how duplicate detection works:

Board (first column, col 0): ['8', '6', '.', '8', '4', '7', '.', '.', '.']

Step 1: Begin checking column 0. Create an empty set to track seen digits.

  • seen = {}

Step 2: Read cell (0, 0) = '8'. Is '8' in seen? No. Add '8' to seen.

  • seen = {'8'}

Step 3: Read cell (1, 0) = '6'. Is '6' in seen? No. Add '6' to seen.

  • seen = {'8', '6'}

Step 4: Read cell (2, 0) = '.'. It's empty — skip.

  • seen = {'8', '6'}

Step 5: Read cell (3, 0) = '8'. Is '8' in seen? YES! Duplicate found!

  • Return false immediately. Column 0 contains '8' twice.

The brute force approach would perform this kind of set-based duplicate check for all 9 rows, then all 9 columns, then all 9 sub-boxes, stopping as soon as a violation is found.

Brute Force — Checking Column 0 for Duplicates — Watch how we scan down column 0, collecting digits into a set. When we encounter '8' a second time, we detect a duplicate and the board is invalid.

Algorithm

  1. Check all 9 rows: For each row, create a set. Iterate through the 9 cells in that row. If a cell is not '.', check if its digit is already in the set. If yes, return false. Otherwise, add the digit to the set.
  2. Check all 9 columns: For each column index j (0 to 8), create a set. Iterate through all 9 rows at column j. Apply the same duplicate-detection logic.
  3. Check all 9 sub-boxes: For each sub-box (identified by box_row 0-2 and box_col 0-2), create a set. Iterate through the 9 cells in that sub-box (rows from box_row3 to box_row3+2, cols from box_col3 to box_col3+2). Apply the same duplicate-detection logic.
  4. If all 27 groups pass the duplicate check, return true.

Code

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // Check each row
        for (int i = 0; i < 9; i++) {
            unordered_set<char> seen;
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                if (seen.count(board[i][j])) return false;
                seen.insert(board[i][j]);
            }
        }
        // Check each column
        for (int j = 0; j < 9; j++) {
            unordered_set<char> seen;
            for (int i = 0; i < 9; i++) {
                if (board[i][j] == '.') continue;
                if (seen.count(board[i][j])) return false;
                seen.insert(board[i][j]);
            }
        }
        // Check each 3x3 sub-box
        for (int boxRow = 0; boxRow < 3; boxRow++) {
            for (int boxCol = 0; boxCol < 3; boxCol++) {
                unordered_set<char> seen;
                for (int i = boxRow * 3; i < boxRow * 3 + 3; i++) {
                    for (int j = boxCol * 3; j < boxCol * 3 + 3; j++) {
                        if (board[i][j] == '.') continue;
                        if (seen.count(board[i][j])) return false;
                        seen.insert(board[i][j]);
                    }
                }
            }
        }
        return true;
    }
};
class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        # Check each row
        for i in range(9):
            seen = set()
            for j in range(9):
                if board[i][j] == '.':
                    continue
                if board[i][j] in seen:
                    return False
                seen.add(board[i][j])
        
        # Check each column
        for j in range(9):
            seen = set()
            for i in range(9):
                if board[i][j] == '.':
                    continue
                if board[i][j] in seen:
                    return False
                seen.add(board[i][j])
        
        # Check each 3x3 sub-box
        for box_row in range(3):
            for box_col in range(3):
                seen = set()
                for i in range(box_row * 3, box_row * 3 + 3):
                    for j in range(box_col * 3, box_col * 3 + 3):
                        if board[i][j] == '.':
                            continue
                        if board[i][j] in seen:
                            return False
                        seen.add(board[i][j])
        
        return True
import java.util.HashSet;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // Check each row
        for (int i = 0; i < 9; i++) {
            HashSet<Character> seen = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                if (seen.contains(board[i][j])) return false;
                seen.add(board[i][j]);
            }
        }
        // Check each column
        for (int j = 0; j < 9; j++) {
            HashSet<Character> seen = new HashSet<>();
            for (int i = 0; i < 9; i++) {
                if (board[i][j] == '.') continue;
                if (seen.contains(board[i][j])) return false;
                seen.add(board[i][j]);
            }
        }
        // Check each 3x3 sub-box
        for (int boxRow = 0; boxRow < 3; boxRow++) {
            for (int boxCol = 0; boxCol < 3; boxCol++) {
                HashSet<Character> seen = new HashSet<>();
                for (int i = boxRow * 3; i < boxRow * 3 + 3; i++) {
                    for (int j = boxCol * 3; j < boxCol * 3 + 3; j++) {
                        if (board[i][j] == '.') continue;
                        if (seen.contains(board[i][j])) return false;
                        seen.add(board[i][j]);
                    }
                }
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(1)

Although we traverse the 9×9 board three separate times (once for rows, once for columns, once for sub-boxes), the board size is fixed at 81 cells. Each pass examines 81 cells, and we do 3 passes, giving 3 × 81 = 243 constant-time operations. Since the board dimensions never change, this is O(1) — technically O(3 × 81) = O(243) = O(1).

Space Complexity: O(1)

We create at most one set at a time with at most 9 elements. All storage is bounded by the fixed board size and does not scale with any variable input. This is constant space.

Why This Approach Is Not Efficient

While the brute force approach is technically O(1) because the Sudoku board is always 9×9, it performs three separate passes over the board — one for rows, one for columns, and one for sub-boxes. This means we visit each cell up to 3 times and create up to 27 separate sets.

The key insight is that when we visit a cell at position (i, j), we already know which row, which column, and which sub-box it belongs to. There is no reason we cannot check all three constraints for that cell in a single visit.

By consolidating the three passes into a single traversal, we reduce redundant cell accesses and make the code cleaner and more elegant. Instead of creating sets on-the-fly for each group, we can maintain all tracking structures simultaneously and validate every cell against all three rules in one go.

Optimal Approach - Single Pass with Hash Sets

Intuition

Instead of making three separate sweeps, we can validate the entire board in a single traversal. The idea is to maintain three collections of tracking sets simultaneously:

  1. 9 row sets — one set per row, tracking which digits have appeared in that row.
  2. 9 column sets — one set per column, tracking which digits have appeared in that column.
  3. 9 sub-box sets — one set per 3×3 sub-box, tracking which digits have appeared in that sub-box.

As we scan through each cell (i, j) from top-left to bottom-right:

  • If the cell is empty ('.'), we skip it.
  • If the cell contains a digit, we check whether that digit already exists in the corresponding row set, column set, or sub-box set. If it does, we have found a violation and return false immediately.
  • If no violation, we record the digit in all three sets and move to the next cell.

The critical trick is computing which sub-box a cell belongs to. For a cell at position (i, j), the sub-box index is: (i / 3) * 3 + (j / 3). This maps each cell to one of the 9 sub-boxes numbered 0 through 8.

Think of it like a librarian cataloging a new book: when a book arrives, you simultaneously check the author index, the subject index, and the shelf catalog. You don't check one index, then come back for the second, then come back for the third — you do all three lookups in one visit.

Step-by-Step Explanation

Let's trace through the first few cells of Example 1's board:

Board row 0: ["5","3",".",".","7",".",".",".","."]

Step 1: Initialize 9 empty row sets, 9 empty column sets, and 9 empty box sets.

  • rows[0..8] = {}, cols[0..8] = {}, boxes[0..8] = {}

Step 2: Process cell (0, 0) = '5'.

  • Row 0 set: does it contain '5'? No.
  • Col 0 set: does it contain '5'? No.
  • Box index = (0/3)*3 + (0/3) = 0. Box 0 set: does it contain '5'? No.
  • Add '5' to rows[0], cols[0], boxes[0].

Step 3: Process cell (0, 1) = '3'.

  • Row 0 set {'5'}: does it contain '3'? No.
  • Col 1 set {}: does it contain '3'? No.
  • Box index = (0/3)*3 + (1/3) = 0. Box 0 set {'5'}: does it contain '3'? No.
  • Add '3' to rows[0], cols[1], boxes[0].

Step 4: Process cell (0, 2) = '.'. Skip — empty cell.

Step 5: Process cell (0, 3) = '.'. Skip — empty cell.

Step 6: Process cell (0, 4) = '7'.

  • Row 0 set {'5','3'}: does it contain '7'? No.
  • Col 4 set {}: does it contain '7'? No.
  • Box index = (0/3)*3 + (4/3) = 1. Box 1 set {}: does it contain '7'? No.
  • Add '7' to rows[0], cols[4], boxes[1].

Step 7: Continue scanning remaining cells... all pass the triple check.

Step 8: Process cell (1, 0) = '6'.

  • Row 1 set {}: does it contain '6'? No.
  • Col 0 set {'5'}: does it contain '6'? No.
  • Box 0 set {'5','3'}: does it contain '6'? No.
  • Add '6' to rows[1], cols[0], boxes[0].

Step 9: Continue through all 81 cells. No violations found → return true.

Single Pass Validation — Checking Row, Column, and Box Simultaneously — Watch how each cell is checked against its row set, column set, and sub-box set in a single traversal. All three constraints are validated at once per cell.

Algorithm

  1. Create three arrays of sets: rows[9], cols[9], boxes[9] — each initialized as empty sets.
  2. For each cell (i, j) in the 9×9 board:
    a. If board[i][j] is '.', skip to the next cell.
    b. Let digit = board[i][j].
    c. Compute the sub-box index: box_idx = (i / 3) * 3 + (j / 3).
    d. If digit is already in rows[i] OR cols[j] OR boxes[box_idx], return false.
    e. Otherwise, add digit to rows[i], cols[j], and boxes[box_idx].
  3. If the entire board is traversed without a violation, return true.

Code

#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        unordered_set<char> rows[9], cols[9], boxes[9];
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') continue;
                
                int boxIdx = (i / 3) * 3 + (j / 3);
                
                if (rows[i].count(c) || cols[j].count(c) || boxes[boxIdx].count(c)) {
                    return false;
                }
                
                rows[i].insert(c);
                cols[j].insert(c);
                boxes[boxIdx].insert(c);
            }
        }
        return true;
    }
};
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 i in range(9):
            for j in range(9):
                c = board[i][j]
                if c == '.':
                    continue
                
                box_idx = (i // 3) * 3 + (j // 3)
                
                if c in rows[i] or c in cols[j] or c in boxes[box_idx]:
                    return False
                
                rows[i].add(c)
                cols[j].add(c)
                boxes[box_idx].add(c)
        
        return True
import java.util.HashSet;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet<Character>[] rows = new HashSet[9];
        HashSet<Character>[] cols = new HashSet[9];
        HashSet<Character>[] boxes = new HashSet[9];
        
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            boxes[i] = new HashSet<>();
        }
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') continue;
                
                int boxIdx = (i / 3) * 3 + (j / 3);
                
                if (rows[i].contains(c) || cols[j].contains(c) || boxes[boxIdx].contains(c)) {
                    return false;
                }
                
                rows[i].add(c);
                cols[j].add(c);
                boxes[boxIdx].add(c);
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(1)

We traverse the 9×9 board exactly once, visiting each of the 81 cells a single time. For each non-empty cell, we perform three O(1) set lookups and at most three O(1) set insertions. The total work is bounded by 81 × 6 = 486 constant-time operations. Since the board size is fixed and never changes, the time complexity is O(1).

Compared to the brute force, we reduced from ~3 passes to 1 pass, though both are technically O(1) due to the fixed board size.

Space Complexity: O(1)

We maintain 27 sets (9 for rows + 9 for columns + 9 for sub-boxes). Each set holds at most 9 elements (digits 1-9). The total storage is bounded by 27 × 9 = 243 entries. Since this does not grow with any variable input, the space complexity is O(1).