Valid Sudoku - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

Understand the problem: Determine if a 9x9 Sudoku board is valid, where each row, column, and 3x3 sub-box must contain digits 1-9 without repetition, ignoring empty cells ('.').
Validate rows: Iterate through each row i from 0 to 8, using a set to track seen digits. For each cell (i, j), if the cell is not '.' and the digit is already in the set, return False; otherwise, add the digit to the set.
Validate columns: Iterate through each column j from 0 to 8, using a new set. For each cell (i, j), if the cell is not '.' and the digit is in the set, return False; otherwise, add the digit to the set.
Validate 3x3 sub-boxes: Define starting coordinates for the nine 3x3 sub-boxes (e.g., (0,0), (0,3), (0,6), etc.). For each sub-box, use a set to track digits. Iterate through the 3x3 cells; if a digit is not '.' and is in the set, return False; otherwise, add it to the set.
If all checks pass, return True, indicating the Sudoku board is valid.

Code Solution

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # Validate Rows
        for i in range(9):
            s = set()
            for j in range(9):
                item = board[i][j]
                if item in s:
                    return False
                elif item != '.':
                    s.add(item)
        
        # Validate Cols
        for i in range(9):
            s = set()
            for j in range(9):
                item = board[j][i]
                if item in s:
                    return False
                elif item != '.':
                    s.add(item)
            
        # Validate Boxes
        starts = [(0, 0), (0, 3), (0, 6),
                  (3, 0), (3, 3), (3, 6),
                  (6, 0), (6, 3), (6, 6)]
        
        for i, j in starts:
            s = set()
            for row in range(i, i+3):
                for col in range(j, j+3):
                    item = board[row][col]
                    if item in s:
                        return False
                    elif item != '.':
                        s.add(item)
        return True

# Time Complexity: O(n^2)
# Space Complexity: O(n)

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

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // Validate Rows
        for (int i = 0; i < 9; i++) {
            unordered_set<char> set;
            for (int j = 0; j < 9; j++) {
                char item = board[i][j];
                if (item != '.' && !set.insert(item).second) {
                    return false;
                }
            }
        }

        // Validate Columns
        for (int i = 0; i < 9; i++) {
            unordered_set<char> set;
            for (int j = 0; j < 9; j++) {
                char item = board[j][i];
                if (item != '.' && !set.insert(item).second) {
                    return false;
                }
            }
        }

        // Validate 3x3 Sub-grids
        vector<vector<int>> starts = {{0, 0}, {0, 3}, {0, 6},
                                      {3, 0}, {3, 3}, {3, 6},
                                      {6, 0}, {6, 3}, {6, 6}};
        
        for (auto& start : starts) {
            unordered_set<char> set;
            for (int row = start[0]; row < start[0] + 3; row++) {
                for (int col = start[1]; col < start[1] + 3; col++) {
                    char item = board[row][col];
                    if (item != '.' && !set.insert(item).second) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
};

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

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        // Validate Rows
        for (int i = 0; i < 9; i++) {
            Set<Character> set = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                char item = board[i][j];
                if (item != '.' && !set.add(item)) {
                    return false;
                }
            }
        }

        // Validate Columns
        for (int i = 0; i < 9; i++) {
            Set<Character> set = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                char item = board[j][i];
                if (item != '.' && !set.add(item)) {
                    return false;
                }
            }
        }

        // Validate 3x3 Sub-grids
        int[][] starts = {{0, 0}, {0, 3}, {0, 6},
                          {3, 0}, {3, 3}, {3, 6},
                          {6, 0}, {6, 3}, {6, 6}};
        
        for (int[] start : starts) {
            Set<Character> set = new HashSet<>();
            for (int row = start[0]; row < start[0] + 3; row++) {
                for (int col = start[1]; col < start[1] + 3; col++) {
                    char item = board[row][col];
                    if (item != '.' && !set.add(item)) {
                        return false;
                    }
                }
            }
        }

        return true;
    }
}

var isValidSudoku = function(board) {
    // Validate Rows
    for (let i = 0; i < 9; i++) {
        let set = new Set();
        for (let j = 0; j < 9; j++) {
            let item = board[i][j];
            if (item !== '.' && set.has(item)) {
                return false;
            }
            set.add(item);
        }
    }

    // Validate Columns
    for (let i = 0; i < 9; i++) {
        let set = new Set();
        for (let j = 0; j < 9; j++) {
            let item = board[j][i];
            if (item !== '.' && set.has(item)) {
                return false;
            }
            set.add(item);
        }
    }

    // Validate 3x3 Sub-grids
    let starts = [[0, 0], [0, 3], [0, 6],
                  [3, 0], [3, 3], [3, 6],
                  [6, 0], [6, 3], [6, 6]];
    
    for (let [startRow, startCol] of starts) {
        let set = new Set();
        for (let row = startRow; row < startRow + 3; row++) {
            for (let col = startCol; col < startCol + 3; col++) {
                let item = board[row][col];
                if (item !== '.' && set.has(item)) {
                    return false;
                }
                set.add(item);
            }
        }
    }

    return true;
};

Detailed Explanation

Understanding the Problem: Valid Sudoku

The “Valid Sudoku” problem asks us to determine whether a partially filled 9×9 Sudoku board is valid. A board is valid if:

Each row contains the digits 1–9 with no duplicates
Each column contains the digits 1–9 with no duplicates
Each of the nine 3×3 sub-boxes contains the digits 1–9 with no duplicates

Empty cells are represented by the character '.' and should be ignored during validation.

Why This Problem Matters

Validating a Sudoku board is a useful exercise in applying set logic, matrix traversal, and multi-dimensional constraints. It frequently appears in coding interviews because it combines pattern checking with efficient scanning of 2D structures.

Brute Force Approach: Rule-by-Rule Validation

The problem can be broken down into three separate validations:

Check each row: Iterate across each row using a set to track seen digits. If a digit reappears, return false.
Check each column: For every column index, scan from top to bottom. Use a set to detect duplicate digits.
Check each 3x3 sub-box: There are 9 sub-boxes starting at positions (0,0), (0,3), (0,6), (3,0), (3,3), etc. For each sub-box:
- Use a set to track seen digits
- Iterate through the 3 rows and 3 columns within the sub-box
- If a digit is already in the set, return false

If no violations are found in any row, column, or sub-box, the board is valid.

Example Walkthrough

Here's a sample valid board layout:

[
  ["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"]
]

Each row, column, and 3×3 box in this board has no duplicates (ignoring '.'), so it is valid.

Time and Space Complexity

Time Complexity: O(1) – The board is always 9×9, so we iterate over a constant number of cells.
Space Complexity: O(1) – We use fixed-size sets for rows, columns, and boxes, each handling at most 9 digits.

Edge Cases to Consider

An entirely empty board → valid
A full board with valid entries → valid
A board with duplicate digits in any row, column, or box → invalid
A board with non-digit, non-dot characters → assume invalid unless input constraints guarantee otherwise

Conclusion

The “Valid Sudoku” problem teaches how to apply multiple constraints across different dimensions of a matrix. By using simple data structures like sets and scanning in a structured way, you can implement an elegant and efficient solution that checks all rules without overcomplication.

Get Personalized Support at AlgoMap Bootcamp 💡