Skip to content

Volume ITechnology

4.4.8 — Valid Sudoku ​

LeetCode 36 · Medium

The problem ​

You are given a 9×9 Sudoku board that is partly filled in. Check whether the digits already on the board break any rule. Return true if they do not, and false if they do.

The rules are these three.

  1. Each row may not contain the same digit twice.
  2. Each column may not contain the same digit twice.
  3. Each of the nine 3×3 boxes may not contain the same digit twice.

Empty cells are written as '.' and are ignored. The digits are stored as text characters, '1' to '9'.

You are only checking the board as it stands. You are not checking whether it can be solved. A board with no repeated digits is valid, even if no legal way to finish it exists. Misreading this rule is the most common mistake on this problem.

What the problem is really asking ​

There are nine rows, nine columns and nine boxes. That is 27 groups of cells. For each group, the question is the same: "has this digit already appeared in this group?"

You have answered that exact question before, in 4.4.1 Contains Duplicate. Here you answer it 27 times at once.

So the duplicate check is not the hard part. The hard part is working out which groups a cell belongs to. Every cell sits in exactly one row, one column and one box. The row is easy: it is the cell's row number. The column is easy too. The box needs a small formula.

Think of students joining clubs. Each digit on the board is a student. Every student belongs to a row club, a column club and a box club. If any club ever gets the same student twice, the board is invalid. We keep one attendance sheet per club, and check the sheet before signing anyone in.

The brute force, and where it wastes work ​

A direct approach checks each rule separately. Walk every row and look for repeats. Then walk every column. Then walk every box. That is three passes over the board, with three slightly different loops, and the box loop is fiddly to write.

For a 9×9 board, three passes cost almost nothing, so speed is not the problem. The waste is in the code, not the time: three separate loops repeat the same duplicate check, and each one is a fresh chance for an off-by-one bug. One pass that puts each cell into its three groups is shorter and harder to get wrong.

The box index ​

The nine boxes themselves sit in a 3×3 arrangement. We number them 0 to 8 in reading order: left to right along the top, then the middle, then the bottom.

To find which box a cell (r, c) is in, first find which band of rows and which band of columns it is in.

  • Rows 0, 1, 2 are in row-band 0. Rows 3, 4, 5 are in row-band 1. Rows 6, 7, 8 are in row-band 2.
  • The same goes for columns.

Dividing by 3 and throwing away the remainder gives the band. In Python that is r // 3, read "r floor-divided by 3". For example, 4 // 3 is 1 and 8 // 3 is 2.

Now turn the two bands into one box number:

\text{box} = 3 \times \left\lfloor \frac{r}{3} \right\rfloor + \left\lfloor \frac{c}{3} \right\rfloor

Read it aloud as "three times the floor of r over three, plus the floor of c over three". The symbols \lfloor \ \rfloor mean floor, which means "round down to a whole number". So this says: take the row-band, multiply by 3, and add the column-band.

Why multiply by 3? Because each row-band holds 3 boxes. To get to the boxes in row-band 1, you must skip past the 3 boxes in row-band 0. To reach row-band 2, you skip 6. Then the column-band tells you how far along that row of boxes you are. This is the same arithmetic a computer uses to find a cell in a grid stored as one long list (4.2).

The figure shows the box numbers, with one cell worked out.

012345678cell (r = 4, c = 7)r // 3 = 1 box-rowc // 3 = 2 box-colbox = 3 × 1 + 2 = 5
Integer division picks the box; multiply-and-add flattens the pair into one number.

Check the formula on a few cells, rather than trusting it.

  • (0, 0): 3 \times 0 + 0 = 0. Top-left box. ✓
  • (8, 8): 3 \times 2 + 2 = 8. Bottom-right box. ✓
  • (2, 3): 3 \times 0 + 1 = 1. Top-middle box. ✓
  • (3, 2): 3 \times 1 + 0 = 3. Middle-left box. ✓

