Valid Sudoku

🎯

Valid Sudoku

mediumMATRIXAmazonFacebookGoogle

Imagine you're building a Sudoku app that needs to instantly verify if a partially filled board is valid before allowing the user to proceed.

💡 This problem tests your ability to validate constraints across multiple dimensions (rows, columns, and boxes) simultaneously. Beginners often struggle because they try to check the entire board repeatedly or miss one of the three constraints, leading to incorrect validation.

📋

Problem Statement

Given a 9x9 Sudoku board (partially filled), determine if it is valid. The board is valid if each row, each column, and each of the nine 3x3 sub-boxes contain the digits 1-9 without repetition. Empty cells are denoted by '.' and can be ignored.

board.length == 9board[i].length == 9board[i][j] is a digit '1'-'9' or '.'

💡

Example

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\"]]"

Outputtrue

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

• All cells empty → valid
• Duplicate in a row → invalid
• Duplicate in a column → invalid
• Duplicate in a 3x3 box → invalid

⚠️

Common Mistakes

Not checking 3x3 boxes

Board incorrectly marked valid despite box duplicates

✅ Add explicit checks for 3x3 boxes

Including '.' as a digit in sets

False duplicate detection or runtime errors

✅ Skip '.' cells when checking or adding to sets

Incorrect box index calculation

Duplicates in boxes go undetected or false positives occur

