Start learning free

LESSON 318 OF 569 · HASH TABLE

Valid Sudoku in JavaScript: One Pass with Sets

Practice O(81) Read the full explanation

A Sudoku board is a 9 x 9 grid of cells. Each cell holds a digit from '1' to '9', or '.' while it is empty. Rows 0-2, 3-5 and 6-8 and columns 0-2, 3-5 and 6-8 split the board into nine 3 x 3 boxes.

Given a partly filled board, return true if it is valid so far, and false otherwise. The board is valid when no digit appears twice:

in the same row,
in the same column,
in the same 3 x 3 box.

Only the filled cells are checked; empty cells don't count. A valid board doesn't have to be solvable: you check the digits already on it, you don't solve the puzzle.

Rows are numbered from 0 at the top and columns from 0 at the left. In the examples, each line is one row of the board.

Example 1:

Input: board =
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Output: true
Explanation: No row, column or box holds the same digit twice.

Example 2:

Input: board =
83..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
Output: false
Explanation: The board of Example 1 with an 8 instead of the 5 in the top left corner.
Column 0 now holds two 8s, in rows 0 and 3, and so does the top left box, in rows 0 and 2.

Example 3:

Input: board =
12345678.
.........
.........
.........
........9
.........
.........
.........
.........
Output: true
Explanation: No digit repeats, so the board is valid, although it has no solution:
the last cell of row 0 can only be a 9, and column 8 already has a 9 in row 4.

Constraints:

The board has 9 rows, and each row has 9 cells.
Each cell holds a digit from '1' to '9' or '.'.

Note:

Your algorithm should look at each cell once and check it in constant time: O(81) time and O(81) extra space for the 81 cells. Scanning the row, the column and the box of every cell again would also work on a board this small, but it looks at each cell many times.

STEP 1 OF 11

Guided

Ctrl + Enter to check

JAVASCRIPT · HASH TABLE

Valid Sudoku in JavaScript, explained

Problem overview

The method isValidSudoku(board) receives a 9 x 9 grid of one-character strings: the digits '1' to '9', or '.' for an empty cell. It returns true when no digit repeats in any row, any column or any of the nine 3 x 3 boxes, and false otherwise. Only the filled cells count, and the board does not have to be solvable. The function checks the digits that are there; it never fills anything in.

For the first example board in the statement (the classic puzzle starting with 53..7....), the result is true. Replace the 5 in the top left corner with an 8 and the result is false: column 0 now holds two 8s, and so does the top left box. A board whose only filled cells are 12345678. in row 0 and a 9 at the end of row 4 is also valid, even though no completion exists, because no digit repeats.

Approach: remember what each row, column and box has seen

The slow way re-scans the row, the column and the box of every filled cell, looking for a copy of its digit. On a 9 x 9 board that is affordable, but it looks at each cell many times.

The faster idea is to visit each cell once and keep a Set of the digits seen so far for every row, every column and every box. That is 27 sets. When a digit arrives, ask its three sets whether they already contain it. If any does, the digit is a repeat and the board is invalid. If none does, add the digit to all three and move on. Each has and add on a set takes constant time, so the whole check does a fixed amount of work per cell.

The only piece that needs thought is the box number. Cell (r, c) lies in box row Math.floor(r / 3) and box column Math.floor(c / 3). Numbering the boxes left to right, then top to bottom, gives box = Math.floor(r / 3) * 3 + Math.floor(c / 3). Printing that formula for all 81 cells gives:

Cell (4, 7) is in box 5, the right box of the middle band, and the formula agrees: 1 * 3 + 2.

Step by step

Create the row sets. Array.from({ length: 9 }, () => new Set()) calls the arrow function once per slot, so each row gets its own set.
Create the column and box sets the same way. Every cell belongs to exactly one row, one column and one box, and each of those keeps its own digits.
Loop over the rows with r from 0 to 8.
Loop over the columns of that row with c from 0 to 8, so the cells are visited row by row.
Read the cell into digit.
Skip empty cells. A '.' can never break a rule, so continue moves on to the next cell.
Compute the box number with the formula above.
Check for a repeat. If the row set, the column set or the box set already has the digit, return false at once. The sets only contain cells visited earlier, so finding the digit means it appears twice.
Record the digit in the row set.
Record it in the column set and the box set too, so that later cells see it.
Return true after both loops: every filled cell was compared with all the earlier ones in its three groups and nothing repeated.

The solution in JavaScript

class Solution {
    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 r = 0; r < 9; r++) {
            for (let c = 0; c < 9; c++) {
                const digit = board[r][c];
                if (digit === '.') continue;
                const box = Math.floor(r / 3) * 3 + Math.floor(c / 3);
                if (rows[r].has(digit) || cols[c].has(digit) || boxes[box].has(digit)) {
                    return false;
                }
                rows[r].add(digit);
                cols[c].add(digit);
                boxes[box].add(digit);
            }
        }
        return true;
    }
}

JavaScript details worth knowing:

Why Array.from and not fill. new Array(9).fill(new Set()) evaluates new Set() once and puts that single object in all nine slots. Adding a digit to rows[0] would then show up in every row. Passing a function to Array.from creates a fresh set for each slot.
Digits are strings. The board holds '5', not 5. A Set compares with strict equality, so '5' and 5 would be different entries. Here every value is a string, so this is consistent, and the code never needs to convert anything.
Dividing keeps the fraction. 7 / 3 is 2.33..., not 2, because all JavaScript numbers are floating-point. Math.floor rounds it down to a whole box index.
Short-circuit ||. The three has calls run left to right and stop at the first true. The result is the same either way; only the work saved differs.

Complexity

Time: one pass over the 81 cells. The two loops run 9 x 9 times, and each visit does a constant number of set operations. For a board with n cells the work would grow linearly with n.

Space: the 27 sets. Each filled cell is stored in three of them, so they hold at most 243 entries in total. That is a fixed amount, proportional to the number of cells.

Edge cases and common mistakes

Empty board. A board of only '.' returns true; nothing is ever added to a set.
A repeat in one group only. A board with 11....... in row 0 fails on the row check, a board with a 5 at (0, 0) and another at (2, 2) fails only on the box check, and a board with a 5 at (0, 0) and another at (8, 0) fails only on the column check. A solution that forgets one of the three groups passes some of these and fails the others.
Solving the puzzle. The task is not to find the missing digits. The board with row 0 equal to 12345678. and a 9 in the last column of row 4 has no completion, yet it is valid.
Wrong box formula. Using Math.floor(r / 3) + Math.floor(c / 3) without the factor of 3 maps different boxes to the same number (the boxes at (0, 1) and (1, 0) would both become 1).
Shared sets. The fill(new Set()) shortcut makes valid boards look invalid, because every row appears to hold the digits of all the others.
Forgetting continue. Without the skip for '.', the second empty cell in a row would be reported as a repeat.

Testing

The first example board (53..7.... and so on) gives true.
The same board with an 8 instead of the 5 in the top left corner gives false.
Row 0 equal to 12345678. and a 9 at the end of row 4, all other cells empty, gives true.
Row 0 equal to 11......., all other cells empty, gives false.
A 5 at (0, 0) and another at (2, 2) gives false.
A 5 at (0, 0) and another at (8, 0) gives false.
A board with every cell empty gives true.

Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free