Course4all
Join us on telegram
Home/dsa/Arrays & Hashing/Valid Sudoku

Valid Sudoku

Master this topic with zero to advance depth.

Valid Sudoku

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

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

Visual Representation

Box Index Formula: (row / 3) * 3 + (col / 3) Row 0-2, Col 0-2 -> Box 0 Row 0-2, Col 3-5 -> Box 1 Row 3-5, Col 0-2 -> Box 3
Medium

Examples

Input: board = [["5","3",".",".","7",".",".",".","."] ,["6",".",".","1","9","5",".",".","."] ,[.".","9","8",".",".",".",".","6","."] ...]
Output: true
Approach 1

Level I: Triple Pass

Intuition

Check rows, columns, and 3x3 boxes separately. For each check, use a boolean array or set to detect duplicates.

⏱ O(N²)💾 O(N)

Detailed Dry Run

Check Row 0: [5, 3, ., 7, .] -> Unique numbers. OK. Check Col 0: [5, 6, ., 8, 4...] -> Unique. OK.

java
import java.util.*;
class Solution {
    public boolean isValidSudoku(char[][] board) {
        for(int i=0; i<9; i++) {
            Set<Character> row = new HashSet<>(), col = new HashSet<>(), box = new HashSet<>();
            for(int j=0; j<9; j++) {
                if(board[i][j] != '.' && !row.add(board[i][j])) return false;
                if(board[j][i] != '.' && !col.add(board[j][i])) return false;
                int r = 3*(i/3) + j/3, c = 3*(i%3) + j%3;
                if(board[r][c] != '.' && !box.add(board[r][c])) return false;
            }
        }
        return true;
    }
}
Approach 2

Level II: Single Pass with HashSets

Intuition

Iterate over the board once. Maintain arrays of HashSets for rows, columns, and boxes to track seen digits.

⏱ O(N²)💾 O(N²)

Detailed Dry Run

i=4, j=4, val='5'

  • Seen in row 4? No.
  • Seen in col 4? No.
  • Seen in box (4/3)*3 + 4/3 = 4? No. Store it.
java
class Solution {
    public boolean isValidSudoku(char[][] board) {
        Set<String> seen = new HashSet<>();
        for (int i=0; i<9; ++i) {
            for (int j=0; j<9; ++j) {
                if (board[i][j] != '.') {
                    String b = "(" + board[i][j] + ")";
                    if (!seen.add(b + i) || !seen.add(j + b) || !seen.add(i/3 + b + j/3)) return false;
                }
            }
        }
        return true;
    }
}
Approach 3

Level III: Bitmasking (Optimal Space)

Intuition

Use an integer (32-bit) as a bitmask for each row, column, and box. The nn-th bit represents the presence of digit nn.

⏱ O(N²)💾 O(N) - 27 integers total.

Detailed Dry Run

i=0, val='5'. mask = 1 << 5 (binary 00100000). Set bit in row[0], col[0], box[0].

java
class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[] rows = new int[9], cols = new int[9], boxes = new int[9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int val = board[i][j] - '1';
                int box_idx = (i / 3) * 3 + j / 3;
                if (((rows[i] >> val) & 1) == 1 || ((cols[j] >> val) & 1) == 1 || ((boxes[box_idx] >> val) & 1) == 1) return false;
                rows[i] |= (1 << val);
                cols[j] |= (1 << val);
                boxes[box_idx] |= (1 << val);
            }
        }
        return true;
    }
}
← Previous QuestionCount of Smaller Numbers After Self
Next Question →Encode and Decode Strings