✅ Use box_index = (row // 3) * 3 + (col // 3)

Using nested loops inefficiently without sets

Code becomes complex and inefficient, prone to bugs

✅ Use sets or bitmasks to track seen digits cleanly

🧠

Brute Force (Check Each Constraint Separately with Nested Loops)

💡 This approach exists to build intuition by explicitly checking each rule independently, even if it means scanning the board multiple times. It helps beginners understand the problem constraints clearly.

Intuition

Check every row for duplicates, then every column, then every 3x3 box separately by scanning all cells multiple times.

Algorithm

1. For each row, check if any digit repeats ignoring '.'
2. For each column, check if any digit repeats ignoring '.'
3. For each 3x3 box, check if any digit repeats ignoring '.'
4. If all checks pass, return true; otherwise, false

💡 The challenge is to systematically check all three constraints without mixing them up and to handle empty cells correctly.

</>

Code

def isValidSudoku(board):
    # Check rows
    for i in range(9):
        seen = set()
        for j in range(9):
            if board[i][j] != '.':
                if board[i][j] in seen:
                    return False
                seen.add(board[i][j])
    # Check columns
    for j in range(9):
        seen = set()
        for i in range(9):
            if board[i][j] != '.':
                if board[i][j] in seen:
                    return False
                seen.add(board[i][j])
    # Check 3x3 boxes
    for box_row in range(3):
        for box_col in range(3):
            seen = set()
            for i in range(box_row * 3, box_row * 3 + 3):
                for j in range(box_col * 3, box_col * 3 + 3):
                    if board[i][j] != '.':
                        if board[i][j] in seen:
                            return False
                        seen.add(board[i][j])
    return True

# Driver code
if __name__ == '__main__':
    board = [
        ["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"]
    ]
    print(isValidSudoku(board))

Line Notes

for i in range(9):Iterate over each row to check duplicates

seen = set()Track digits seen in current row to detect duplicates

if board[i][j] != '.':Ignore empty cells as they don't affect validity

if board[i][j] in seen:If digit already seen, board is invalid

import java.util.*;
public class ValidSudoku {
    public static boolean isValidSudoku(char[][] board) {
        // Check rows
        for (int i = 0; i < 9; i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    if (seen.contains(board[i][j])) return false;
                    seen.add(board[i][j]);
                }
            }
        }
        // Check columns
        for (int j = 0; j < 9; j++) {
            Set<Character> seen = new HashSet<>();
            for (int i = 0; i < 9; i++) {
                if (board[i][j] != '.') {
                    if (seen.contains(board[i][j])) return false;
                    seen.add(board[i][j]);
                }
            }
        }
        // Check 3x3 boxes
        for (int boxRow = 0; boxRow < 3; boxRow++) {
            for (int boxCol = 0; boxCol < 3; boxCol++) {
                Set<Character> seen = new HashSet<>();
                for (int i = boxRow * 3; i < boxRow * 3 + 3; i++) {
                    for (int j = boxCol * 3; j < boxCol * 3 + 3; j++) {
                        if (board[i][j] != '.') {
                            if (seen.contains(board[i][j])) return false;
                            seen.add(board[i][j]);
                        }
                    }
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] board = {
            {'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'}
        };
        System.out.println(isValidSudoku(board));
    }
}

Line Notes

for (int i = 0; i < 9; i++) {Loop over each row to check duplicates

Set<Character> seen = new HashSet<>();Use a set to track digits seen in current row

if (board[i][j] != '.') {Skip empty cells as they don't affect validity

if (seen.contains(board[i][j])) return false;Duplicate found means invalid board

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

bool isValidSudoku(vector<vector<char>>& board) {
    // Check rows
    for (int i = 0; i < 9; i++) {
        unordered_set<char> seen;
        for (int j = 0; j < 9; j++) {
            if (board[i][j] != '.') {
                if (seen.count(board[i][j])) return false;
                seen.insert(board[i][j]);
            }
        }
    }
    // Check columns
    for (int j = 0; j < 9; j++) {
        unordered_set<char> seen;
        for (int i = 0; i < 9; i++) {
            if (board[i][j] != '.') {
                if (seen.count(board[i][j])) return false;
                seen.insert(board[i][j]);
            }
        }
    }
    // Check 3x3 boxes
    for (int boxRow = 0; boxRow < 3; boxRow++) {
        for (int boxCol = 0; boxCol < 3; boxCol++) {
            unordered_set<char> seen;
            for (int i = boxRow * 3; i < boxRow * 3 + 3; i++) {
                for (int j = boxCol * 3; j < boxCol * 3 + 3; j++) {
                    if (board[i][j] != '.') {
                        if (seen.count(board[i][j])) return false;
                        seen.insert(board[i][j]);
                    }
                }
            }
        }
    }
    return true;
}

int main() {
    vector<vector<char>> board = {
        {'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'}
    };
    cout << (isValidSudoku(board) ? "true" : "false") << endl;
    return 0;
}

Line Notes

for (int i = 0; i < 9; i++) {Iterate over rows to check duplicates

unordered_set<char> seen;Track digits seen in current row using hash set

if (board[i][j] != '.') {Ignore empty cells for validity checks

if (seen.count(board[i][j])) return false;Return false immediately on duplicate

function isValidSudoku(board) {
    // Check rows
    for (let i = 0; i < 9; i++) {
        let seen = new Set();
        for (let j = 0; j < 9; j++) {
            if (board[i][j] !== '.') {
                if (seen.has(board[i][j])) return false;
                seen.add(board[i][j]);
            }
        }
    }
    // Check columns
    for (let j = 0; j < 9; j++) {
        let seen = new Set();
        for (let i = 0; i < 9; i++) {
            if (board[i][j] !== '.') {
                if (seen.has(board[i][j])) return false;
                seen.add(board[i][j]);
            }
        }
    }
    // Check 3x3 boxes
    for (let boxRow = 0; boxRow < 3; boxRow++) {
        for (let boxCol = 0; boxCol < 3; boxCol++) {
            let seen = new Set();
            for (let i = boxRow * 3; i < boxRow * 3 + 3; i++) {
                for (let j = boxCol * 3; j < boxCol * 3 + 3; j++) {
                    if (board[i][j] !== '.') {
                        if (seen.has(board[i][j])) return false;
                        seen.add(board[i][j]);
                    }
                }
            }
        }
    }
    return true;
}

// Test
const board = [
    ['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']
];
console.log(isValidSudoku(board));

Line Notes

for (let i = 0; i < 9; i++) {Loop over each row to check duplicates

let seen = new Set();Create a set to track digits seen in current row

if (board[i][j] !== '.') {Skip empty cells as they don't affect validity

if (seen.has(board[i][j])) return false;Return false immediately if duplicate found

⏱

Complexity

TimeO(9*9*3) = O(1)

SpaceO(9) for sets

We scan each cell up to three times (row, column, box). Since board size is fixed 9x9, time is constant but conceptually O(n^2). Space is O(n) for sets per check.

💡 Though it looks like triple nested loops, the fixed board size means this runs instantly in practice.

Interview Verdict: Accepted

This approach is simple and correct but not the most efficient in terms of repeated scans. Good for initial correctness.

🧠

Single Pass with Hash Sets for Rows, Columns, and Boxes

💡 This approach improves efficiency by checking all constraints simultaneously in one pass, reducing redundant scans and improving clarity.

Intuition

Use three arrays of sets to track digits seen in each row, column, and box while iterating once over the board.

Algorithm

1. Initialize 9 sets for rows, 9 for columns, and 9 for boxes
2. Iterate over each cell once
3. For each digit, check if it already exists in corresponding row, column, or box set
4. If duplicate found, return false; else add digit to all three sets
5. Return true if no duplicates found

💡 The key is mapping each cell to its box index and updating all three sets simultaneously.

</>

Code

def isValidSudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for i in range(9):
        for j in range(9):
            val = board[i][j]
            if val == '.':
                continue
            box_index = (i // 3) * 3 + (j // 3)
            if val in rows[i] or val in cols[j] or val in boxes[box_index]:
                return False
            rows[i].add(val)
            cols[j].add(val)
            boxes[box_index].add(val)
    return True

# Driver code
if __name__ == '__main__':
    board = [
        ["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"]
    ]
    print(isValidSudoku(board))

Line Notes

rows = [set() for _ in range(9)]Initialize sets to track digits in each row

box_index = (i // 3) * 3 + (j // 3)Calculate box index for current cell

if val in rows[i] or val in cols[j] or val in boxes[box_index]:Check if digit already seen in row, column, or box

rows[i].add(val)Add digit to row set after validation

import java.util.*;
public class ValidSudoku {
    public static boolean isValidSudoku(char[][] board) {
        Set<Character>[] rows = new HashSet[9];
        Set<Character>[] cols = new HashSet[9];
        Set<Character>[] boxes = new HashSet[9];
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            boxes[i] = new HashSet<>();
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char val = board[i][j];
                if (val == '.') continue;
                int boxIndex = (i / 3) * 3 + j / 3;
                if (rows[i].contains(val) || cols[j].contains(val) || boxes[boxIndex].contains(val))
                    return false;
                rows[i].add(val);
                cols[j].add(val);
                boxes[boxIndex].add(val);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] board = {
            {'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'}
        };
        System.out.println(isValidSudoku(board));
    }
}

Line Notes

Set<Character>[] rows = new HashSet[9];Create array of sets for rows to track digits

int boxIndex = (i / 3) * 3 + j / 3;Compute box index for current cell

if (rows[i].contains(val) || cols[j].contains(val) || boxes[boxIndex].contains(val))Check for duplicates in row, column, or box

rows[i].add(val);Add digit to row set after confirming no duplicates

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

bool isValidSudoku(vector<vector<char>>& board) {
    vector<unordered_set<char>> rows(9), cols(9), boxes(9);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char val = board[i][j];
            if (val == '.') continue;
            int boxIndex = (i / 3) * 3 + j / 3;
            if (rows[i].count(val) || cols[j].count(val) || boxes[boxIndex].count(val))
                return false;
            rows[i].insert(val);
            cols[j].insert(val);
            boxes[boxIndex].insert(val);
        }
    }
    return true;
}

int main() {
    vector<vector<char>> board = {
        {'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'}
    };
    cout << (isValidSudoku(board) ? "true" : "false") << endl;
    return 0;
}

Line Notes

vector<unordered_set<char>> rows(9), cols(9), boxes(9);Initialize vectors of sets for rows, columns, and boxes

int boxIndex = (i / 3) * 3 + j / 3;Calculate box index for current cell

if (rows[i].count(val) || cols[j].count(val) || boxes[boxIndex].count(val))Check if digit already exists in any constraint

rows[i].insert(val);Insert digit into row set after validation

function isValidSudoku(board) {
    const rows = Array.from({length: 9}, () => new Set());
    const cols = Array.from({length: 9}, () => new Set());
    const boxes = Array.from({length: 9}, () => new Set());
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const val = board[i][j];
            if (val === '.') continue;
            const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
            if (rows[i].has(val) || cols[j].has(val) || boxes[boxIndex].has(val)) {
                return false;
            }
            rows[i].add(val);
            cols[j].add(val);
            boxes[boxIndex].add(val);
        }
    }
    return true;
}

// Test
const board = [
    ['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']
];
console.log(isValidSudoku(board));

Line Notes

const rows = Array.from({length: 9}, () => new Set());Initialize array of sets for rows

const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);Calculate box index for current cell

if (rows[i].has(val) || cols[j].has(val) || boxes[boxIndex].has(val)) {Check for duplicates in row, column, or box

rows[i].add(val);Add digit to row set after confirming no duplicates

⏱

Complexity

TimeO(9*9) = O(1)

SpaceO(9*3) = O(1)

Single pass over all cells with constant time set operations. Space is fixed for 27 sets.

💡 This approach is more efficient and elegant, suitable for interviews.

Interview Verdict: Accepted

This is the preferred approach in interviews due to clarity and efficiency.

🧠

Bitmasking for Constant Space and Faster Checks

💡 This approach uses bitmasks to represent digits seen in rows, columns, and boxes, reducing memory usage and potentially speeding up checks by using bit operations.

Intuition

Represent digits 1-9 as bits in an integer. For each cell, check if the bit is set in the corresponding row, column, or box mask. If set, duplicate found; else set the bit.

Algorithm

1. Initialize three integer arrays of size 9 for rows, columns, and boxes to 0
2. Iterate over each cell
3. Convert digit to bitmask by shifting 1 left by digit-1
4. Check if bit is set in row, column, or box mask; if yes, return false
5. Otherwise, set the bit in all three masks
6. Return true if no duplicates found

💡 Bit operations allow constant time checks and updates, but require careful indexing and masking.

</>

Code

def isValidSudoku(board):
    rows = [0] * 9
    cols = [0] * 9
    boxes = [0] * 9
    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
    return True

# Driver code
if __name__ == '__main__':
    board = [
        ["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"]
    ]
    print(isValidSudoku(board))

Line Notes

rows = [0] * 9Initialize integer masks for rows to zero

val = ord(board[i][j]) - ord('1')Convert character digit to zero-based index

mask = 1 << valCreate bitmask with bit set for current digit

if (rows[i] & mask) or (cols[j] & mask) or (boxes[box_index] & mask):Check if digit already seen in row, column, or box

public class ValidSudoku {
    public static boolean isValidSudoku(char[][] board) {
        int[] rows = new int[9];
        int[] cols = new int[9];
        int[] boxes = new int[9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int val = board[i][j] - '1';
                int mask = 1 << val;
                int boxIndex = (i / 3) * 3 + j / 3;
                if ((rows[i] & mask) != 0 || (cols[j] & mask) != 0 || (boxes[boxIndex] & mask) != 0)
                    return false;
                rows[i] |= mask;
                cols[j] |= mask;
                boxes[boxIndex] |= mask;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        char[][] board = {
            {'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'}
        };
        System.out.println(isValidSudoku(board));
    }
}

Line Notes

int[] rows = new int[9];Initialize integer arrays to store bitmasks for rows

int mask = 1 << val;Create bitmask for current digit

if ((rows[i] & mask) != 0 || (cols[j] & mask) != 0 || (boxes[boxIndex] & mask) != 0)Check if digit already present in any constraint

rows[i] |= mask;Set bit for digit in row mask

#include <iostream>
#include <vector>
using namespace std;

bool isValidSudoku(vector<vector<char>>& board) {
    int rows[9] = {0}, cols[9] = {0}, boxes[9] = {0};
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') continue;
            int val = board[i][j] - '1';
            int mask = 1 << val;
            int boxIndex = (i / 3) * 3 + j / 3;
            if ((rows[i] & mask) || (cols[j] & mask) || (boxes[boxIndex] & mask))
                return false;
            rows[i] |= mask;
            cols[j] |= mask;
            boxes[boxIndex] |= mask;
        }
    }
    return true;
}

int main() {
    vector<vector<char>> board = {
        {'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'}
    };
    cout << (isValidSudoku(board) ? "true" : "false") << endl;
    return 0;
}

Line Notes

int rows[9] = {0}, cols[9] = {0}, boxes[9] = {0};Initialize bitmask arrays for rows, columns, and boxes

int mask = 1 << val;Create bitmask for current digit

if ((rows[i] & mask) || (cols[j] & mask) || (boxes[boxIndex] & mask))Check if digit already seen in any constraint

rows[i] |= mask;Set bit for digit in row mask

function isValidSudoku(board) {
    const rows = new Array(9).fill(0);
    const cols = new Array(9).fill(0);
    const boxes = new Array(9).fill(0);
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            if (board[i][j] === '.') continue;
            const val = board[i][j].charCodeAt(0) - '1'.charCodeAt(0);
            const mask = 1 << val;
            const boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3);
            if ((rows[i] & mask) !== 0 || (cols[j] & mask) !== 0 || (boxes[boxIndex] & mask) !== 0) {
                return false;
            }
            rows[i] |= mask;
            cols[j] |= mask;
            boxes[boxIndex] |= mask;
        }
    }
    return true;
}

