Start learning free

LESSON 322 OF 573 · HASH TABLE

Valid Sudoku in TypeScript: One Pass with Sets, O(81)

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:

  1. in the same row,
  2. in the same column,
  3. 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
    Ctrl + Enter to check

    TYPESCRIPT · HASH TABLE

    Valid Sudoku in TypeScript, explained

    Problem overview

    The method isValidSudoku receives a 9 x 9 board, a string[][] where each cell is a digit character from '1' to '9' or '.' for an empty cell. It returns true when no digit appears twice in the same row, the same column or the same 3 x 3 box, and false otherwise.

    Only the filled cells are checked. The puzzle does not have to be solvable: a board with just the digits 1 to 8 in the top row and a 9 in the fifth row is valid, even though no one could finish it. The task is to inspect what is already on the board, not to solve it.

    The well-known example board starting with 53..7.... gives true. Changing its first digit from 5 to 8 gives false, because column 0 then holds two 8s (rows 0 and 3), and so does the top left box (rows 0 and 2).

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

    You could scan the row, the column and the box of every cell again each time. On a board this small that works, but it looks at each cell many times. A single pass is simpler: visit the cells once, and keep a record of the digits seen so far in every row, every column and every box.

    That record is a Set of digits for each of the 9 rows, 9 columns and 9 boxes: 27 sets in all. For each filled cell you ask three questions, and each answer takes constant time with has: is this digit already in my row's set, my column's set, or my box's set? If any answer is yes, the digit repeats and the board is invalid. Otherwise you add the digit to all three sets and move on. If the loops finish without a repeat, the board is valid.

    The only tricky part is finding a cell's box. The boxes are numbered left to right, then top to bottom, from 0 to 8. The cell at row r, column c is in box row Math.floor(r / 3) and box column Math.floor(c / 3), so its box number is the box row times 3 plus the box column. For example, the cells (0, 0), (4, 7), (8, 8) and (3, 5) are in boxes 0, 5, 8 and 4.

    Step by step

    1. Create the row sets. rows is an array of 9 empty Set<string> objects, built with Array.from and an arrow function that creates a new set for each place. rows[r] then holds the digits seen so far in row r.
    2. Create cols and boxes the same way.
    3. Loop over the rows with r from 0 to 8.
    4. Loop over the columns of that row with c from 0 to 8, so every cell is visited, row by row.
    5. Read the cell into a const named digit.
    6. Skip empty cells with continue when the digit is '.'. Empty cells never break a rule.
    7. Compute the box number in a const named box.
    8. Look for a repeat. If the row set, the column set or the box set already has the digit, return false right away.
    9. Record the digit in the row set.
    10. Record it in the column and box sets too.
    11. Return true after both loops: every filled cell was compared with the ones before it, and none repeated.

    The solution in TypeScript

    class Solution {
    isValidSudoku(board: string[][]): boolean {
        const rows: Set<string>[] = Array.from({ length: 9 }, () => new Set<string>());
        const cols: Set<string>[] = Array.from({ length: 9 }, () => new Set<string>());
        const boxes: Set<string>[] = Array.from({ length: 9 }, () => new Set<string>());
        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;
    }
}

    Details that matter in TypeScript:

    • Why Array.from with a function. new Array(9).fill(new Set()) looks shorter but creates one set and puts that same set in all 9 places. Adding a 5 to rows[0] would then also make rows[8].has('5') true. The arrow function passed to Array.from runs once per place, so each place gets its own set.
    • The type annotation on the sets. Set<string>[] says that each set holds strings, and board[r][c] is a string. Annotations are erased when the code is compiled to JavaScript, so they only help the compiler catch mistakes such as adding a number to a set of strings.
    • Digits stay characters. The cells are strings such as '5'. There is no need to convert them to numbers: a set of strings works just as well, and '.' can be tested directly with ===.
    • Math.floor and division. In JavaScript and TypeScript, / keeps the fraction: 7 / 3 is 2.3333333333333335. Without Math.floor, the box number would be a fractional value and could never match an array position.
    • if (digit === '.') continue; without braces is legal for a single statement. continue jumps to the next value of c.
    • Short-circuit ||. The three has checks stop at the first one that is true. The result is the same either way, since the checks have no side effects.

    Complexity

    Time: O(81), which is constant. The loops visit each of the 81 cells once, and each visit does at most three has and three add calls on sets, which take constant time on average.

    Space: O(81), also constant. The 27 sets together hold at most 81 digits, because each cell adds a digit to exactly one row set, one column set and one box set, and a set holds at most 9 distinct digits.

    Edge cases and common mistakes

    • An empty board. Every cell is skipped, so the method returns true. An empty board does not break any rule.
    • A repeat in only one of the three groups. Two 5s in row 0 (columns 0 and 8) are caught by the row set. Two 5s in column 0 (rows 0 and 8) are caught by the column set. Two 5s at (0, 0) and (2, 2) are in different rows and columns, and only the box set catches them. Each of those boards makes the method return false, so all three checks are needed.
    • The same digit in unrelated places. A 5 at (0, 0) and another at (3, 3) share no row, column or box, so the board stays valid.
    • Treating '.' as a digit. Without the continue, the second empty cell in a row would look like a repeat and the method would reject almost every board.
    • A wrong box formula. Using r / 3 + c / 3 mixes the row and the column in the same fractional number. Row times 3 plus column, after rounding each down, gives a different number for every box.
    • Solving the puzzle. The method is not asked to find out whether the board has a solution, only whether the digits placed break a rule. The board with 1 to 8 in the top row and a 9 at row 4, column 8 is valid, and the method returns true.

    Testing

    Results from running the method:

    • The board starting with 53..7.... gives true.
    • The same board with the first digit changed to 8 gives false.
    • The board with 12345678. in the top row and a single 9 at the end of the fifth row gives true.
    • A board with nothing but . gives true.
    • Two 5s in one row, in one column or in one box each give false.
    • A 5 at (0, 0) and another at (3, 3) gives true.
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free