Check Sudoku Board Configuration is Valid or Not

Given a Sudoku board configuration, check whether the given Sudoku board configuration is valid or not. A valid configuration requires that each row, column, and 3x3 sub-matrix must contain the digits 1-9 without repetition.

Examples:

Input:

Output: true
Explanation: It is possible to have a proper sudoku.

Try it on GfG Practice

Table of Content

[Naive Approach] Checking Constraints - Time O(n^3) and Space O(n)
[Better Approach 1] Using Hashing - Time O(n^2) and Space O(n^2)
[Better Approach 2] Using Array of Fixed Length - Time O(n^2) and Space O(n^2)
[Expected Approach] Using Bitmasking

[Naive Approach] Checking Constraints - Time O(n^3) and Space O(n)

Every number between 1 to 9 appears only once in every row, column and 3X3 sub-matrix of the sudoku. Check for every cell that it's value is appearing only once in it's row, column and 3X3 sub-matrix.

C++

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

// Checks for duplicates in the current row
bool validRow(vector<vector<int>>& mat, int row) {

    vector<int> vis(10, 0);

    for (int i = 0; i < 9; i++) {

        // If the cell is not empty
        if (mat[row][i] != 0) {
            int val = mat[row][i];

            // If duplicate is found
            if (vis[val] != 0)
                return false;

            // Mark the number as visited
            vis[val]++;
        }
    }
    return true;
}

// Checks for duplicates in the current column
bool colValid(vector<vector<int>>& mat, int col) {

    // Visited array to track occurrences
    vector<int> vis(10, 0);

    for (int i = 0; i < 9; i++) {

        // If the cell is not empty
        if (mat[i][col] != 0) {
            int val = mat[i][col];

            // If duplicate is found
            if (vis[val] != 0)
                return false;

            // Mark the number as visited
            vis[val]++;
        }
    }
    return true;
}

// Checks for duplicates in 
// the current 3x3 submatrix
bool subMatValid(vector<vector<int>>& mat, 
                    int startRow, int startCol) {

    // Visited array to track occurrences
    vector<int> vis(10, 0);

    for (int row = 0; row < 3; row++) {
        for (int col = 0; col < 3; col++) {

            // Current element in the submatrix
            int curr = mat[row + startRow][col + startCol];

            // If the cell is not empty
            if (curr != 0) {

                // If duplicate is found
                if (vis[curr] != 0)
                    return false;

                // Mark the number as visited
                vis[curr]++;
            }
        }
    }
    return true;
}

// Validates the Sudoku board
bool isValid(vector<vector<int>>& mat) {
  
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {

            // Check if the row, column,
            // or submatrix is invalid
            if (!validRow(mat, i) || !colValid(mat, j)
                || !subMatValid(mat, i - i % 3, j - j % 3))
                return false; 
        }
    }
    return true; 
}

int main() {

    vector<vector<int>> mat = {
        {9, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 5, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };
    
    cout << (isValid(mat) ? "true" : "false") << endl;
    return 0;
}

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

// Checks for duplicates in current row
bool validRow(int mat[9][9], int row){
  
    // Integer array for marking visited
    int vis[10] = {0};

    for (int i = 0; i < 9; i++)
    {
        // If the cell is not empty
        if (mat[row][i] != 0)
        {

            // If duplicate is found
            if (vis[mat[row][i]] != 0)
                return false;

            // Mark occurrence in the visited array
            vis[mat[row][i]]++;
        }
    }
    return true;
}

// Checks for duplicates in current column
bool colValid(int mat[9][9], int col)
{

    // Integer array for hashing
    int vis[10] = {0};

    // Loop through the column
    for (int i = 0; i < 9; i++)
    {

        // If the cell is not empty
        if (mat[i][col] != 0)
        {

            // If duplicate is found
            if (vis[mat[i][col]] != 0)
                return false;

            // Mark occurrence in the hash array
            vis[mat[i][col]]++;
        }
    }
    return true;
}

// Checks for duplicates in 
// the current 3x3 submatrix
bool subMatValid(int mat[9][9], int startRow,
                                      int startCol){

    // Integer array for hashing
    int vis[10] = {0};

    for (int row = 0; row < 3; row++){
        for (int col = 0; col < 3; col++){

            // Current element in the submatrix
            int curr = mat[row + startRow][col + startCol];

            // If the cell is not empty
            if (curr != 0){

                // If duplicate is found
                if (vis[curr] != 0)
                    return false;

                // Mark occurrence in the hash array
                vis[curr]++;
            }
        }
    }
    return true;
}

// Validates the Sudoku board
bool isValid(int mat[9][9]){

    for (int i = 0; i < 9; i++){
        for (int j = 0; j < 9; j++){

            // Check if row, column, or submatrix is invalid
            if (!validRow(mat, i) || !colValid(mat, j)
                || !subMatValid(mat, i - i % 3, j - j % 3))
                return false;
        }
    }
    return true;
}

int main(){
    int mat[9][9] = {{9, 3, 0, 0, 7, 0, 0, 0, 0},
                     {6, 0, 0, 1, 9, 5, 0, 0, 0},
                     {0, 5, 8, 0, 0, 0, 0, 6, 0},
                     {8, 0, 0, 0, 6, 0, 0, 0, 3},
                     {4, 0, 0, 8, 0, 3, 0, 0, 1},
                     {7, 0, 0, 0, 2, 0, 0, 0, 6},
                     {0, 6, 0, 0, 0, 0, 2, 8, 0},
                     {0, 0, 0, 4, 1, 9, 0, 0, 5},
                     {0, 0, 0, 0, 8, 0, 0, 7, 9}};

    printf(isValid(mat) ? "true\n" : "false\n");
    return 0;
}

Java

class GfG {

    // Checks for duplicates in the current row
    static boolean validRow(int[][] mat, int row) {

        // Visited array to track occurrences
        int[] vis = new int[10];
        
        for (int i = 0; i < 9; i++) {

            // If the cell is not empty
            if (mat[row][i] != 0) {
                int val = mat[row][i];

                // If duplicate is found
                if (vis[val] != 0)
                    return false;

                // Mark the number as visited
                vis[val]++;
            }
        }
        return true;
    }

    // Checks for duplicates in the current column
    static boolean colValid(int[][] mat, int col) {

        // Visited array to track occurrences
        int[] vis = new int[10];
        
        for (int i = 0; i < 9; i++) {

            // If the cell is not empty
            if (mat[i][col] != 0) {
                int val = mat[i][col];

                // If duplicate is found
                if (vis[val] != 0)
                    return false;

                // Mark the number as visited
                vis[val]++;
            }
        }
        return true;
    }

    // Checks for duplicates in 
    // the current 3x3 submatrix
    static boolean subMatValid(int[][] mat, int startRow,
                                         int startCol) {

        // Visited array to track occurrences
        int[] vis = new int[10];
        
        for (int row = 0; row < 3; row++) {
            for (int col = 0; col < 3; col++) {

                // Current element in the submatrix
                int curr = mat[row + startRow][col + startCol];
                
                // If the cell is not empty
                if (curr != 0) {

                    // If duplicate is found
                    if (vis[curr] != 0)
                        return false;

                    // Mark the number as visited
                    vis[curr]++;
                }
            }
        }
        return true;
    }

    // Validates the Sudoku board
    static boolean isValid(int[][] mat) {

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {

                // Check if the row, column,
                // or submatrix is invalid
                if (!validRow(mat, i) || !colValid(mat, j)
                    || !subMatValid(mat, i - i % 3, j - j % 3))
                    return false;
            }
        }
        return true; 
    }

    public static void main(String[] args) {

        int[][] mat = {
            {9, 3, 0, 0, 7, 0, 0, 0, 0},
            {6, 0, 0, 1, 9, 5, 0, 0, 0},
            {0, 5, 8, 0, 0, 0, 0, 6, 0},
            {8, 0, 0, 0, 6, 0, 0, 0, 3},
            {4, 0, 0, 8, 0, 3, 0, 0, 1},
            {7, 0, 0, 0, 2, 0, 0, 0, 6},
            {0, 6, 0, 0, 0, 0, 2, 8, 0},
            {0, 0, 0, 4, 1, 9, 0, 0, 5},
            {0, 0, 0, 0, 8, 0, 0, 7, 9}
        };
        System.out.println(isValid(mat) ? "true" : "false");
    }
}

Python

# Checks for duplicates in the current row
def validRow(mat, row):

    # Visited array to track occurrences
    vis = [0] * 10
    
    for i in range(9):

        # If the cell is not empty
        if mat[row][i] != 0:
            val = mat[row][i]

            # If duplicate is found
            if vis[val] != 0:
                return False

            # Mark the number as visited
            vis[val] += 1
    return True

# Checks for duplicates in the current column
def colValid(mat, col):

    # Visited array to track occurrences
    vis = [0] * 10
    
    for i in range(9):

        # If the cell is not empty
        if mat[i][col] != 0:
            val = mat[i][col]

            # If duplicate is found
            if vis[val] != 0:
                return False

            # Mark the number as visited
            vis[val] += 1
    return True

# Checks for duplicates in the current 3x3 submatrix
def subMatValid(mat, startRow, startCol):

    # Visited array to track occurrences
    vis = [0] * 10
    
    for row in range(3):
        for col in range(3):

            # Current element in the submatrix
            curr = mat[row + startRow][col + startCol]

            # If the cell is not empty
            if curr != 0:

                # If duplicate is found
                if vis[curr] != 0:
                    return False

                # Mark the number as visited
                vis[curr] += 1
    return True

# Validates the Sudoku board
def isValid(mat):
    for i in range(9):
        for j in range(9):

            # Check if the row, column, or submatrix is invalid
            if not validRow(mat, i) or not colValid(mat, j) or \
               not subMatValid(mat, i - i % 3, j - j % 3):
                return False
    return True 

if __name__ == "__main__":
    mat = [
        [9, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 5, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9]
    ]
    print("true" if isValid(mat) else "false")

using System;

class GfG {

    // Checks for duplicates in the current row
    static bool ValidRow(int[, ] mat, int row)
    {

        // Visited array to track occurrences
        int[] vis = new int[10];

        for (int i = 0; i < 9; i++) {

            // If the cell is not empty
            if (mat[row, i] != 0) {
                int val = mat[row, i];

                // If duplicate is found
                if (vis[val] != 0)
                    return false;

                // Mark the number as visited
                vis[val]++;
            }
        }
        return true;
    }

