grid47 Exploring patterns and algorithms
Nov 3, 2024
6 min read
Solution to LeetCode 36: Valid Sudoku Problem
Determine if a 9x9 Sudoku board is valid. A valid Sudoku board follows three rules: Each row, column, and 3x3 sub-box must contain the digits 1-9 without repetition. Only the filled cells need to be validated.
Problem
Approach
Steps
Complexity
Input: A 9x9 grid representing the Sudoku board. Cells contain digits '1'-'9' or '.' for empty cells.
This line declares a function named 'isValidSudoku' that takes a 2D vector 'board' representing the Sudoku board as input and returns a boolean indicating whether the board is valid.
2 : Map Initialization
map<string, bool> ma;
This line initializes an empty map 'ma' to store information about the numbers seen in each row, column, and 3x3 sub-grid.
3 : Nested Loops
for(int i =0; i <9; i++)
for(int j =0; j <9; j++) {
This nested loop iterates over each cell of the Sudoku board.
4 : Conditional Check
if(board[i][j] !='.') {
This line checks if the current cell is not empty.
5 : String Manipulation
string key ="(";
key+=board[i][j];
key+=")";
This block creates a unique key for the current number, row, or column by concatenating the number with the row or column index enclosed in parentheses.
6 : Map Operations
if(ma.count(to_string(i)+key)) returnfalse;
This line checks if the current number has already been seen in the current row. If so, it means the Sudoku is invalid, and the function returns false.
7 : Map Operations
else ma[to_string(i)+key] =true;
If the number hasn't been seen in the current row, it's added to the map with a key representing the row and number.
8 : Map Operations
if(ma.count(key+to_string(j))) returnfalse;
This line checks if the current number has already been seen in the current column. If so, it means the Sudoku is invalid, and the function returns false.
9 : Map Operations
else ma[key+to_string(j)] =true;
If the number hasn't been seen in the current column, it's added to the map with a key representing the column and number.
10 : Calculation
int x = i /3, y = j /3;
This line calculates the indices of the 3x3 sub-grid to which the current cell belongs.
This line checks if the current number has already been seen in the current 3x3 sub-grid. If so, it means the Sudoku is invalid, and the function returns false.
12 : Map Operations
else ma[to_string(x)+ key+ to_string(y)] =true;
If the number hasn't been seen in the current 3x3 sub-grid, it's added to the map with a key representing the sub-grid indices and number.
13 : Return
returntrue;
If the loop completes without finding any violations, the function returns true, indicating that the Sudoku board is valid.
Best Case: O(1)
Average Case: O(n^2)
Worst Case: O(n^2)
Description: Time complexity is O(n^2) because we are iterating through a 9x9 grid.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is O(n) due to the use of sets to track digits for rows, columns, and sub-boxes.
