Valid Sudoku

Q: What is the time complexity of Valid Sudoku?

The board always has 81 cells, so both approaches run in O(1) time and use O(1) memory. For a general n × n Sudoku the one-pass check reads each of the n² cells once and keeps 3n² flags, so it is O(n²) in time and memory.

Q: How do you find which 3 × 3 box a cell is in?

With integer division, r / 3 is the band of rows (0, 1 or 2) and c / 3 is the stack of columns. (r / 3) * 3 + c / 3 numbers the boxes 0 to 8, left to right and top to bottom. Cell (7, 1) is in box 2 * 3 + 0 = 6 , the bottom-left one.

MediumHashing

+10

You get a 9 × 9 Sudoku board as board, a list of 9 strings with 9 characters each, one string per row. Each character is a digit from 1 to 9 or . for an empty cell. Return true if no digit appears twice in the same row, the same column or the same 3 × 3 box, and false otherwise. Only the filled cells are checked: the board does not have to be solvable.

Function

isValidSudoku(board: string-array) → boolean

boardstring-array: 9 strings of 9 characters, one per row, digits 1 to 9 and . for an empty cell
Returnsboolean: true if no row, column or 3 × 3 box repeats a digit, false otherwise

Constraints

board.length == 9 and board[i].length == 9
board[i][j] is a digit from 1 to 9 or .
The board may be impossible to complete; only repeats among the filled cells matter.

Examples

Input: board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
Output: true
Explanation: Every row, column and box holds each digit at most once. Row 4 (counting from 0), .74..89.3, has 7, 4, 8, 9 and 3 once each, and the same holds for the other 26 groups, so the answer is true.

Input: board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
Output: false
Explanation: Row 0 and row 7 both start with a 3, so column 0 holds two 3s. The two cells are in different rows and different boxes; only the column check catches this one.

Input: board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
Output: false
Explanation: The 5 at row 0, column 8 and the 5 at row 2, column 7 are in different rows and different columns, but both are in the top-right box, so the answer is false.

+16 hidden tests on Submit

Follow-up

Generalize the check to a 16 × 16 board with 4 × 4 boxes and the symbols 1 to 9 and A to G. Which numbers in your code depend on the board size, and what does the box formula become?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Every digit belongs to three groups at once: its row, its column and its 3 × 3 box. Rows and columns are direct to index; the box is where most bugs live. Number the boxes 0 to 8 with (r / 3) * 3 + c / 3 and a single pass over the 81 cells can check all 27 groups together.

Check each row, column and box on its own

Intuition

The rules name 27 groups: 9 rows, 9 columns and 9 boxes. Gather the nine cells of each group and ask whether a digit repeats among them, ignoring the dots. If no group has a repeat, the board is valid.

Row i is board[i][0..8] and column i is board[0..8][i]. Box i starts at row 3 * (i / 3) and column 3 * (i % 3) with integer division, so box 5 starts at row 3, column 6. Its cell k is k / 3 rows down and k % 3 columns right of that corner.

To find a repeat among nine cells, keep a seen flag per digit and stop at the first digit that is already flagged. Each of the 81 cells is read three times, once for each group it belongs to: 243 reads, a fixed amount of work. On an n × n board the same method costs O(n²).

Algorithm

For i from 0 to 8, collect row i, column i and box i, nine cells each.
Box i starts at top = 3 * (i / 3) and left = 3 * (i % 3); its cell k is at row top + k / 3, column left + k % 3.
For each group, walk its cells with fresh seen flags, skipping dots.
If a digit is already flagged, return false.
After all 27 groups, return true.

def has_repeat(cells):
    seen = set()
    for ch in cells:
        if ch == '.':
            continue
        if ch in seen:
            return True
        seen.add(ch)
    return False


