Valid Sudoku

MediumHash TableMatrix
Category: Array & Hashing
Companies that ask this question:
AmazonGoogleFacebookApple

Approach

Valid Sudoku

Problem Statement

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 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

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: First row and first column both have '8'.

Constraints

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

Approach

Key Insight

We need to track which digits we've seen in:

  1. Each row (9 sets)
  2. Each column (9 sets)
  3. Each 3x3 sub-box (9 sets)

Use HashSets for O(1) lookup!

Sub-box Index Calculation

For a cell at position (row, col), its sub-box index is:

boxIndex = (row / 3) * 3 + (col / 3)

This maps the 9 sub-boxes to indices 0-8.

Algorithm

  1. Create HashSets for:
    • 9 rows
    • 9 columns
    • 9 boxes
  2. For each cell:
    • Skip if empty ('.')
    • Check if digit already exists in its row/column/box
    • If yes → return false
    • If no → add to all three sets
  3. Return true if no duplicates found

Complexity Analysis

  • Time Complexity: O(1)
    • Board is fixed 9x9 = 81 cells
    • Constant time operations
  • Space Complexity: O(1)
    • Fixed storage for 27 sets (9+9+9)
    • Each set has at most 9 elements

Pattern Recognition

This problem demonstrates:

  • HashSet for duplicate detection
  • Matrix traversal
  • Index mapping - converting 2D to 1D (box calculation)
  • Multiple constraint checking simultaneously

Solution

java
1import java.util.*;
2
3class Solution {
4    // Optimal Solution: Using HashSets
5    public boolean isValidSudoku(char[][] board) {
6        // Create sets for rows, columns, and boxes
7        Set<String> seen = new HashSet<>();
8
9        for (int row = 0; row < 9; row++) {
10            for (int col = 0; col < 9; col++) {
11                char num = board[row][col];
12
13                // Skip empty cells
14                if (num == '.') continue;
15
16                // Calculate box index: (row/3)*3 + (col/3)
17                int boxIndex = (row / 3) * 3 + (col / 3);
18
19                // Create unique keys for row, column, and box
20                String rowKey = num + " in row " + row;
21                String colKey = num + " in col " + col;
22                String boxKey = num + " in box " + boxIndex;
23
24                // Check if number already exists
25                if (seen.contains(rowKey) ||
26                    seen.contains(colKey) ||
27                    seen.contains(boxKey)) {
28                    return false;
29                }
30
31                // Add to seen set
32                seen.add(rowKey);
33                seen.add(colKey);
34                seen.add(boxKey);
35            }
36        }
37
38        return true;
39    }
40
41    // Alternative: Using Arrays of HashSets
42    public boolean isValidSudokuArrays(char[][] board) {
43        // Create separate sets for rows, columns, and boxes
44        @SuppressWarnings("unchecked")
45        Set<Character>[] rows = new HashSet[9];
46        @SuppressWarnings("unchecked")
47        Set<Character>[] cols = new HashSet[9];
48        @SuppressWarnings("unchecked")
49        Set<Character>[] boxes = new HashSet[9];
50
51        // Initialize sets
52        for (int i = 0; i < 9; i++) {
53            rows[i] = new HashSet<>();
54            cols[i] = new HashSet<>();
55            boxes[i] = new HashSet<>();
56        }
57
58        // Check each cell
59        for (int row = 0; row < 9; row++) {
60            for (int col = 0; col < 9; col++) {
61                char num = board[row][col];
62
63                if (num == '.') continue;
64
65                // Calculate box index
66                int boxIndex = (row / 3) * 3 + (col / 3);
67
68                // Check if number exists in row, column, or box
69                if (rows[row].contains(num) ||
70                    cols[col].contains(num) ||
71                    boxes[boxIndex].contains(num)) {
72                    return false;
73                }
74
75                // Add number to sets
76                rows[row].add(num);
77                cols[col].add(num);
78                boxes[boxIndex].add(num);
79            }
80        }
81
82        return true;
83    }
84}
85
Loading visualizer...