    // Checks for duplicates in the current column
    static bool ColValid(int[, ] mat, int col)
    {

        // Visited array to track occurrences
        int[] vis = new int[10];

        for (int i = 0; i < 9; i++) {

            // If the cell is not empty
            if (mat[i, col] != 0) {
                int val = mat[i, col];

                // If duplicate is found
                if (vis[val] != 0)
                    return false;

                // Mark the number as visited
                vis[val]++;
            }
        }
        return true;
    }

    // Checks for duplicates in 
    // current 3x3 submatrix
    static bool SubMatValid(int[, ] mat, int startRow,
                            int startCol)
    {

        // Visited array to track occurrences
        int[] vis = new int[10];

        for (int row = 0; row < 3; row++) {
            for (int col = 0; col < 3; col++) {

                // Current element in the submatrix
                int curr
                    = mat[row + startRow, col + startCol];

                // If the cell is not empty
                if (curr != 0) {

                    // If duplicate is found
                    if (vis[curr] != 0)
                        return false;

                    // Mark the number as visited
                    vis[curr]++;
                }
            }
        }
        return true;
    }

    // Validates the Sudoku board
    static bool IsValid(int[, ] mat)
    {

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {

                // Check if the row, column, or submatrix is
                // invalid
                if (!ValidRow(mat, i) || !ColValid(mat, j)
                    || !SubMatValid(mat, i - i % 3,
                                    j - j % 3))
                    return false;
            }
        }
        return true;
    }

    static void Main(){
        int[, ] mat = { { 9, 3, 0, 0, 7, 0, 0, 0, 0 },
                        { 6, 0, 0, 1, 9, 5, 0, 0, 0 },
                        { 0, 5, 8, 0, 0, 0, 0, 6, 0 },
                        { 8, 0, 0, 0, 6, 0, 0, 0, 3 },
                        { 4, 0, 0, 8, 0, 3, 0, 0, 1 },
                        { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
                        { 0, 6, 0, 0, 0, 0, 2, 8, 0 },
                        { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
                        { 0, 0, 0, 0, 8, 0, 0, 7, 9 } };
        Console.WriteLine(IsValid(mat) ? "true" : "false");
    }
}

JavaScript

// Checks for duplicates in the current row
function validRow(mat, row)
{

    // Visited array to track occurrences
    let vis = Array(10).fill(0);

    for (let i = 0; i < 9; i++) {

        // If the cell is not empty
        if (mat[row][i] !== 0) {
            let val = mat[row][i];

            // If duplicate is found
            if (vis[val] !== 0)
                return false;

            // Mark the number as visited
            vis[val]++;
        }
    }
    return true;
}

// Checks for duplicates in the current column
function colValid(mat, col)
{

    // Visited array to track occurrences
    let vis = Array(10).fill(0);

    for (let i = 0; i < 9; i++) {

        // If the cell is not empty
        if (mat[i][col] !== 0) {
            let val = mat[i][col];

            // If duplicate is found
            if (vis[val] !== 0)
                return false;

            // Mark the number as visited
            vis[val]++;
        }
    }
    return true;
}

// Checks for duplicates in 
// the current 3x3 submatrix
function subMatValid(mat, startRow, startCol)
{

    // Visited array to track occurrences
    let vis = Array(10).fill(0);

    for (let row = 0; row < 3; row++) {
        for (let col = 0; col < 3; col++) {

            // Current element in the submatrix
            let curr = mat[row + startRow][col + startCol];

            // If the cell is not empty
            if (curr !== 0) {

                // If duplicate is found
                if (vis[curr] !== 0)
                    return false;

                // Mark the number as visited
                vis[curr]++;
            }
        }
    }
    return true;
}

// Validates the Sudoku board
function isValid(mat)
{

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {

            // Check if the row, column, or submatrix is
            // invalid
            if (!validRow(mat, i) || !colValid(mat, j)
                || !subMatValid(mat, i - i % 3, j - j % 3))
                return false;
        }
    }
    return true;
}

// Driver code
let mat = [
    [ 9, 3, 0, 0, 7, 0, 0, 0, 0 ],
    [ 6, 0, 0, 1, 9, 5, 0, 0, 0 ],
    [ 0, 5, 8, 0, 0, 0, 0, 6, 0 ],
    [ 8, 0, 0, 0, 6, 0, 0, 0, 3 ],
    [ 4, 0, 0, 8, 0, 3, 0, 0, 1 ],
    [ 7, 0, 0, 0, 2, 0, 0, 0, 6 ],
    [ 0, 6, 0, 0, 0, 0, 2, 8, 0 ],
    [ 0, 0, 0, 4, 1, 9, 0, 0, 5 ],
    [ 0, 0, 0, 0, 8, 0, 0, 7, 9 ]
];
console.log(isValid(mat) ? "true" : "false");

Output

true

[Better Approach 1] Using Hashing - Time O(n^2) and Space O(n^2)

This approach improves the time complexity of the previous method, but with a trade-off in space complexity. We use an unordered set for each row, column, and sub-matrix to track the values we’ve already seen/visited.
As we iterate through the matrix and for each cell, we check if the current cell value already exists in the corresponding row, column, or sub-grid. If a duplicate is found, the Sudoku board is invalid. If no duplicates are found after checking all cells, the board configuration is valid.

Important Observation: There are 9 submatrix of size 3*3 exists in the sudoku matrix, so to find index of sub-matrix we can use the formula (i / 3) * 3 + j / 3, where i and j are the row and column indices.