The last two are worth checking every time. If you accidentally wrote the formula the wrong way round, as 3 × (c // 3) + r // 3, those two cells would swap boxes, and you would catch it here.

The solution ​

python
from collections import defaultdict

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        rows = defaultdict(set)                                   # (1)
        cols = defaultdict(set)
        boxes = defaultdict(set)

        for r in range(9):                                        # (2)
            for c in range(9):
                v = board[r][c]
                if v == '.':                                      # (3)
                    continue
                b = (r // 3) * 3 + (c // 3)                       # (4)
                if v in rows[r] or v in cols[c] or v in boxes[b]: # (5)
                    return False
                rows[r].add(v)                                    # (6)
                cols[c].add(v)
                boxes[b].add(v)
        return True                                               # (7)
ts
function isValidSudoku(board: string[][]): boolean {
  const rows = Array.from({ length: 9 }, () => new Set<string>());   // (1)
  const cols = Array.from({ length: 9 }, () => new Set<string>());
  const boxes = Array.from({ length: 9 }, () => new Set<string>());

  for (let r = 0; r < 9; r++) {                                      // (2)
    for (let c = 0; c < 9; c++) {
      const v = board[r][c];
      if (v === '.') continue;                                       // (3)
      const b = Math.floor(r / 3) * 3 + Math.floor(c / 3);           // (4)
      if (rows[r].has(v) || cols[c].has(v) || boxes[b].has(v)) {     // (5)
        return false;
      }
      rows[r].add(v);                                                // (6)
      cols[c].add(v);
      boxes[b].add(v);
    }
  }
  return true;                                                       // (7)
}

Line by line ​

(1) One set per group. rows[3] will hold every digit seen so far in row 3. cols and boxes work the same way. A defaultdict(set) creates an empty set the first time a key is used, so we never have to set them up by hand.

In TypeScript we make nine sets for each kind of group with Array.from({ length: 9 }, () => new Set()). Do not write new Array(9).fill(new Set()). That creates one set and puts it in all nine slots. Every row would then share one set, and digits from different rows would wrongly clash.

(2) Visit every cell, row by row, column by column. That is 81 cells.

(3) Skip empty cells. A '.' is not a digit, so it cannot break any rule.

(4) Work out the box number with the formula from above. In TypeScript, / gives a decimal answer, so 4 / 3 is 1.333.... Using that as a list position would quietly give undefined. Math.floor rounds it down to 1, which matches Python's //.

(5) Check all three attendance sheets. If the digit is already in this cell's row, column or box, a rule is broken, and we return false at once.

(6) Sign the digit into all three sheets. This line must come after line (5). If you added first and checked second, the digit would find itself and every board would look invalid. This is the same check-before-insert rule from Contains Duplicate.

(7) No rule was broken. Every filled cell was checked against everything before it, so the board is valid.

Trace ​

Take a small part of a board. Suppose these are the first few filled cells, in reading order: a '5' at (0, 0), a '3' at (0, 1), a '6' at (1, 0), and then a '5' at (1, 1).

CellvBox bRow set beforeCol set beforeBox set beforeResult
(0, 0)50{}{}{}add
(0, 1)30{}add
(1, 0)60{}add
(1, 1)50{5, 3, 6}return false

The last '5' is in a different row and a different column from the first '5'. Only the box catches it. This is exactly the kind of board that proves your box formula is working.

Complexity, derived ​

Time. The board is always 9×9, so the loops always visit exactly 81 cells. Each visit does a fixed amount of work: one formula, three lookups and three inserts. So the total work is the same for every input, no matter what. Work that does not grow with the input is O(1).

Many people say O(n^2) here. That is the mistake the problem is testing. There is no n that can grow. If an interviewer asks about a general board with m rows and m columns, the answer is O(m^2), because there are m^2 cells. But for the board in this problem, say O(1) first.

Space. There are 27 sets, and each can hold at most 9 digits. That is at most 27 \times 9 = 243 stored items, a fixed limit. So the space is O(1) too.

The bitmask version ​

27 set objects is a lot of machinery for 27 small groups. Since there are only nine digits, one group's whole state fits into a single small whole number, using one bit per digit. A bit is a single 0 or 1 inside a number. Bit d set to 1 means "digit d has been seen in this group".

python
rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
# inside the loop, with d = int(v):
bit = 1 << d                                             # a number with only bit d set
if rows[r] & bit or cols[c] & bit or boxes[b] & bit:     # is bit d already on?
    return False
rows[r] |= bit                                           # turn bit d on
cols[c] |= bit
boxes[b] |= bit

Here is what each operator does.

  • 1 << d means "the number 1, shifted left by d places". For d = 3 that is the binary number 1000, which is 8. It has a 1 in position 3 and zeros everywhere else.
  • & compares two numbers bit by bit and keeps a 1 only where both have a 1. So rows[r] & bit is non-zero exactly when bit d is already on in rows[r].
  • |= turns on the bits of bit and leaves all the other bits as they were.

On an 81-cell board this makes no visible difference. It matters a great deal in a Sudoku solver, which runs this check millions of times while it searches. 4.29 teaches bit operations properly.

Edge cases ​

  • An empty board with only '.'s. Nothing is checked, and the answer is true.
  • A valid but unsolvable board. Still true. We only check the rules for the digits already placed.
  • Two equal digits in the same box but in different rows and columns. Only the box set catches it, as the trace showed. This is the input that tests your box formula.

Variations you will meet ​

  • Sudoku Solver. This check becomes the test inside a search that tries digits one by one and backs up when a rule breaks. See 4.18. The bitmask is worth it there.
  • N-Queens. Place queens on a chessboard so no two attack each other. The same "name the group" idea works on diagonals. Two cells are on the same downward diagonal when r - c is equal, and on the same upward diagonal when r + c is equal. So r - c and r + c are the group names, just as the box formula is here. See 4.18.9.
  • A 16×16 board. The boxes become 4×4, so the formula becomes (r // 4) * 4 + (c // 4), and the bitmask needs 16 bits.

The general lesson: when an item belongs to several overlapping groups, give each group a name you can compute, and keep one "seen" set per group.

What the interviewer will push on ​

"What is the time complexity?" O(1), because the board size is fixed. This question is asked to see whether you notice.

"How did you get the box number?" Talk through r // 3 and c // 3 as bands, explain why the row-band is multiplied by 3, and check it on (3, 2).

"Can you use less memory?" The bitmask.

"Does this check that the board can be solved?" No. Solving needs a search that tries digits and backs up, which is a much bigger job.

"Make it work for a 16×16 board." Change both 3s to 4s and use 16 bits. Giving the general rule shows you understood the formula rather than memorised it.

One thing to volunteer: say that all three rules are one check applied to differently named groups. That one idea makes the code short, and it carries straight over to N-Queens.

Next: 4.4.9 Longest Consecutive Sequence. The one problem in this group where proving the speed is harder than writing the code.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet