Valid Sudoku

Valid Sudoku is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Hashing - Previously Seen / Existence Check subpattern.

Problem statement

Implement isValidSudoku to determine whether the filled entries in board follow the rules of a 9x9 Sudoku grid. Each cell contains either a digit from '1' through '9' or '.', where '.' means the cell is empty.

Every digit that appears in a row must be different from all other digits in that row. The same requirement applies independently to each column and to each 3x3 subgrid; a subgrid is one of the nine regions formed by three consecutive rows and three consecutive columns.

Return true if no filled digit violates any row, column, or subgrid rule. Return false as soon as any duplicate is found. Empty cells are ignored, and the board does not need to be complete or solvable.

Example 1:

Input: board = [["4",".",".",".","7",".",".",".","."],[".",".","8",".",".",".",".","1","."],[".",".",".","2",".",".","6",".","."],[".","5",".",".",".","9",".",".","."],[".",".","1",".","3",".",".",".","7"],[".",".",".","6",".",".","4",".","."],[".","2",".",".",".",".",".","8","."],[".",".","6",".",".",".","3",".","."],[".",".",".","9",".",".",".",".","5"]] Output: true Explanation: Every filled digit is unique within its row, column, and 3x3 subgrid.

Example 2:

Input: board = [["4",".",".",".",".",".",".",".","."],[".","4",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]] Output: false Explanation: The two '4' cells lie in the same upper-left 3x3 subgrid, so that subgrid contains a duplicate.

Example 3:

Input: board = [[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]] Output: true Explanation: There are no filled cells, so no row, column, or subgrid can contain a duplicate.

Constraints:

- board contains exactly 9 rows. - Every row in board contains exactly 9 cells. - Each cell is a one-character string equal to '.' or one of '1' through '9'. - Only filled cells are checked; empty cells represented by '.' impose no restriction. - The input board may be incomplete and is not guaranteed to have a solution.

Topics and companies

Topics: Array, Matrix, Hash Table, Hash Function.

How to practise Valid Sudoku on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) for the fixed 9x9 board (more generally, O(n^2) for an n x n board). time and O(1) for the fixed 9x9 board. space.

Open Valid Sudoku in the code editor, or read the Valid Sudoku editorial for a worked solution with its approach and complexity analysis.

Where Valid Sudoku sits in the DSA pattern sheet

Problems related to Valid Sudoku

Other problems that use the same Hashing - Previously Seen / Existence Check and Array/Matrix Manipulation Patterns techniques:

Preparing this workspace.