C++

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

// Function to check if the Sudoku matrix is valid
int isValid(vector<vector<int>> & mat) {
  
    // Arrays of unordered sets to keep track of seen
    // numbers in rows, columns, and subMatrix
    unordered_set<int> rows[9];
    unordered_set<int> cols[9];
    unordered_set<int> subMat[9];

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
          
            // Get the value at the current cell
            int val = mat[i][j];

            // For empty (0), skip to the next cell
            if (val == 0) continue;

            // Check if the value already exists
            // in the current row
            if (rows[i].find(val) != rows[i].end()) {
              
                // Duplicate found, return false
                return false;
            }
          
            // Insert the value into the current row's set
            rows[i].insert(val);

            // Check if the value already exists
            // in the current column
            if (cols[j].find(val) != cols[j].end()) {
              
                // Duplicate found, return false
                return false; 
            }
          
            // Insert the value into the current column's set
            cols[j].insert(val);

            // Calculate the index for the 3x3 box
            int idx = (i / 3) * 3 + j / 3;
          
            // Check if the value already exists
            // in the current 3x3 box
            if (subMat[idx].find(val) != subMat[idx].end()) {
              
                // Duplicate found, return false
                return false; 
            }
          
            // Insert the value into the current box's set
            subMat[idx].insert(val);
        }
    }
  
    // If no duplicates were found, return true
    return true;
}

int main() {

    vector<vector<int>> mat = {
        {9, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 5, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };
    cout << (isValid(mat) ? "true" : "false") << "\n";
    return 0;
}

Java

import java.util.List;
import java.util.ArrayList;
import java.util.HashSet;

class GfG {

    // Function to check if the Sudoku matrix is valid
    static boolean isValid(int[][] mat) {

        // Lists of sets to track seen numbers in rows, columns, and subMatrices
        List<HashSet<Integer>> rows = new ArrayList<>();
        List<HashSet<Integer>> cols = new ArrayList<>();
        List<HashSet<Integer>> subMat = new ArrayList<>();
        
        // Initialize the sets
        for (int i = 0; i < 9; i++) {
            rows.add(new HashSet<>());
            cols.add(new HashSet<>());
            subMat.add(new HashSet<>());
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int val = mat[i][j];

                // Skip empty cells
                if (val == 0) continue;

                // Check for duplicates in the row
                if (rows.get(i).contains(val)) return false;
                rows.get(i).add(val);

                // Check for duplicates in the column
                if (cols.get(j).contains(val)) return false;
                cols.get(j).add(val);

                // Calculate the sub-matrix index
                int idx = (i / 3) * 3 + (j / 3);

                // Check for duplicates in the sub-matrix
                if (subMat.get(idx).contains(val)) return false;
                subMat.get(idx).add(val);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[][] mat = {
            {9, 3, 0, 0, 7, 0, 0, 0, 0},
            {6, 0, 0, 1, 9, 5, 0, 0, 0},
            {0, 5, 8, 0, 0, 0, 0, 6, 0},
            {8, 0, 0, 0, 6, 0, 0, 0, 3},
            {4, 0, 0, 8, 0, 3, 0, 0, 1},
            {7, 0, 0, 0, 2, 0, 0, 0, 6},
            {0, 6, 0, 0, 0, 0, 2, 8, 0},
            {0, 0, 0, 4, 1, 9, 0, 0, 5},
            {0, 0, 0, 0, 8, 0, 0, 7, 9}
        };

        System.out.println(isValid(mat) ? "true" : "false");
    }
}

Python

# Function to check if the Sudoku matrix is valid
def isValid(mat):

    # Arrays of sets to track seen numbers in rows, cols
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    subMat = [set() for _ in range(9)]

    # Loop through the Sudoku grid
    for i in range(9):
        for j in range(9):
            val = mat[i][j]

            # Skip empty cells
            if val == 0:
                continue

            # Check for duplicates in the row
            if val in rows[i]:
                return False
            rows[i].add(val)

            # Check for duplicates in the column
            if val in cols[j]:
                return False
            cols[j].add(val)

            # Calculate the sub-matrix index
            idx = (i // 3) * 3 + (j // 3)

            # Check for duplicates in the sub-matrix
            if val in subMat[idx]:
                return False
            subMat[idx].add(val)

    return True

if __name__ == "__main__" :
    mat = [
        [9, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 5, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9]
    ]
    
    # Check if the Sudoku matrix is valid
    print("true" if isValid(mat) else "false")

using System;
using System.Collections.Generic;

class GfG {

    // Function to check if the Sudoku matrix is valid
    static bool IsValid(int[, ] mat)
    {

        // Arrays of sets to track seen numbers in rows,
        // cols
        HashSet<int>[] rows = new HashSet<int>[ 9 ];
        HashSet<int>[] cols = new HashSet<int>[ 9 ];
        HashSet<int>[] subMat = new HashSet<int>[ 9 ];

        // Initialize the sets
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<int>();
            cols[i] = new HashSet<int>();
            subMat[i] = new HashSet<int>();
        }

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int val = mat[i, j];

                // Skip empty cells
                if (val == 0)
                    continue;

                // Check for duplicates in the row
                if (rows[i].Contains(val))
                    return false;
                rows[i].Add(val);

                // Check for duplicates in the column
                if (cols[j].Contains(val))
                    return false;
                cols[j].Add(val);

                // Calculate the sub-matrix index
                int idx = (i / 3) * 3 + j / 3;

                // Check for duplicates in the sub-matrix
                if (subMat[idx].Contains(val))
                    return false;
                subMat[idx].Add(val);
            }
        }
        return true;
    }

    static void Main()
    {
        int[, ] mat = { { 9, 3, 0, 0, 7, 0, 0, 0, 0 },
                        { 6, 0, 0, 1, 9, 5, 0, 0, 0 },
                        { 0, 5, 8, 0, 0, 0, 0, 6, 0 },
                        { 8, 0, 0, 0, 6, 0, 0, 0, 3 },
                        { 4, 0, 0, 8, 0, 3, 0, 0, 1 },
                        { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
                        { 0, 6, 0, 0, 0, 0, 2, 8, 0 },
                        { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
                        { 0, 0, 0, 0, 8, 0, 0, 7, 9 } };

        Console.WriteLine(IsValid(mat) ? "true" : "false");
    }
}

JavaScript

// Function to check if the Sudoku matrix is valid
function isValid(mat){

    // Arrays to track seen numbers in rows, cols, and
    // subMatrices
    let rows = Array.from({length : 9}, () => new Set());
    let cols = Array.from({length : 9}, () => new Set());
    let subMat = Array.from({length : 9}, () => new Set());

    // Loop through the Sudoku grid
    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            let val = mat[i][j];

            // Skip empty cells
            if (val === 0)
                continue;

            // Check for duplicates in the row
            if (rows[i].has(val))
                return false;
            rows[i].add(val);

            // Check for duplicates in the column
            if (cols[j].has(val))
                return false;
            cols[j].add(val);

            // Calculate the sub-matrix index
            let idx
                = Math.floor(i / 3) * 3 + Math.floor(j / 3);

            // Check for duplicates in the sub-matrix
            if (subMat[idx].has(val))
                return false;
            subMat[idx].add(val);
        }
    }
    return true;
}


