36. Valid Sudoku

📝 Problem Details

• Title: 36. Valid Sudoku
• Link: https://leetcode.com/problems/valid-sudoku/
• Difficulty: Medium
• Tags/Categories: Arrays Matrix Hashmap

input matrix of chars board representing a 9x9 Sudoku board the board is partially filled determine if its a valid Sudoku configuration each row, column and 3x3 sub-box must contain digits 1-9 without repetition empty cells are represented as .

💡 Explanation of Solution

- use hashsets for O(1) lookup
	- maintain three hashsets
		- rows[9] --> keeps track of seen numbers in each row 
		- cols[9] --> keeps track of seen number in each column
		- boxes[9] --> keeps track of seen numbers in each 3x3 box

- iterate through the board 
	- if the current cell is empty `.` skip it 
	- compute the box index using :
		- boxIndex = (row / 3) * 3 + col / 3
	- check if the number exists in:
		- rows[row]
		- cols[col]
		- boxes[boxIndex]
	- if found, return false
	- otherwise, insert the number into the sets and continue

- return true if all constraints are satisfied 

⌛ Complexity Analysis

Time Complexity: O(1)
- since the board is always 9x9, we iterate over all cells (fixed size)

Space Complexity: O(1)
- three arrays of hash sets with a max size of 9

💻 Implementation of Solution

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<unordered_set<char>> rows(9), cols(9), boxes(9);
 
        for(int row = 0; row < 9; row++) {
            for(int col = 0; col < 9; col++) {
 
                char val = board[row][col];
 
                if(val == '.') continue; // check if empty space
 
                //if the value already exists in the current row, its an invalid sudoku
                if(rows[row].find(val) == rows[row].end()) {
                    rows[row].insert(val);
                } else {
                    return false;
                }
 
                //if the value already exists in the current column, its an invalid sudoku
                if(cols[col].find(val) == cols[col].end()) {
                    cols[col].insert(val);
                }else {
                    return false;
                }
 
                int boxIndex = (row / 3) * 3 + col / 3;
 
                if(boxes[boxIndex].find(val) == boxes[boxIndex].end()) {
                    boxes[boxIndex].insert(val);
                } else {
                    return false;
                }
            }
        }
        return true;
    }
};