// Test
const board = [
    ['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']
];
console.log(isValidSudoku(board));

Line Notes

const rows = new Array(9).fill(0);Initialize integer arrays for rows bitmasks

const mask = 1 << val;Create bitmask for current digit

if ((rows[i] & mask) !== 0 || (cols[j] & mask) !== 0 || (boxes[boxIndex] & mask) !== 0)Check if digit already present in any constraint

rows[i] |= mask;Set bit for digit in row mask

⏱

Complexity

TimeO(9*9) = O(1)

SpaceO(1) using fixed integer arrays

Bitmasking uses constant space and time for fixed board size, with very fast bit operations.

💡 This approach is optimal for memory and speed but requires understanding bit operations.

Interview Verdict: Accepted

Bitmasking is a neat optimization but not always necessary unless asked for space/time improvements.

📊

All Approaches - One-Glance Tradeoffs

💡 Approach 2 (single pass with sets) is best for most interviews due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(3 * 9 * 9) = O(1)	O(9) per check	No	N/A	Mention only - never code
2. Single Pass with Sets	O(9 * 9) = O(1)	O(27) sets total	No	N/A	Code this approach
3. Bitmasking	O(9 * 9) = O(1)	O(27) integers	No	N/A	Mention if asked for optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify input size and constraintsState brute force approach checking rows, columns, and boxes separatelyExplain inefficiency and propose single pass with setsIf asked, mention bitmasking for optimizationWrite clean code and test edge cases

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Ability to handle multiple constraints simultaneously, optimize checks, and write clean, bug-free code.

