Introduction

Sudoku is a universally beloved puzzle, but validating a Sudoku board

algorithmically is a classic technical interview question. In this post, we are

going to dive deep into LeetCode 36: Valid Sudoku.

We won't just look at the code; we will explore the intuition behind the problem

so you don't have to memorize anything. We’ll cover an ingenious in-place

validation approach, break down the complex math formula used to check

3 \times 3 sub-boxes, and look at an alternative optimal solution using

HashSets.

Let's dive in!

Understanding the Problem

The problem asks us to determine if a partially filled 9 \times 9 Sudoku board

is valid. To be valid, the filled cells must follow three straightforward rules:

1. Each row must contain the digits 1-9 without repetition.

2. Each column must contain the digits 1-9 without repetition.

3. Each of the nine 3 \times 3 sub-boxes must contain the digits 1-9 without

repetition.

Important Note: A valid board doesn't mean the board is fully solvable! We only

care about checking the numbers that are currently on the board.

Intuition: How to Think About the Problem

Before writing code, how do we, as humans, check if a Sudoku board is valid? If

you place a 5 in a cell, you quickly scan horizontally (its row), vertically

(its column), and within its small 3 \times 3 square. If you see another 5, the

board is invalid.

To translate this to code, we have two choices:

1. The Simulation Approach: Go cell by cell. Pick up the number, hide it, and

check its row, column, and 3 \times 3 box to see if that number exists

anywhere else. (This is the approach we will look at first).

2. The Memory Approach: Go cell by cell, but keep a "notebook" (like a Hash

Table) of everything we have seen so far. If we see a number we've already

written down for a specific row, column, or box, it's invalid.

Approach 1: The In-Place Validation (Space-Optimized)

Here is a brilliant solution that validates the board without using any extra

data structures.

The Logic: Iterate through every cell on the board. When we find a number, we

temporarily replace it with a . (empty space). Then, we iterate 9 times to check

its entire row, column, and sub-box. If the number is found, we return false.

Otherwise, we put the number back and move to the next cell.

The Java Code

The Math Breakdown: Demystifying the 3 \times 3 Grid Formula

The hardest part of this code to understand is this exact line: board[3*(i/3) +

m/3][3*(j/3) + m%3]

How does a single loop variable m (from 0 to 8) traverse a 3 \times 3 grid?

Let’s do a dry run.

Step 1: Finding the Starting Point of the Box

The grid is 9 \times 9, broken into nine 3 \times 3 boxes. If we are at a random

cell, say row i = 4, col j = 5, which box are we in? Because integer division in

Java drops the decimal:

1. i / 3 = 4 / 3 = 1
2. j / 3 = 5 / 3 = 1

Now multiply by 3 to get the actual starting coordinates (top-left corner) of

that specific sub-box:

1. 3 * 1 = 3 (Row offset)
2. 3 * 1 = 3 (Col offset) So, the 3 \times 3 box starts at row 3, col 3.

Step 2: Traversing the Box (Dry Run)

Now, as m goes from 0 to 8, we use m / 3 for rows and m % 3 for columns:

1. m = 0: row offset 0/3 = 0, col offset 0%3 = 0 \rightarrow Checks (3+0, 3+0) = (3, 3)
2. m = 1: row offset 1/3 = 0, col offset 1%3 = 1 \rightarrow Checks (3+0, 3+1) = (3, 4)
3. m = 2: row offset 2/3 = 0, col offset 2%3 = 2 \rightarrow Checks (3+0, 3+2) = (3, 5)
4. m = 3: row offset 3/3 = 1, col offset 3%3 = 0 \rightarrow Checks (3+1, 3+0) = (4, 3)
5. m = 4: row offset 4/3 = 1, col offset 4%3 = 1 \rightarrow Checks (3+1, 3+1) = (4, 4)
6. ...and so on up to m = 8.

This brilliant math formula maps a 1D loop (0 to 8) directly onto a 2D

3 \times 3 grid perfectly! No nested loops needed inside the isvalid function.

Approach 2: The HashSet Solution (Single Pass)

While the first approach is highly space-efficient, it does a bit of redundant

checking. An alternative approach that interviewers love is using a HashSet.

Instead of checking rows and columns every time we see a number, we generate a

unique "string signature" for every number and attempt to add it to a HashSet.

If we see a 5 at row 0 and col 1, we create three strings:

1. "5 in row 0"

2. "5 in col 1"

3. "5 in block 0-0"

The HashSet.add() method returns false if the item already exists in the set. If

it returns false, we instantly know the board is invalid!

HashSet Java Code:

Notice how we use i/3 + "-" + j/3 to identify the blocks. Top-left is block 0-0,

bottom-right is block 2-2.

Time and Space Complexity Breakdown

Interviewers will always ask for your complexity analysis. Because a Sudoku

board is strictly fixed at 9 \times 9, the strict Big-O is actually constant.

However, let's look at it conceptually as if the board were N \times N.

Approach 1: In-Place Validation (Your Solution)

1. Time Complexity: O(1) (Strictly speaking). We traverse 81 cells, and for

each cell, we do at most 9 iterations. 81 \times 9 = 729 operations. Since

729 is a constant, it's O(1). (If the board was N \times N, time complexity

would be O(N^3) because for N^2 cells, we iterate N times).

1. Space Complexity: O(1). We only use primitive variables (i, j, k, m, temp).

No extra memory is allocated.

Approach 2: HashSet Approach

1. Time Complexity: O(1). We traverse the 81 cells exactly once. Generating

strings and adding to a HashSet takes O(1) time. (If the board was

N \times N, time complexity would be O(N^2)).

1. Space Complexity: O(1). The HashSet will store a maximum of

81 \times 3 = 243 strings. Since this upper limit is fixed, space is

constant.

Conclusion

The Valid Sudoku problem is a fantastic exercise in matrix traversal and

coordinate math.

When solving this in an interview:

1. Use the first approach if you want to impress the interviewer with O(1)

space complexity and your deep understanding of math formulas (the /3 and %3

trick).

2. Use the second approach (HashSet) if you want to show off your knowledge of

data structures and write highly readable, clean, and clever code.

I hope this breakdown gives you the intuition needed so you never have to

memorize the code for LeetCode 36!

Happy Coding! Keep Learning🤟