// Driver code
let mat = [
    [ 9, 3, 0, 0, 7, 0, 0, 0, 0 ],
    [ 6, 0, 0, 1, 9, 5, 0, 0, 0 ],
    [ 0, 5, 8, 0, 0, 0, 0, 6, 0 ],
    [ 8, 0, 0, 0, 6, 0, 0, 0, 3 ],
    [ 4, 0, 0, 8, 0, 3, 0, 0, 1 ],
    [ 7, 0, 0, 0, 2, 0, 0, 0, 6 ],
    [ 0, 6, 0, 0, 0, 0, 2, 8, 0 ],
    [ 0, 0, 0, 4, 1, 9, 0, 0, 5 ],
    [ 0, 0, 0, 0, 8, 0, 0, 7, 9 ]
];
console.log(isValid(mat) ? "true" : "false");

Output

true

[Better Approach 2] Using Array of Fixed Length - Time O(n^2) and Space O(n^2)

Instead of using any hash table for keeping track of seen/visited elements, We can use auxiliary arrays to track the seen/visited of each number in rows, columns, and sub-matrix. By using arrays, we can eliminate the overhead of hashing.

Step-by-step approach:

We use three 2D arrays (rows, cols, subMat) to track which numbers have already appeared in each row, column, and sub-matrix, respectively.
For each cell, we skip if it contains 0 (empty). Otherwise, we check if the number has already appeared in the corresponding row, column, or sub-matrix. If so, the matrix is invalid.
The sub-matrix index is calculated as (i / 3) * 3 + j / 3 where i and j are the row and column indices.
If the current number is not visited before in the current row, column, or sub-matrix then marked as seen/visited.

C++

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

// Function to check if the Sudoku matrix is valid
int isValid(vector<vector<int>> & mat){
  
    // Track of numbers in rows, columns, and sub-matrix
    vector<vector<int>> rows(10, vector<int>(10, 0));
    vector<vector<int>> cols(10, vector<int>(10, 0));
    vector<vector<int>> subMat(10, vector<int>(10, 0));

    for (int i = 0; i < 9; i++){
        for (int j = 0; j < 9; j++){

            // Skip empty cells
            if (mat[i][j] == 0)
                continue;

            // Current value
            int val = mat[i][j]; 

            // Check for duplicates in row
            if (rows[i][val] == 1)
                return false;

            // Mark as seen
            rows[i][val] = 1; 

            // Check for duplicates in column
            if (cols[j][val] == 1)
                return false;

            // Mark as seen
            cols[j][val] = 1; 

            // Check for duplicates in sub-grid
            int idx = (i / 3) * 3 + j / 3;
            if (subMat[idx][val] == 1)
                return false;

            // Mark as seen
            subMat[idx][val] = 1; 
        }
    }

    return true;
}

int main(){
    vector<vector<int>> mat = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}};

    cout << (isValid(mat) ? "true" : "false") << "\n";

    return 0;
}

#include <stdio.h>
#include <stdbool.h>