Common Follow-ups

• How to solve Sudoku (backtracking) → use DFS with constraints
• How to optimize space → bitmasking approach

💡 Follow-ups test your ability to extend validation to solving and optimize resource usage.

🔍

Pattern Recognition

When to Use

1) Problem involves validating constraints in rows, columns, and sub-boxes; 2) Board or matrix input; 3) Need to detect duplicates; 4) Fixed size 9x9 grid

Signature Phrases

each row must contain digits 1-9 without repetitioneach column must contain digits 1-9 without repetitioneach 3x3 sub-box must contain digits 1-9 without repetition

NOT This Pattern When

Problems that only check rows or columns without sub-box constraints, or problems that require counting rather than validation.

Similar Problems

Sudoku Solver - extends validation to solving with backtrackingWord Search - matrix traversal with constraints

Practice

1. You are given a square matrix and need to find the sum of all elements on both its main diagonal and secondary diagonal. Which approach guarantees the most optimal time complexity for this problem?

easy

A. Use a single loop to directly access and sum elements at indices (i, i) and (i, n-1-i).

B. Use a brute force nested loop to check every element and sum those on diagonals.

C. Use dynamic programming to store sums of submatrices and combine results.

D. Use a greedy approach to pick the largest elements from diagonals first.

Solution

1. Step 1: Understand the problem constraints

   The problem requires summing elements on the main and secondary diagonals of an n x n matrix.

