# [Valid Sudoku](https://leetcode.com/problems/valid-sudoku/)
###### tags: `Leetcode`, `Medium`, `Arrays and Hashing`

## Approach 1 - Using Hashset
* Initialize three dictionaries whose values are sets (for rows, columns and boxes)
* For every cell in the grid, check if it exists in the corresponding row, column and box (defined in the bullet point above)
* If the value in the cell is in any of the visited sets, return False
* Else, continue
* Return True

### Asymptotic Analysis
#### Time Complexity: **O(N²)**
#### Space Complexity: **O(N²)**

## Approach 2 - Using Bitmasking
* Initialize three lists (for rows, columns and boxes)
* For every cell in the grid, check if the bit value at that position in the corresponding row, column and box (defined in the bullet point above) is set to 1
* If the bit value at that position is 1, return False
* Else, continue
* Return True

### Asymptotic Analysis
#### Time Complexity: **O(N²)**
#### Space Complexity: **O(N)**

## Code

from collections import defaultdict
from typing import List


class ValidSudoku:
    # Using hashset
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # Initialize rows, columns and boxes
        rows = defaultdict(set)
        columns = defaultdict(set)
        boxes = defaultdict(set)

        # Iterate through the cells to check if the value is present in the
        # sets rows, columns and boxes.
        for row in range(9):
            for column in range(9):
                current = board[row][column]
                if current == ".":
                    continue

                if (current in rows[row] or
                        current in columns[column] or
                        current in boxes[(row // 3, column // 3)]):
                    return False

                rows[row].add(current)
                columns[column].add(current)
                boxes[(row // 3, column // 3)].add(current)
        return True

    def isValidSudokuUsingBitManipulation(self, board: List[List[str]]) -> bool:
        rows = [0] * 9
        columns = [0] * 9
        boxes = [0] * 9

        for row in range(9):
            for column in range(9):
                current = board[row][column]
                if current == '.':
                    continue
                pos = int(current) - 1
                if (rows[row] & (1 << pos) or
                        columns[column] & (1 << pos) or
                        boxes[(row // 3) * 3 + (column // 3)] & (1 << pos)):
                    return False
                rows[row] |= (1 << pos)
                columns[column] |= (1 << pos)
                boxes[(row // 3) * 3 + (column // 3)] |= (1 << pos)
        return True


obj = ValidSudoku()
board = [["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"]]

board1 = [["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(obj.isValidSudoku(board1))
print(obj.isValidSudokuUsingBitManipulation(board1))