int isValid(int mat[9][9]) {
  
    // Track of numbers in rows, columns, and sub-matrix
    int rows[10][10] = {0};
    int cols[10][10] = {0};
    int subMat[10][10] = {0};

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
          
            // Skip empty cells
            if (mat[i][j] == 0)
                continue;

            // Current value
            int val = mat[i][j];

            // Check for duplicates in row
            if (rows[i][val] == 1)
                return false; // false

            // Mark as seen
            rows[i][val] = 1;

            // Check for duplicates in column
            if (cols[j][val] == 1)
                return false; // false

            // Mark as seen
            cols[j][val] = 1;

            // Check for duplicates in sub-grid
            int idx = (i / 3) * 3 + j / 3;
            if (subMat[idx][val] == 1)
                return 0; 

            // Mark as seen
            subMat[idx][val] = 1;
        }
    }

    return true;
}

int main() {
    int mat[9][9] = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };

    printf("%s\n", isValid(mat) ? "true" : "false");

    return 0;
}

Java

class GfG {
    static boolean isValid(int[][] mat){

        // Track of numbers in rows, columns,
        // and sub-matrix
        int[][] rows = new int[10][10];
        int[][] cols = new int[10][10];
        int[][] subMat = new int[10][10];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {

                // Skip empty cells
                if (mat[i][j] == 0)
                    continue;

                // Current value
                int val = mat[i][j];

                // Check for duplicates in row
                if (rows[i][val] == 1)
                    return false;

                // Mark as seen
                rows[i][val] = 1;

                // Check for duplicates in column
                if (cols[j][val] == 1)
                    return false;

                // Mark as seen
                cols[j][val] = 1;

                // Check for duplicates in sub-grid
                int idx = (i / 3) * 3 + j / 3;
                if (subMat[idx][val] == 1)
                    return false;

                // Mark as seen
                subMat[idx][val] = 1;
            }
        }
        return true;
    }

    public static void main(String[] args)
    {
        int[][] mat = { { 5, 3, 0, 0, 7, 0, 0, 0, 0 },
                        { 6, 0, 0, 1, 9, 5, 0, 0, 0 },
                        { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
                        { 8, 0, 0, 0, 6, 0, 0, 0, 3 },
                        { 4, 0, 0, 8, 0, 3, 0, 0, 1 },
                        { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
                        { 0, 6, 0, 0, 0, 0, 2, 8, 0 },
                        { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
                        { 0, 0, 0, 0, 8, 0, 0, 7, 9 } };

        System.out.println(isValid(mat) ? "true" : "false");
    }
}

Python

def isValid(mat):
    # Track of numbers in rows, columns, and sub-matrix
    rows = [[0] * 10 for _ in range(10)]
    cols = [[0] * 10 for _ in range(10)]
    subMat = [[0] * 10 for _ in range(10)]

    for i in range(9):
        for j in range(9):
            # Skip empty cells
            if mat[i][j] == 0:
                continue

            # Current value
            val = mat[i][j]

            # Check for duplicates in row
            if rows[i][val] == 1:
                return False

            # Mark as seen
            rows[i][val] = 1

            # Check for duplicates in column
            if cols[j][val] == 1:
                return False

            # Mark as seen
            cols[j][val] = 1

            # Check for duplicates in sub-grid
            idx = (i // 3) * 3 + j // 3
            if subMat[idx][val] == 1:
                return False

            # Mark as seen
            subMat[idx][val] = 1

    return True


if __name__ == "__main__":
    mat = [
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9]
    ]
    
    print("true" if isValid(mat) else "false")

using System;

class GfG {
  
    // Function to check if the Sudoku matrix is valid
    static bool IsValid(int[, ] mat){
      
        // Track of numbers in rows, columns, and sub-matrix
        int[, ] rows = new int[10, 10];
        int[, ] cols = new int[10, 10];
        int[, ] subMat = new int[10, 10];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // Skip empty cells
                if (mat[i, j] == 0)
                    continue;

                // Current value
                int val = mat[i, j];

                // Check for duplicates in row
                if (rows[i, val] == 1)
                    return false;

                // Mark as seen
                rows[i, val] = 1;

                // Check for duplicates in column
                if (cols[j, val] == 1)
                    return false;

                // Mark as seen
                cols[j, val] = 1;

                // Check for duplicates in sub-grid
                int idx = (i / 3) * 3 + j / 3;
                if (subMat[idx, val] == 1)
                    return false;

                // Mark as seen
                subMat[idx, val] = 1;
            }
        }

        return true;
    }

    static void Main(){
        int[, ] mat = { { 5, 3, 0, 0, 7, 0, 0, 0, 0 },
                        { 6, 0, 0, 1, 9, 5, 0, 0, 0 },
                        { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
                        { 8, 0, 0, 0, 6, 0, 0, 0, 3 },
                        { 4, 0, 0, 8, 0, 3, 0, 0, 1 },
                        { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
                        { 0, 6, 0, 0, 0, 0, 2, 8, 0 },
                        { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
                        { 0, 0, 0, 0, 8, 0, 0, 7, 9 } };

        Console.WriteLine(IsValid(mat) ? "true" : "false");
    }
}

JavaScript

// Function to check if the Sudoku matrix is valid
function isValid(mat) {

    // Track numbers in rows, columns, and sub-matrices
    let rows = Array.from({ length: 9 }, () => Array(10).fill(0));
    let cols = Array.from({ length: 9 }, () => Array(10).fill(0));
    let subMat = Array.from({ length: 9 }, () => Array(10).fill(0));

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {

            // Skip empty cells
            if (mat[i][j] === 0) continue;

            let val = mat[i][j];

            // Check duplicate in row
            if (rows[i][val] === 1) return false;
            rows[i][val] = 1;

            // Check duplicate in column
            if (cols[j][val] === 1) return false;
            cols[j][val] = 1;

            // Sub-matrix index
            let idx = Math.floor(i / 3) * 3 + Math.floor(j / 3);

            // Check duplicate in sub-matrix
            if (subMat[idx][val] === 1) return false;
            subMat[idx][val] = 1;
        }
    }

    return true;
}

// Driver code
let mat = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
];

console.log(isValid(mat) ? "true" : "false");

Output

true

[Expected Approach] Using Bitmasking

In the previous approach, we used arrays to track which numbers have appeared in each row, column, and sub-matrix. Now, we can make this more efficient by using bit manipulation, we represent the presence of numbers with bits in an integer, which reduces memory usage and improves time complexity as well. The implementation steps remain the same as above approach, apart from checking and marking visited values in row, column and sub-matrix.

Step-by-step approach:

Use a single integer for each row, column, and sub-matrix. Each bit in the integer corresponds to a number.
For each cell, we can use bitwise AND (&) to check if a number's bit is already set. If it is, that means the number has appeared before and the Sudoku is invalid.
If the current cell value (i,e, mat[i][j]) is not set in the row, column, or sub-matrix then we have to set the bit for the number using bitwise OR operation (|=) to mark it visited.

C++

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

bool isValid(vector<vector<int>> &mat) {

    // Arrays to track seen numbers in rows,
    // columns, and sub-matrix
    vector<int> rows(9);
    vector<int> cols(9);
    vector<int> subMat(9);

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {

            // Skip empty cells
            if (mat[i][j] == 0)
                continue;

            int val = mat[i][j];

            // Bit position for the current value
            int pos = 1 << (val - 1); 

            // Check for duplicates in the current row
            if ((rows[i] & pos) > 0)
                return false;

            // Mark the value as seen in the row
            rows[i] |= pos; 

            // Check for duplicates in the current column
            if ((cols[j] & pos) > 0)
                return false; 

            // Mark the value as seen in the column
            cols[j] |= pos; 

            // Calculate the index for the 3x3 sub-matrix
            int idx = (i / 3) * 3 + j / 3;

            // Check for duplicates in the current sub-matrix
            if ((subMat[idx] & pos) > 0)
                return false;

            // Mark the value as seen in the sub-matrix
            subMat[idx] |= pos; 
        }
    }
    return true; 
}