def isValidSudoku(board):
    for r in range(9):
        if has_repeat(board[r][c] for c in range(9)):
            return False
    for c in range(9):
        if has_repeat(board[r][c] for r in range(9)):
            return False
    for top in (0, 3, 6):
        for left in (0, 3, 6):
            box = (board[top + i][left + j] for i in range(3) for j in range(3))
            if has_repeat(box):
                return False
    return True

One pass with a seen table per row, column and box

Intuition

Instead of gathering groups, visit each cell once and ask all three questions at the same time. Keep three tables of 9 × 9 flags: seenRow[r][d] says digit d+1 is already in row r, and seenCol and seenBox work the same way for columns and boxes.

Cell (r, c) belongs to box (r / 3) * 3 + c / 3. The first part picks the band of three boxes (rows 0 to 2 give band 0, rows 3 to 5 band 1, rows 6 to 8 band 2), and c / 3 picks the box inside the band. Cell (4, 7) lands in box 1 * 3 + 2 = 5, the middle-right box.

For each filled cell, if any of its three flags is already set, the digit repeats in that group and you return false at once. Otherwise you set all three. Each cell is read once and the tables hold 243 flags, so time and memory are fixed for a 9 × 9 board, and O(n²) for an n × n one.

Algorithm

Create seenRow, seenCol and seenBox, each 9 × 9 and all false.
Visit every cell (r, c); skip it if it holds a dot.
Let d be the digit minus 1 and b = (r / 3) * 3 + c / 3.
If seenRow[r][d], seenCol[c][d] or seenBox[b][d] is true, return false.
Otherwise set all three to true. After the last cell, return true.

def isValidSudoku(board):
    # seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
    seen_row = [[False] * 9 for _ in range(9)]
    seen_col = [[False] * 9 for _ in range(9)]
    seen_box = [[False] * 9 for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == '.':
                continue
            d = int(ch) - 1
            b = (r // 3) * 3 + c // 3
            if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
                return False
            seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
    return True

Pitfalls and edge cases

The row and column checks rarely go wrong. The bugs are in the box index and in what counts as a repeat.

Computing the box as r / 3 + c / 3. That gives only 0 to 4, so cells (0, 3) and (3, 0) share a number though they are in different boxes, and two 7s there are reported as a repeat. Use (r / 3) * 3 + c / 3.
Dividing with / in JavaScript, Python 3 or Lua, where 4 / 3 is 1.33, not a box number. Use Math.floor, // or math.floor.
Treating . as a value. An empty board has nine dots in every row, and it is valid.
Trying to solve the puzzle. With 12345678. as row 0 and a 9 lower down in column 8, the last cell of row 0 can never be filled, yet no group repeats a digit, so the answer is true.
Checking rows and columns but not boxes. A full grid where each row is the previous one shifted left by one place has no repeat in any row or column, while every box holds repeats.

Frequently asked questions4

What is the time complexity of Valid Sudoku?

The board always has 81 cells, so both approaches run in O(1) time and use O(1) memory. For a general n × n Sudoku the one-pass check reads each of the n² cells once and keeps 3n² flags, so it is O(n²) in time and memory.

Does a valid Sudoku board have to be solvable?

No. Valid here means only that no digit repeats in a row, a column or a 3 × 3 box among the cells already filled. A board can pass that check and still have no solution. Deciding solvability needs a search such as backtracking, which is a different problem.

How do you find which 3 × 3 box a cell is in?

With integer division, r / 3 is the band of rows (0, 1 or 2) and c / 3 is the stack of columns. (r / 3) * 3 + c / 3 numbers the boxes 0 to 8, left to right and top to bottom. Cell (7, 1) is in box 2 * 3 + 0 = 6, the bottom-left one.

Can Valid Sudoku be solved with bit masks?

Yes. Give each row, column and box one integer, and let bit d mean digit d+1 has been seen. For a filled cell, compute 1 << d; if it ANDs to nonzero with any of the three masks, the digit repeats, otherwise OR it into all three. That is 27 integers instead of 243 flags, with the same one-pass logic.

Python

def isValidSudoku(board):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]

Expected

true