Valid Sudoku

Medium Top 250

Associated Patterns

Interviewed At (Company Tags)

GoogleUberAmazonMicrosoft

Problem Description

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:

A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

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

Constraints

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

Hashing Digit Coordinates

Instead of checking rows, columns, and sub-boxes in three separate nested loop passes, you can run a single pass over the board. For each filled cell at row r and column c containing digit d, record three distinct validation keys: "row: " + r + d, "col: " + c + d, and "box: " + (r/3) + "-" + (c/3) + d. If any of these keys is already present in a global hash set, the board contains duplicate digits and is invalid.

Solution 1: Single Pass Hashing

Use a hash set to collect formatted keys representing row, column, and subgrid contents.

import java.util.HashSet;

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet<String> seen = new HashSet<>();
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char val = board[r][c];
                if (val != '.') {
                    // Attempt to add row, column, and subgrid validation strings
                    if (!seen.add(val + " in row " + r) ||
                        !seen.add(val + " in col " + c) ||
                        !seen.add(val + " in box " + (r / 3) + "-" + (c / 3))) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

class Solution:
    def isValidSudoku(self, board: list[list[str]]) -> bool:
        seen = set()
        for r in range(9):
            for c in range(9):
                val = board[r][c]
                if val != '.':
                    row_key = f"{val} in row {r}"
                    col_key = f"{val} in col {c}"
                    box_key = f"{val} in box {r // 3}-{c // 3}"
                    
                    if row_key in seen or col_key in seen or box_key in seen:
                        return False
                        
                    seen.add(row_key)
                    seen.add(col_key)
                    seen.add(box_key)
        return True

#include <vector>
#include <unordered_set>
#include <string>

class Solution {
public:
    bool isValidSudoku(std::vector<std::vector<char>>& board) {
        std::unordered_set<std::string> seen;
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                char val = board[r][c];
                if (val != '.') {
                    std::string row_key = std::to_string(val) + " r " + std::to_string(r);
                    std::string col_key = std::to_string(val) + " c " + std::to_string(c);
                    std::string box_key = std::to_string(val) + " b " + std::to_string(r / 3) + "-" + std::to_string(c / 3);
                    
                    if (seen.count(row_key) || seen.count(col_key) || seen.count(box_key)) {
                        return false;
                    }
                    seen.insert(row_key);
                    seen.insert(col_key);
                    seen.insert(box_key);
                }
            }
        }
        return true;
    }
};

Complexity Analysis

Time Complexity: O(1) since the board is always fixed at 9 x 9 elements, executing exactly 81 lookups.
Space Complexity: O(1) auxiliary space as the maximum size of the hash set is bounded by 3 * 81 = 243 entries.

Where It Breaks

If the board size scales from 9 x 9 to an N² x N² grid, string serialization adds overhead. Under those circumstances, using bitmasks or an array of boolean flags is much faster than string concatenations.

Common Mistakes

Incorrect box index formula: Calculating box index as r / 3 + c / 3 instead of (r / 3) * 3 + (c / 3) or using a coordinate string wrapper like (r / 3) + "-" + (c / 3).
Validating empty cells: Attempting to hash the . character, which triggers duplicate mismatches on blank values.

Frequently Asked Questions

Does this algorithm guarantee the Sudoku is solvable? No, a Sudoku grid can contain valid numbers that cannot be solved to completion. This function only verifies the current board rules.

Why are box indices computed using floor division? Dividing row and column indices by 3 maps all cell coordinates in a specific 3x3 block to the same coordinate representation (e.g., cell (0,0) and cell (2,2) both map to box index 0-0).