36. Valid Sudoku

Quick Identifier

• Topic: arrays-hashing
• Pattern: Multiple Hash Sets
• Hint: Maintain separate tracking sets for each of the 9 rows, 9 columns, and 9 sub-boxes. The trickiest part is the mathematical formula to map a (row, col) coordinate to a flat boxIndex.
• Difficulty: Medium
• Companies: Amazon, Google, Meta, Apple, Bloomberg
• LeetCode: 36

Quick Sights

• Time Complexity: O(1) or O(N^2). Since the board is strictly fixed at $9 \times 9$, iterating through all 81 cells takes constant time $O(81) = O(1)$. If generalized to an $N \times N$ board, it is $O(N^2)$.
• Space Complexity: O(1) or O(N^2). We allocate 27 hash sets (or arrays), each holding at most 9 digits. This is bounded and constant $O(27 \times 9) = O(1)$.
• Core Mechanism: We iterate over every cell. If a cell contains a digit, we check three conditions:
  1. Is this digit already in the current row's set?
  2. Is this digit already in the current column's set?
  3. Is this digit already in the current $3 \times 3$ box's set? If any of these are true, the board is invalid. Otherwise, we add the digit to all three corresponding sets and continue.

Concept Explanation

As a senior engineer, the structural challenge here isn't the iteration—it's the State Representation and Coordinate Mapping.

1. State Representation: We need to ask three independent questions for every cell. Trying to do this by rescanning the board is absurd. Instead, we pre-allocate "memory banks" (Sets or fixed arrays): 9 for the rows, 9 for the columns, and 9 for the boxes.
2. Coordinate Mapping (The Box Formula): Rows and columns map easily. Row 5 uses rows[5]. Column 4 uses cols[4]. But which of the 9 boxes does (row 5, col 4) belong to?
   • Think of the $9 \times 9$ board as a $3 \times 3$ grid of macro-boxes.
   • The "macro-row" of a box is floor(row / 3).
   • The "macro-col" of a box is floor(col / 3).
   • To flatten a 2D (macro-row, macro-col) coordinate into a 1D index (from 0 to 8), you multiply the macro-row by the grid width (3) and add the macro-col:
   • boxIndex = floor(row / 3) * 3 + floor(col / 3)
3. Single Pass Evaluation: Because Sudoku rules only care about duplicates of existing filled numbers, we can populate our tracking sets and check for violations simultaneously in a single pass.

Diagram

This flowchart highlights the lookup logic and the critical boxIndex calculation.

Study Pattern (SDE3+)

• 0–3 min: Confidently state that since the board is fixed at $9 \times 9$, the problem is strictly $O(1)$ time and space, but explain the $O(N^2)$ generalization. Write down the boxIndex formula immediately, as it proves you aren't memorizing code but understand 2D-to-1D index flattening.
• Implementation pass: Use Arrays of Arrays or Arrays of Hash Sets. In languages like Go or C++, an array of boolean arrays [9][9]bool is incredibly fast and avoids the overhead of Hash Maps entirely.
• 5 min extension: What if memory was extremely constrained? You can swap the Hash Sets for Bitmasks. An integer has 32 bits. You only need 9 bits to represent digits 1-9. rows[row] |= (1 << digit) sets the bit. (rows[row] & (1 << digit)) != 0 checks if it was already set. This reduces the space from 27 Hash Sets to just an array of 27 integers.

Approaches

• Brute force — For every cell, run a loop across its row, column, and box. Time: $O(81 \cdot 27)$, Space: $O(1)$. It's technically $O(1)$, but computationally wasteful.
• Hash Sets / Boolean Arrays — Time: $O(81) \to O(1)$, Space: $O(81) \to O(1)$. (Pick this)
• Bitmasking — Time: $O(1)$, Space: $O(1)$ (only 27 integers used). Best for systems-level interviews.

Optimal Solution

Go

func isValidSudoku(board [][]byte) bool {
	// Use arrays of booleans instead of maps for faster O(1) performance
	var rows [9][9]bool
	var cols [9][9]bool
	var boxes [9][9]bool

	for r := 0; r < 9; r++ {
		for c := 0; c < 9; c++ {
			if board[r][c] == '.' {
				continue
			}

			// Convert byte '1'-'9' to integer 0-8 for zero-indexed array access
			val := board[r][c] - '1'

			// Flatten the 2D box coordinate to a 1D index
			boxIndex := (r/3)*3 + (c/3)

			// Check if we've seen this value before in this row, col, or box
			if rows[r][val] || cols[c][val] || boxes[boxIndex][val] {
				return false
			}

			// Mark as seen
			rows[r][val] = true
			cols[c][val] = true
			boxes[boxIndex][val] = true
		}
	}

	return true
}

JavaScript

function isValidSudoku(board) {
	const rows = Array.from({ length: 9 }, () => new Set());
	const cols = Array.from({ length: 9 }, () => new Set());
	const boxes = Array.from({ length: 9 }, () => new Set());

	for (let r = 0; r < 9; r++) {
		for (let c = 0; c < 9; c++) {
			const cell = board[r][c];
			if (cell === '.') continue;

			// Flatten the 2D box coordinate to a 1D index
			const boxIndex = Math.floor(r / 3) * 3 + Math.floor(c / 3);

			// Check if the value violates Sudoku rules
			if (rows[r].has(cell) || cols[c].has(cell) || boxes[boxIndex].has(cell)) {
				return false;
			}

			// Mark as seen
			rows[r].add(cell);
			cols[c].add(cell);
			boxes[boxIndex].add(cell);
		}
	}

	return true;
}

Walkthrough

Tracing a conflict in the top-left box:

Output: false

Edge Cases

• Completely empty board (Returns true).
• Partially filled but totally valid board (Returns true).
• A board that is mathematically unsolvable, but currently has no rule violations (Returns true. The problem only asks if the current state violates rules, not if a full solution is possible).

Pitfalls

• Calculating the boxIndex using floating-point math in JS without Math.floor(). (1/3) * 3 is 1, not 0.
• Thinking you have to solve the Sudoku. Read carefully: it just asks to validate the current numbers.
• Mixing up rows and columns when initializing 2D arrays or arrays of sets.

Similar Problems

• 37. Sudoku Solver — The Hard backtracking sequel to this problem.
• 73. Set Matrix Zeroes — Matrix state tracking utilizing row and column arrays.

Mind-Map Tags

#matrix #hashset #sudoku #grid-indexing #validation