int main(){
    vector<vector<int>> mat = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}};

    cout << (isValid(mat) ? "true" : "false") << "\n";

    return 0;
}

#include <stdio.h>
#include <stdbool.h>

bool isValid(int mat[][9]) {
  
    // Arrays to track seen numbers in rows,
    // columns, and sub-matrix
    int rows[9] = {0}, cols[9] = {0}, subMat[9] = {0};

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
          
            // Skip empty cells
            if (mat[i][j] == 0)
                continue;

            int val = mat[i][j];
            int pos = 1 << (val - 1);

            // Check for duplicates in the current row
            if ((rows[i] & pos) > 0)
                return false;
            rows[i] |= pos;

            // Check for duplicates in the current column
            if ((cols[j] & pos) > 0)
                return false;
            cols[j] |= pos;

            // Calculate the index for the 3x3 sub-matrix
            int idx = (i / 3) * 3 + j / 3;

            // Check for duplicates in the current sub-matrix
            if ((subMat[idx] & pos) > 0)
                return false;
            subMat[idx] |= pos;
        }
    }
    return true;
}

int main() {
    int mat[][9] = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };

    printf("%s\n", isValid(mat) ? "true" : "false");
    return 0;
}

Java

import java.util.Arrays;

class GfG {
    static boolean isValid(int[][] mat){

        // Arrays to track seen numbers in rows,
        // columns, and sub-matrix
        int[] rows = new int[9];
        int[] cols = new int[9];
        int[] subMat = new int[9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {

                // Skip empty cells
                if (mat[i][j] == 0)
                    continue;

                int val = mat[i][j];
                int pos = 1 << (val - 1);

                // Check for duplicates in the current row
                if ((rows[i] & pos) > 0)
                    return false;
                rows[i] |= pos;

                // Check for duplicates
                // in the current column
                if ((cols[j] & pos) > 0)
                    return false;
                cols[j] |= pos;

                // Calculate the index for the 3x3
                // sub-matrix
                int idx = (i / 3) * 3 + j / 3;

                // Check for duplicates in the current
                // sub-matrix
                if ((subMat[idx] & pos) > 0)
                    return false;
                subMat[idx] |= pos;
            }
        }
        return true;
    }

    public static void main(String[] args)
    {
        int[][] mat = { { 5, 3, 0, 0, 7, 0, 0, 0, 0 },
                        { 6, 0, 0, 1, 9, 5, 0, 0, 0 },
                        { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
                        { 8, 0, 0, 0, 6, 0, 0, 0, 3 },
                        { 4, 0, 0, 8, 0, 3, 0, 0, 1 },
                        { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
                        { 0, 6, 0, 0, 0, 0, 2, 8, 0 },
                        { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
                        { 0, 0, 0, 0, 8, 0, 0, 7, 9 } };

        System.out.println(isValid(mat) ? "true" : "false");
    }
}

Python

def isValid(mat):
  
    # Arrays to track seen numbers in rows,
    # columns, and sub-matrix
    rows = [0] * 9
    cols = [0] * 9
    subMat = [0] * 9

    for i in range(9):
        for j in range(9):
            # Skip empty cells
            if mat[i][j] == 0:
                continue

            val = mat[i][j]
            pos = 1 << (val - 1)

            # Check for duplicates in the current row
            if (rows[i] & pos) > 0:
                return False
            rows[i] |= pos

            # Check for duplicates in the current column
            if (cols[j] & pos) > 0:
                return False
            cols[j] |= pos

            # Calculate the index for the 3x3 sub-matrix
            idx = (i // 3) * 3 + j // 3

            # Check for duplicates in the current sub-matrix
            if (subMat[idx] & pos) > 0:
                return False
            subMat[idx] |= pos

    return True

if __name__ == "__main__":
    mat = [
        [5, 3, 0, 0, 7, 0, 0, 0, 0],
        [6, 0, 0, 1, 9, 5, 0, 0, 0],
        [0, 9, 8, 0, 0, 0, 0, 6, 0],
        [8, 0, 0, 0, 6, 0, 0, 0, 3],
        [4, 0, 0, 8, 0, 3, 0, 0, 1],
        [7, 0, 0, 0, 2, 0, 0, 0, 6],
        [0, 6, 0, 0, 0, 0, 2, 8, 0],
        [0, 0, 0, 4, 1, 9, 0, 0, 5],
        [0, 0, 0, 0, 8, 0, 0, 7, 9]
    ]

    print("true" if isValid(mat) else "false")

using System;

class GfG {
    static bool IsValid(int[, ] mat)
    {

        // Arrays to track seen numbers in rows,
        // columns, and sub-matrix
        int[] rows = new int[9];
        int[] cols = new int[9];
        int[] subMat = new int[9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // Skip empty cells
                if (mat[i, j] == 0)
                    continue;

                int val = mat[i, j];

                // Bit position for the current value
                int pos = 1 << (val - 1);

                // Check for duplicates in the current row
                if ((rows[i] & pos) > 0)
                    return false;

                // Mark the value as seen in the row
                rows[i] |= pos;

                // Check for duplicates in the current
                // column
                if ((cols[j] & pos) > 0)
                    return false;

                // Mark the value as seen in the column
                cols[j] |= pos;

                // Calculate the index for the 3x3
                // sub-matrix
                int idx = (i / 3) * 3 + j / 3;

                // Check for duplicates in the current
                // sub-matrix
                if ((subMat[idx] & pos) > 0)
                    return false;

                // Mark the value as seen in the sub-matrix
                subMat[idx] |= pos;
            }
        }
        return true;
    }

    static void Main(){
        int[, ] mat = { { 5, 3, 0, 0, 7, 0, 0, 0, 0 },
                        { 6, 0, 0, 1, 9, 5, 0, 0, 0 },
                        { 0, 9, 8, 0, 0, 0, 0, 6, 0 },
                        { 8, 0, 0, 0, 6, 0, 0, 0, 3 },
                        { 4, 0, 0, 8, 0, 3, 0, 0, 1 },
                        { 7, 0, 0, 0, 2, 0, 0, 0, 6 },
                        { 0, 6, 0, 0, 0, 0, 2, 8, 0 },
                        { 0, 0, 0, 4, 1, 9, 0, 0, 5 },
                        { 0, 0, 0, 0, 8, 0, 0, 7, 9 } };

        Console.WriteLine(IsValid(mat) ? "true" : "false");
    }
}

JavaScript

function isValid(mat) {

    // Arrays to track seen numbers using bitmask
    let rows = new Array(9).fill(0);
    let cols = new Array(9).fill(0);
    let subMat = new Array(9).fill(0);

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {

            // Skip empty cells
            if (mat[i][j] === 0) continue;

            let val = mat[i][j];

            // Bit position for current value
            let pos = 1 << (val - 1);

            // Check duplicate in row
            if ((rows[i] & pos) !== 0)
                return false;
            rows[i] |= pos;

            // Check duplicate in column
            if ((cols[j] & pos) !== 0)
                return false;
            cols[j] |= pos;

            // Sub-matrix index
            let idx = Math.floor(i / 3) * 3 + Math.floor(j / 3);

            // Check duplicate in sub-matrix
            if ((subMat[idx] & pos) !== 0)
                return false;
            subMat[idx] |= pos;
        }
    }

    return true;
}

// Driver code
let mat = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
];

console.log(isValid(mat) ? "true" : "false");

Output

true

Time Complexity: O(n^2), where n is the size of the Sudoku matrix (i.e, 9). This is because we iterate through all n*n cells of the matrix.
Auxiliary Space: O(n), as we use three arrays (rows, cols, subMat), each of size n to track the seen numbers for rows, columns, and sub-matrix. Each array element holds an integer, which is used for bitwise operations.

Check Sudoku Board Configuration is Valid or Not

[Naive Approach] Checking Constraints - Time O(n^3) and Space O(n)

[Better Approach 1] Using Hashing - Time O(n^2) and Space O(n^2)

[Better Approach 2] Using Array of Fixed Length - Time O(n^2) and Space O(n^2)

[Expected Approach] Using Bitmasking

Explore