Valid Sudoku

📋

Valid Sudoku

Edge cases:

</>

IDE

def isValidSudoku(board: list[list[str]]) -> bool:public boolean isValidSudoku(char[][] board)bool isValidSudoku(vector<vector<char>>& board)function isValidSudoku(board)

def isValidSudoku(board):
    # Write your solution here
    pass

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // Write your solution here
        return true;
    }
}

#include <vector>
using namespace std;

bool isValidSudoku(vector<vector<char>>& board) {
    // Write your solution here
    return true;
}

function isValidSudoku(board) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: trueMissed duplicate in column check, only checked rows and boxes.✅ Add column-wise duplicate detection using sets for each column.

Wrong: trueMissed duplicate in 3x3 box due to incorrect box indexing or skipping box checks.✅ Implement correct 3x3 box iteration using (row//3)*3 and (col//3)*3 indices.

Wrong: falseIncorrectly treating '.' as a digit causing false duplicates.✅ Skip '.' cells when checking duplicates in rows, columns, and boxes.

Wrong: falseOff-by-one errors in box iteration causing false positives.✅ Ensure loops cover exactly 3 rows and 3 columns per box without overlap.

Wrong: TLEInefficient repeated scanning or nested loops beyond fixed 9x9 iterations.✅ Use single pass with sets or bitmasks to check duplicates in O(1) time per cell.

✓

Test Cases

Try testing your code on empty and minimal boards to catch base case bugs.

Consider tricky cases where duplicates appear only in columns or boxes.

Think about how to reduce repeated work and achieve constant time checks.

t1_01basic

Input[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

Expectedtrue

⏱ Performance - must finish in 2000ms

No duplicates in any row, column, or 3x3 box.

💡 Check each row, column, and 3x3 box for duplicates.

💡 Use sets to track seen digits per row, column, and box.

💡 Return false immediately if a duplicate digit is found in any unit.

Why it failed: Failed basic test: likely missed checking one of row, column, or box constraints. Fix by ensuring all three checks are implemented.

✓ Correctly validates standard Sudoku board with no duplicates.

t1_02basic

Input[["8","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

Expectedfalse

⏱ Performance - must finish in 2000ms

Duplicate '8' in first column (rows 0 and 3).

💡 Check columns carefully for duplicates, not just rows.

💡 Track digits seen per column using sets.

💡 Return false if a digit repeats in any column.

Why it failed: Missed duplicate in column check. Fix by adding column-wise duplicate detection using sets.

✓ Correctly detects duplicate in column and returns false.

t2_01edge

Input[[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]]

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty board with all '.' is valid as no duplicates exist.

💡 Consider that empty cells '.' do not count as digits.

💡 Ensure your code skips '.' when checking duplicates.

💡 Return true if no digits found repeated anywhere.

Why it failed: Incorrectly treats '.' as a digit causing false duplicates. Fix by skipping '.' in all checks.

✓ Correctly handles empty board as valid.

t2_02edge

Input[["5",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]]

Expectedtrue

⏱ Performance - must finish in 2000ms

Single digit on board is valid as no duplicates exist.

💡 Check that single digits do not cause false duplicates.

💡 Ensure sets are cleared per row, column, and box.

💡 Return true if no duplicates found with minimal input.

Why it failed: Fails single element test by mishandling sets or indices. Fix by proper initialization and checks.

✓ Correctly validates board with single digit.

t2_03edge

Input[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

Expectedtrue

⏱ Performance - must finish in 2000ms

Fully filled valid Sudoku board with no duplicates.

💡 Test exact boundary with fully filled board.

💡 Check all rows, columns, and boxes for duplicates.

💡 Return true only if all constraints hold for full board.

Why it failed: Fails exact boundary test by missing some checks or off-by-one errors. Fix index calculations for boxes.

✓ Correctly validates fully filled valid Sudoku board.

t2_04edge

Input[["5","5",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

Expectedfalse

⏱ Performance - must finish in 2000ms

Duplicate '5' in first row.

💡 Check rows carefully for duplicates.

💡 Use sets to track digits per row.

💡 Return false if duplicate digit found in any row.

Why it failed: Missed duplicate in row check. Fix by adding row-wise duplicate detection using sets.

✓ Correctly detects duplicate in row and returns false.

t3_01corner

Input[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],["5",".",".",".","8",".",".","7","9"]]

Expectedfalse

⏱ Performance - must finish in 2000ms

Duplicate '5' in first column (rows 0 and 8) - greedy trap if only checking rows and boxes.

💡 Don't rely on checking only rows and boxes; columns matter too.

💡 Ensure column duplicates are detected to avoid greedy trap.

💡 Add column-wise duplicate checks to fix this bug.

Why it failed: Missed duplicate in column due to greedy approach checking only rows and boxes. Fix by adding column duplicate checks.

✓ Correctly detects duplicate in column, avoiding greedy trap.

t3_02corner

Input[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","5"]]

Expectedfalse

⏱ Performance - must finish in 2000ms

Duplicate '5' in bottom-right 3x3 box (positions (7,8) and (8,8)) - 0/1 vs unbounded confusion.

💡 Remember Sudoku boxes are 3x3 sub-grids, not entire rows or columns.

💡 Check duplicates within each 3x3 box separately.

💡 Fix by correctly indexing and checking each 3x3 box for duplicates.

Why it failed: Missed duplicate in 3x3 box due to incorrect box indexing or skipping box checks. Fix box iteration logic.

✓ Correctly detects duplicate in 3x3 box.

t3_03corner

Input[["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]

Expectedtrue

⏱ Performance - must finish in 2000ms

Valid board but test for off-by-one errors in box indexing.

💡 Check that box indices are calculated as (row//3)*3 and (col//3)*3.

💡 Avoid off-by-one errors when iterating over 3x3 boxes.

💡 Fix loops to cover exactly 3 rows and 3 columns per box.

Why it failed: Fails due to off-by-one error in box iteration causing missed duplicates or false positives. Fix box loop ranges.

✓ Correctly handles box indexing without off-by-one errors.

t4_01performance

Input[["1","2","3","4","5","6","7","8","9"],["4","5","6","7","8","9","1","2","3"],["7","8","9","1","2","3","4","5","6"],["2","3","4","5","6","7","8","9","1"],["5","6","7","8","9","1","2","3","4"],["8","9","1","2","3","4","5","6","7"],["3","4","5","6","7","8","9","1","2"],["6","7","8","9","1","2","3","4","5"],["9","1","2","3","4","5","6","7","8"]]

Expectedtrue

⏱ Performance - must finish in 2000ms

Full 9x9 board at constraint boundary; algorithm must run in O(1) time effectively within 2 seconds.

💡 Sudoku board size is fixed; complexity is constant time.

💡 Use sets or bitmasks for O(1) checks per cell.

💡 Avoid nested loops beyond fixed 9x9 iterations.

Why it failed: TLE due to inefficient nested loops or repeated scanning. Fix by using single pass with sets or bitmasks.

✓ Algorithm runs in constant time as expected for fixed 9x9 board.

Practice

1. 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

2. The following code attempts to rotate an n x n matrix by 90 degrees clockwise in-place. Identify the line containing the subtle bug that causes incorrect rotation.

medium

A. matrix[last][last - offset] = matrix[i][last]

B. matrix[last - offset][first] = matrix[last][last - offset]

C. matrix[i][last] = matrix[i][last]

D. matrix[first][i] = matrix[last - offset][first]

Solution

1. Step 1: Analyze the last assignment

   The last line should assign the saved top value to matrix[i][last], but it assigns matrix[i][last] to itself.

2. Step 2: Identify the fix

   Replace matrix[i][last] = matrix[i][last] with matrix[i][last] = top to complete the four-way swap correctly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Incorrect assignment leaves matrix partially unrotated [OK]

Hint: Last assignment must restore saved top element to complete rotation [OK]

Common Mistakes:

• Forgetting to assign saved top value
• Swapping elements twice causing corruption

3. What is the time complexity of the optimal in-place boundary shrinking approach to generate an n x n spiral matrix, and why?

medium

A. O(n²) because every cell in the matrix is visited exactly once

B. O(n) because each boundary shrinks linearly

C. O(n³) due to nested loops and repeated boundary checks

D. O(n log n) because of direction cycling and boundary updates

Solution

1. Step 1: Identify the number of cells to fill

   The matrix has n² cells, each must be assigned a value exactly once.

2. Step 2: Analyze loops and operations

   Each iteration fills one side of the current boundary, and boundaries shrink inward. The total number of assignments sums to n², so time complexity is O(n²).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Every cell visited once -> O(n²) time [OK]

Hint: Each cell visited once -> O(n²) time [OK]

Common Mistakes:

• Confusing boundary shrinking with linear time
• Assuming nested loops multiply to cubic time
• Ignoring that direction cycling is constant time

4. What is the time complexity of the in-place transpose algorithm for an n x n matrix that swaps elements only above the main diagonal?

medium

A. O(n)

B. O(n^3)

C. O(n^2 / 2)

D. O(n^2)

Solution

1. Step 1: Identify loops and iterations

   The outer loop runs n times, inner loop runs approximately n - i - 1 times, summing to about n(n-1)/2 swaps.

2. Step 2: Simplify complexity

   Ignoring constants and lower order terms, time complexity is O(n^2).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Quadratic time due to nested loops over matrix elements [OK]

Hint: Nested loops over n x n matrix -> O(n^2) [OK]

Common Mistakes:

• Confusing O(n^2 / 2) as different from O(n^2)
• Mistaking it for O(n^3) due to nested loops
• Assuming linear time due to skipping diagonal

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