Valid Sudoku

▶

Steps

setup

Initialize bitmask arrays

Initialize three arrays 'rows', 'cols', and 'boxes' with zeros to track digits seen in each row, column, and 3x3 box.

💡 Starting with zero means no digits have been seen yet; these arrays will store bitmasks representing digits 1-9.

Line:

rows = [0] * 9
cols = [0] * 9
boxes = [0] * 9

💡 Bitmask arrays allow constant-time checks for duplicates by using bitwise operations.

traverse

Start scanning cell (0,0)

Set pointers i=0, j=0 to start scanning the first cell of the board, which contains digit '5'.

💡 The algorithm processes each cell in row-major order, starting at the top-left corner.

Line:

for i in range(9):
    for j in range(9):

💡 Pointer positions indicate the current cell being validated.

fill_cells

Convert digit '5' to bitmask

Convert digit '5' to zero-based index 4 and create bitmask by shifting 1 left by 4 (1 << 4 = 16).

💡 Bitmasking uses bits to represent digits; shifting 1 by digit-1 sets the bit for that digit.

Line:

val = ord(board[i][j]) - ord('1')
mask = 1 << val

💡 This bitmask uniquely identifies the digit '5' for quick presence checks.

fill_cells

Calculate box index for cell (0,0)

Calculate box index as (0 // 3) * 3 + (0 // 3) = 0, identifying the top-left 3x3 box.

💡 Boxes are numbered 0 to 8 left to right, top to bottom; this helps track digits per box.

Line:

box_index = (i // 3) * 3 + (j // 3)

💡 Knowing the box index allows checking duplicates within the same 3x3 subgrid.

compare

Check for duplicates of '5' in row, column, box

Check if bitmask 16 is already set in rows[0], cols[0], or boxes[0]. None are set, so no duplicate.

💡 If the bit is set, it means the digit appeared before in the same row, column, or box.

Line:

if (rows[i] & mask) or (cols[j] & mask) or (boxes[box_index] & mask):
    return False

💡 Bitwise AND quickly detects duplicates by checking if the digit's bit is already set.

insert

Set bitmask for digit '5' in row, column, box

Update rows[0], cols[0], and boxes[0] by OR-ing with mask 16 to mark digit '5' as seen.

💡 Setting the bit records that digit '5' has appeared in these row, column, and box.

Line:

rows[i] |= mask
cols[j] |= mask
boxes[box_index] |= mask

💡 Bitwise OR updates the bitmask to include the new digit without affecting other bits.

traverse

Move to next cell (0,1) with digit '3'

Increment pointer j to 1, processing cell (0,1) which contains digit '3'.

💡 The algorithm continues scanning cells left to right in the first row.

Line:

for j in range(9):

💡 Pointer movement shows the scanning order of the board.

fill_cells

Convert digit '3' to bitmask and calculate box index

Digit '3' converts to val=2, mask=1<<2=4; box index remains 0 for cell (0,1).

💡 Same process as before to prepare for duplicate checks.

Line:

val = ord(board[i][j]) - ord('1')
mask = 1 << val
box_index = (i // 3) * 3 + (j // 3)

💡 Bitmask and box index are recalculated for each digit cell.

compare

Check for duplicates of '3' in row, column, box

Check if bitmask 4 is set in rows[0], cols[1], or boxes[0]. None are set, so no duplicate.

💡 No duplicates means digit '3' is valid here.

Line:

if (rows[i] & mask) or (cols[j] & mask) or (boxes[box_index] & mask):
    return False

💡 Bitwise AND confirms digit '3' is unique in its row, column, and box.

insert

Set bitmask for digit '3' in row, column, box

Update rows[0], cols[1], and boxes[0] by OR-ing with mask 4 to mark digit '3' as seen.

💡 Marking digit '3' ensures future duplicates will be detected.

Line:

rows[i] |= mask
cols[j] |= mask
boxes[box_index] |= mask

💡 Bitmask updates track all digits seen so far.

traverse

Skip empty cell (0,2)

Move pointer j to 2; cell contains '.', so skip processing and continue.

💡 Empty cells do not affect bitmasks and are ignored.

Line:

if board[i][j] == '.':
    continue

💡 Skipping empty cells saves unnecessary checks.

traverse

Process digit '7' at cell (0,4)

Move pointer j to 4; cell contains digit '7'. Convert to bitmask and calculate box index 1.

💡 Continue scanning and validating digits in the first row.

Line:

val = ord(board[i][j]) - ord('1')
mask = 1 << val
box_index = (i // 3) * 3 + (j // 3)

💡 Each digit is processed with the same steps for consistency.

compare

Check for duplicates of '7' in row, column, box

Check if bitmask 64 (1<<6) is set in rows[0], cols[4], or boxes[1]. None set, so no duplicate.

💡 No duplicates means digit '7' is valid here.

Line:

if (rows[i] & mask) or (cols[j] & mask) or (boxes[box_index] & mask):
    return False

💡 Bitwise AND confirms digit '7' is unique in its row, column, and box.

insert

Set bitmask for digit '7' in row, column, box

Update rows[0], cols[4], and boxes[1] by OR-ing with mask 64 to mark digit '7' as seen.

💡 Marking digit '7' ensures future duplicates will be detected.

Line:

rows[i] |= mask
cols[j] |= mask
boxes[box_index] |= mask

💡 Bitmask updates track all digits seen so far.

traverse

Continue scanning remaining cells

The algorithm continues scanning each cell in the board, skipping empty cells and validating digits similarly.

💡 Each cell is processed with the same steps: convert, check duplicates, and update bitmasks.

Line:

for i in range(9):
    for j in range(9):
        if board[i][j] == '.':
            continue
        val = ord(board[i][j]) - ord('1')
        mask = 1 << val
        box_index = (i // 3) * 3 + (j // 3)
        if (rows[i] & mask) or (cols[j] & mask) or (boxes[box_index] & mask):
            return False
        rows[i] |= mask
        cols[j] |= mask
        boxes[box_index] |= mask

💡 The pattern repeats for all cells, ensuring the entire board is validated.

prune

Finish scanning all cells without duplicates

All cells have been scanned and no duplicates found in any row, column, or box.

💡 No duplicate bits were detected, so the board is valid.

Line:

return True

💡 The algorithm confirms validity by absence of duplicate bits.

def isValidSudoku(board):
    rows = [0] * 9  # STEP 1
    cols = [0] * 9  # STEP 1
    boxes = [0] * 9  # STEP 1
    for i in range(9):  # STEP 2
        for j in range(9):  # STEP 2
            if board[i][j] == '.':  # STEP 11
                continue
            val = ord(board[i][j]) - ord('1')  # STEP 3,8,12
            mask = 1 << val  # STEP 3,8,12
            box_index = (i // 3) * 3 + (j // 3)  # STEP 4,8,12
            if (rows[i] & mask) or (cols[j] & mask) or (boxes[box_index] & mask):  # STEP 5,9,13
                return False
            rows[i] |= mask  # STEP 6,10,14
            cols[j] |= mask  # STEP 6,10,14
            boxes[box_index] |= mask  # STEP 6,10,14
    return True  # STEP 16

📊

Valid Sudoku - Watch the Algorithm Execute, Step by Step

Watching this step-by-step visualization reveals how bitmasking efficiently tracks duplicates without extra space for sets or arrays, making the logic crystal clear.

setup

0

1

2

Result: true

traverse

j

5

0

3

1

.

2

.

3

7

4

.

5

.

6

.

7

.

8

Result: true

fill_cells

j

5

0

3

1

.

2

.

3

7

4

.

5

.

6

.

7

.

8

Result: true

fill_cells

box

5

0

3

1

.

2

.

3

7

4

.

5

.

6

.

7

.

8

Result: true

compare

box

0

1

2

Result: true

insert

box

0

1

2

Result: true

traverse

i

5

0

j

3

1

.

2

.

3

7

4

.

5

.

6

.

7

.

8

Result: true

fill_cells

box

5

0

j

3

1

.

2

.

3

7

4

.

5

.

6

.

7

.

8

Result: true

compare

box

0

j

1

2

Result: true

insert

box

0

j

1

2

Result: true

traverse

i

5

0

3

1

j

.

2

.

3

7

4

.

5

.

6

.

7

.

8

Result: true

fill_cells

i

5

0

box

3

1

.

2

.

3

j

7

4

.

5

.

6

.

7

.

8

Result: true

compare

i

0

box

1

2

Result: true

insert

i

0

box

1

2

Result: true

traverse

Result: true

prune

Result: true

Key Takeaways

✓ Bitmasking enables constant-time duplicate checks for rows, columns, and boxes.

This insight is hard to see from code alone because bitwise operations are less intuitive than sets or arrays.

✓ The algorithm processes the board cell by cell, skipping empty cells efficiently.

Visualizing pointer movement clarifies the scanning order and skipping logic.

✓ Calculating the box index maps each cell to its 3x3 subgrid for localized duplicate checks.

Seeing box index calculation in action helps understand Sudoku's box constraints.

Practice

1. You need to fill an n x n matrix with numbers from 1 to n² in a pattern that starts at the top-left corner and proceeds in a clockwise spiral moving outward. Which approach guarantees filling all cells correctly without revisiting or skipping any cell?

easy

A. Greedy approach filling rows and columns independently without tracking boundaries

B. Dynamic programming to store partial sums and fill matrix based on subproblems

C. Directional simulation with boundary shrinking and cycling through directions

D. Sorting all numbers and placing them diagonally from top-left to bottom-right

Solution

1. Step 1: Understand the problem constraints

   The matrix must be filled in a spiral order, visiting each cell exactly once in a clockwise manner.

2. Step 2: Identify the approach that tracks boundaries and direction

   Directional simulation with boundary shrinking ensures that after filling one side, boundaries are updated to avoid revisiting cells, and directions cycle through right, down, left, and up correctly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Boundary shrinking prevents overwriting and ensures full coverage [OK]

Hint: Track boundaries and directions to avoid revisits [OK]

Common Mistakes:

• Assuming greedy row/column fills without boundary checks works
• Confusing DP with spiral traversal
• Ignoring direction cycling leads to incomplete fills

2. You are given a square matrix and asked to transform it so that rows become columns and columns become rows without using extra space. Which approach guarantees an optimal in-place solution?

easy

A. Use a brute force approach by creating a new matrix and copying elements accordingly.

B. Swap elements symmetrically across the diagonal only once, iterating over the upper triangle of the matrix.

C. Apply a greedy approach by swapping elements row-wise without considering the diagonal symmetry.

D. Use dynamic programming to store intermediate transposed states and build the final matrix.

Solution

1. Step 1: Understand the problem constraints

   The problem requires an in-place transpose of a square matrix, meaning no extra matrix can be used.

2. Step 2: Identify the correct approach

   Swapping elements symmetrically across the diagonal once (upper triangle only) ensures each pair is swapped exactly once, achieving in-place transpose efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Swapping only upper triangle elements avoids double swaps and extra space [OK]

Hint: Swap only upper triangle elements once [OK]

Common Mistakes:

• Using extra space unnecessarily
• Swapping elements twice by iterating entire matrix
• Ignoring diagonal symmetry leading to incorrect results

3. What is the space complexity of the optimal in-place layer-by-layer rotation algorithm for an n x n matrix, and why might some candidates mistakenly think it is higher?

medium

A. O(n^2) because the entire matrix is modified in place.

B. O(log n) because the algorithm processes layers recursively.

C. O(n) due to the recursion stack or auxiliary arrays used during rotation.

D. O(1) because only a fixed number of variables are used regardless of matrix size.

Solution

1. Step 1: Identify space usage

   The algorithm uses only a few variables (indices, temp storage) regardless of matrix size.

2. Step 2: Understand common misconceptions

   Some think space is O(n) or more due to confusion with extra matrix or recursion, but no extra arrays or recursion are used.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only constant extra variables used, so space is O(1) [OK]

Hint: In-place means constant extra space regardless of input size [OK]

Common Mistakes:

• Confusing time complexity with space
• Assuming recursion or extra arrays are used

4. Suppose the problem changes: you want to find the top 3 maximum hourglass sums in the matrix instead of just the maximum. Which modification to the sliding window approach is correct and efficient?

hard

A. Store all hourglass sums in a list and sort it at the end to pick top 3.

B. Run the sliding window 3 times, each time removing the previously found max hourglass from the matrix.

C. Maintain a min-heap of size 3 to track top sums while sliding through the matrix.

D. Use dynamic programming to store maximum sums for all submatrices and pick top 3.

Solution

1. Step 1: Understand the need to track multiple top sums efficiently

   Storing all sums and sorting is inefficient for large matrices.

2. Step 2: Use a min-heap of fixed size 3

   Insert sums as you compute; if heap size exceeds 3, pop smallest. This keeps top 3 sums efficiently.

3. Step 3: Reject other options

   Sorting all sums (A) is costly; repeated removal (C) is complex and incorrect; DP (D) is unnecessary and inefficient.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Min-heap maintains top K sums in O(n*m*logK) time [OK]

Hint: Use min-heap to track top K sums efficiently [OK]

Common Mistakes:

• Sorting all sums after computation
• Repeatedly removing max sums from matrix
• Using DP unnecessarily

5. Suppose you need to transpose a non-square matrix (m x n) in-place, but the matrix is stored as a flat array in row-major order. Which approach correctly handles this scenario?

hard

A. Transpose in-place by swapping elements only in the upper triangle of the matrix.

B. Use the same in-place swapping approach as for square matrices, swapping elements symmetrically across the diagonal.

C. Create a new matrix of size n x m and copy elements accordingly, since in-place transpose is not possible for non-square matrices.

D. Use a recursive approach to swap elements in cycles to achieve in-place transpose.

Solution

1. Step 1: Understand matrix shape constraints

   In-place transpose by swapping only works for square matrices because indices map symmetrically.

2. Step 2: For non-square matrices, in-place transpose is not possible

   Because the shape changes from m x n to n x m, a new matrix must be created to hold the transposed data.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Non-square matrix transpose requires extra space due to dimension change [OK]

Hint: In-place transpose only works for square matrices [OK]

Common Mistakes:

• Trying to swap elements in-place for non-square matrices
• Assuming upper triangle swaps apply to rectangular matrices
• Ignoring dimension changes after transpose