valid-sudoku.sh — zsh
← listnormal view →

Valid Sudoku

medium
Binary Tree Postorder TraversalFind All Duplicates in an Array
matrixhashingarrays

You are given a 9 x 9 Sudoku board encoded as int[][] board, where 0 denotes an empty cell (instead of '.') and the integers 1 through 9 represent filled digits. Determine whether the board is valid by checking only the filled cells.

A Sudoku board is valid if:

  • each row contains no repeated digit from 1 to 9 (ignoring 0s)
  • each column contains no repeated digit from 1 to 9
  • each 3 x 3 sub-box contains no repeated digit from 1 to 9

The board does not need to be solvable. You only need to verify that the currently filled cells do not violate the rules.

Input / output

  • Input: board: int[][] where board.length == 9 and board[i].length == 9
  • Output: boolean — true if the filled cells form a valid Sudoku state, otherwise false

Constraints

  • board.length == 9
  • board[i].length == 9
  • 0 <= board[i][j] <= 9
  • 0 means the cell is empty
  • Only the filled cells must satisfy the Sudoku rules

Follow-up

Can you solve it in a single pass over the board by tracking used digits for each row, column, and 3 x 3 box as you go?

Examples
Example 1
Input: board = [[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]]
Output: true
Example 2
Input: board = [[5,3,5,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,0,6,0],[8,0,0,0,6,0,0,0,3],[4,0,0,8,0,3,0,0,1],[7,0,0,0,2,0,0,0,6],[0,6,0,0,0,0,2,8,0],[0,0,0,4,1,9,0,0,5],[0,0,0,0,8,0,0,7,9]]
Output: false
Example 3
Input: board = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
Output: true