2. Step 2: Identify the optimal approach

   Using a single loop from 0 to n-1, we can directly access mat[i][i] and mat[i][n-1-i] in O(n) time, avoiding unnecessary checks.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single loop with direct indexing is O(n) and minimal code [OK]

Hint: Direct indexing avoids nested loops [OK]

Common Mistakes:

• Using nested loops unnecessarily
• Trying DP for a simple sum
• Misapplying greedy selection

2. You are given an n x n matrix representing an image. The task is to rotate the image by 90 degrees clockwise in-place, without using extra space. Which of the following approaches guarantees an optimal in-place solution with O(1) extra space and O(n²) time complexity?

easy

A. Perform a layer-by-layer rotation by swapping four elements at a time in-place for each layer of the matrix.

B. Apply a dynamic programming approach to store intermediate rotations and build the final rotated matrix.

C. Use a brute force approach by creating a new matrix and copying elements to their rotated positions.

D. Transpose the matrix and then reverse each column to achieve the rotation.

Solution

1. Step 1: Understand the problem constraints

   The problem requires rotating the matrix in-place with O(1) extra space and O(n²) time.

2. Step 2: Evaluate approaches

   Brute force uses extra space, DP is unrelated, and transposing then reversing columns rotates counterclockwise, not clockwise. Layer-by-layer four-way swaps correctly rotate clockwise in-place.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Layer-by-layer swaps rotate in-place with correct direction and complexity [OK]

