36. Valid Sudoku

At a Glance

Topic: arrays-hashing
Pattern: Hash Set per Row/Col/Box
Difficulty: Medium
Companies: Amazon, Google, Meta, Apple, Bloomberg
Frequency: High
LeetCode: 36

Problem (one-liner)

Given a 9 × 9 Sudoku board (partially filled with digits '1'–'9' and '.'), return true if no digit repeats in any row, column, or 3 × 3 box.

Recognition Cues

"Valid Sudoku", "no duplicates in row, column, subgrid"
Nine rows, nine columns, nine boxes — group membership

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — for each cell, scan row/col/box — O(81 · 27) ≈ constant but ugly.
Better — sets per row, col, box — O(81) time / O(81) space.
Optimal — same: fixed board size; bitsets or arrays of sets for each constraint.

Optimal Solution

Go

package main

func isValidSudoku(board [][]byte) bool {
	rows := [9]map[byte]bool{}
	cols := [9]map[byte]bool{}
	boxes := [9]map[byte]bool{}
	for index := range rows {
		rows[index] = map[byte]bool{}
		cols[index] = map[byte]bool{}
		boxes[index] = map[byte]bool{}
	}
	for row := 0; row < 9; row++ {
		for col := 0; col < 9; col++ {
			digit := board[row][col]
			if digit == '.' {
				continue
			}
			boxIndex := (row/3)*3 + col/3
			if rows[row][digit] || cols[col][digit] || boxes[boxIndex][digit] {
				return false
			}
			rows[row][digit] = true
			cols[col][digit] = true
			boxes[boxIndex][digit] = 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 row = 0; row < 9; row++) {
		for (let col = 0; col < 9; col++) {
			const digit = board[row][col];
			if (digit === '.') {
				continue;
			}
			const boxIndex = Math.floor(row / 3) * 3 + Math.floor(col / 3);
			if (rows[row].has(digit) || cols[col].has(digit) || boxes[boxIndex].has(digit)) {
				return false;
			}
			rows[row].add(digit);
			cols[col].add(digit);
			boxes[boxIndex].add(digit);
		}
	}
	return true;
}