Valid Sudoku

36. Valid Sudoku

Medium

Determine if a 9x9 Sudoku board is valid according to Sudoku rules.

ArrayHash TableMatrix

View Problem

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

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: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Constraints:

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

Try It Yourself

TypeScript

function isValidSudoku(board: string[][]): boolean {
    // Your solution here
}

Go

func isValidSudoku(board [][]string) bool {
    // Your solution here
}

Solution

Click to reveal solution

Validate each row, column, and 3x3 sub-box separately by checking for duplicate digits.

TypeScript Solution

function isValidSudoku(board: string[][]): boolean {
  for (let i = 0; i < board.length; i++) {
      if (!isValidRow(board, i)) {
          return false;
      }
  }

  for (let j = 0; j < board.length; j++) {
      if (!isValidCol(board, j)) {
          return false;
      }
  }

  for (const anchor of getAnchors()) {
      if (!isValidZone(board, anchor)) {
          return false;
      }
  }

  return true;
}

function isValidRow(board: string[][], rowIndex: number): boolean {
  return isValidSet(board[rowIndex]);
}

function isValidSet(array: string[]): boolean {
  const count = {};
  for (const val of array) {
      if (val === '.') {
          continue;
      }
      count[val] ||= 0;
      count[val]++;
  }

  if (Object.keys(count).length === 0) {
      return true;
  }

  return Object.values(count).every(val => val === 1);
}

function isValidCol(board: string[][], colIndex: number): boolean {
  const colSet = [];

  board.forEach(row => {
      colSet.push(row[colIndex]);
  });

  return isValidSet(colSet);
}

function getAnchors(): [number, number][] {
  return [
      [0, 0], [0, 3], [0, 6],
      [3, 0], [3, 3], [3, 6],
      [6, 0], [6, 3], [6, 6],
  ];
}

function isValidZone(board: string[][], anchor: [number, number]): boolean {
  const zoneSet = [];

  for (let i = anchor[0]; i < anchor[0] + 3; i++) {
      for (let j = anchor[1]; j < anchor[1] + 3; j++) {
          zoneSet.push(board[i][j]);
      }
  }

  return isValidSet(zoneSet);
}

Time:O(1)

Space:O(1)

Go Solution

func isValidSudoku(board [][]string) bool {
  // Validate all rows
  for i := 0; i < len(board); i++ {
      if !isValidRow(board, i) {
          return false
      }
  }
  
  // Validate all columns
  for j := 0; j < len(board); j++ {
      if !isValidCol(board, j) {
          return false
      }
  }
  
  // Validate all 3x3 sub-boxes
  anchors := getAnchors()
  for _, anchor := range anchors {
      if !isValidZone(board, anchor) {
          return false
      }
  }
  
  return true
}

func isValidRow(board [][]string, rowIndex int) bool {
  return isValidSet(board[rowIndex])
}

func isValidSet(array []string) bool {
  count := make(map[string]int)
  
  for _, val := range array {
      if val == "." {
          continue
      }
      count[val]++
  }
  
  for _, freq := range count {
      if freq != 1 {
          return false
      }
  }
  
  return true
}

func isValidCol(board [][]string, colIndex int) bool {
  colSet := make([]string, len(board))
  
  for i, row := range board {
      colSet[i] = row[colIndex]
  }
  
  return isValidSet(colSet)
}

func getAnchors() [][2]int {
  return [][2]int{
      {0, 0}, {0, 3}, {0, 6},
      {3, 0}, {3, 3}, {3, 6},
      {6, 0}, {6, 3}, {6, 6},
  }
}

func isValidZone(board [][]string, anchor [2]int) bool {
  var zoneSet []string
  
  for i := anchor[0]; i < anchor[0]+3; i++ {
      for j := anchor[1]; j < anchor[1]+3; j++ {
          zoneSet = append(zoneSet, board[i][j])
      }
  }
  
  return isValidSet(zoneSet)
}

Time:O(1)

Space:O(1)

Algorithm:

1. Validate Rows: Check each row for duplicate digits (ignoring '.')
2. Validate Columns: Extract each column and check for duplicates
3. Validate 3x3 Sub-boxes: Use anchor points to define each 3x3 box and validate
4. Helper Function: isValidSet counts digit frequencies and ensures no duplicates

Time Complexity: O(1) - Fixed 9x9 grid size Space Complexity: O(1) - Constant extra space for validation

Optimized Single-Pass Approach:

function isValidSudoku(board: string[][]): boolean {
    const rows = Array(9).fill(null).map(() => new Set());
    const cols = Array(9).fill(null).map(() => new Set());
    const boxes = Array(9).fill(null).map(() => new Set());
    
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const val = board[i][j];
            if (val === '.') continue;
            
            const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
            
            if (rows[i].has(val) || cols[j].has(val) || boxes[boxIndex].has(val)) {
                return false;
            }
            
            rows[i].add(val);
            cols[j].add(val);
            boxes[boxIndex].add(val);
        }
    }
    
    return true;
}