Hint: Layer-by-layer four-way swaps rotate in-place clockwise [OK]

Common Mistakes:

• Confusing transpose+reverse columns with clockwise rotation
• Using extra space when in-place is required

3. You are given a 2D matrix and asked to output all elements starting from the outermost layer and moving inward in a clockwise manner, visiting each element exactly once. Which algorithmic approach best guarantees an efficient and correct solution for this problem?

easy

A. Perform a depth-first search (DFS) starting from the top-left corner, marking visited cells to avoid repeats.

B. Use a greedy approach that picks the next available element in clockwise order without tracking boundaries.

C. Apply dynamic programming to store intermediate traversal states and build the spiral order iteratively.

D. Simulate the traversal by shrinking the boundaries inward after completing each outer layer, ensuring no element is revisited.

Solution

1. Step 1: Understand the problem constraints

   The problem requires visiting all elements in a matrix in a spiral order without repetition, moving layer by layer inward.

2. Step 2: Identify the approach that guarantees correctness and efficiency

   Simulating the traversal by shrinking boundaries after completing each layer ensures no element is revisited and the traversal is orderly and complete.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Boundary shrinking matches the spiral traversal pattern perfectly [OK]

Hint: Boundary shrinking ensures no repeats and full coverage [OK]

Common Mistakes:

• Greedy approach misses boundary checks causing repeats
• DFS can revisit or miss elements without careful visited tracking
• DP is not suitable for traversal order problems

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

5. Suppose the matrix is no longer sorted row-wise or column-wise but only each row is sorted independently. Which approach correctly counts negative numbers efficiently in this scenario?

hard

A. Use the staircase search from top-right corner as before.

B. Use brute force nested loops to check every element.

C. Perform binary search on each row to find the first negative number and sum counts.

D. Apply dynamic programming to store counts of negatives in submatrices.

Solution

1. Step 1: Analyze sorting constraints

   Only rows are sorted, columns are not, so staircase search relying on column sorting fails.

2. Step 2: Choose correct approach

   Binary search per row finds first negative efficiently in O(log n), total O(m log n), better than brute force.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Row-wise binary search exploits partial sorting [OK]

Hint: When only rows sorted, binary search per row is optimal [OK]

Common Mistakes:

• Trying staircase search without column sorting
• Using brute force ignoring partial sorting
• Assuming DP is needed