### View *Valid Sudoku* on LeetCode

## Statistics

**Time Spent Coding**

30 minutes

**Time Complexity**

O(n * m) - We must check each cell, meaning we must iterate through each row (n) and each column (m), resulting in the O(n * m) time complexity.

**Space Complexity**

O(n * m) - We store three unique identifiers for each cell, resulting in the O(n * m) space complexity.

The space complexity is not O(n * m * 3) because the increase in space remains quadratic despite the multiplier. Hence, it is not included in the final space complexity.

## Explanation

We iterate through each row, while inside each row, we iterate through each cell.

At each cell, we place the number at that cell into a variable and check if it is a number or an empty space.

- If it is an empty space, we will
`continue`

to the next cell.

If it is a number, place it into three unique string identifiers, one for denoting it and its row, column, and box placements. The identifier to check if the box of the 3x3 grid is valid, is slightly different than the rest. Each box contains 3 rows and 3 columns, meaning each box can be identified by the current rows and columns floor division by 3 `[r//3,c//3]`

, this remaineder is equivelent to the box the number is within.

- If this unique identifier is already within the set, we know this is an invalid sodoku board, so we return
`False`

.

If this unique identifier is not within the set, then add it.

If we exit both for loops and have not returned `False`

, the sodoku board must be valid.

## Data Structure Used

**Hash Table (Set) -** An unordered container of non-repeating values.

**Visual Examples**

An array being transformed into a set, click to view

## Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution:
def isValidSudoku(self, board):
s = set()
for r in range(9):
for c in range(9):
num = board[r][c]
if num == ".": continue
# Create row identifier
check = f"{num} in row # {r}"
# Check identifier
if check in s: return False
s.add(check)
# Create
check = f"{num} in column # {c}"
# Check
if check in s: return False
s.add(check)
# Create
check = f"{num} in box @ {[r//3,c//3]}"
#Check
if check in s: return False
s.add(check)
return True