LeetCode-python/problem_036.py at main · saitejamanchi/LeetCode-python · GitHub

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""
Problem Statement: https://leetcode.com/problems/valid-sudoku/

Solution: We first check row by row if there is any duplicate element.
Then we check each column. At the end we check each 3*3 square for duplicate elements.
If we don't find any duplicates then it is a Valid sudoku, Otherwise not.

Time Complexity: O(1) as there is no variamce in the input.

Space Complexity: O(1) as we're creating a set that is at most of size 9.
"""
classSolution:
defisValidSudoku(self, board: List[List[str]]) ->bool:
curr_ele=set()
foriinrange(9):
forjinrange(9):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()

curr_ele=set()

foriinrange(9):
forjinrange(9):
ifboard[j][i] incurr_ele:
returnFalse
ifboard[j][i] !=".":
curr_ele.add(board[j][i])
curr_ele=set()

curr_ele=set()

sub_matrix_start_inds= [0, 3, 6]

forh_startinsub_matrix_start_inds:
forv_startinsub_matrix_start_inds:
foriinrange(h_start, h_start+3):
forjinrange(v_start, v_start+3):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()
returnTrue
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""
Problem Statement: https://leetcode.com/problems/valid-sudoku/

Solution: We first check row by row if there is any duplicate element.
Then we check each column. At the end we check each 3*3 square for duplicate elements.
If we don't find any duplicates then it is a Valid sudoku, Otherwise not.

Time Complexity: O(1) as there is no variamce in the input.

Space Complexity: O(1) as we're creating a set that is at most of size 9.
"""
classSolution:
defisValidSudoku(self, board: List[List[str]]) ->bool:
curr_ele=set()
foriinrange(9):
forjinrange(9):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()

curr_ele=set()

foriinrange(9):
forjinrange(9):
ifboard[j][i] incurr_ele:
returnFalse
ifboard[j][i] !=".":
curr_ele.add(board[j][i])
curr_ele=set()

curr_ele=set()

sub_matrix_start_inds= [0, 3, 6]

forh_startinsub_matrix_start_inds:
forv_startinsub_matrix_start_inds:
foriinrange(h_start, h_start+3):
forjinrange(v_start, v_start+3):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()
returnTrue
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""
Problem Statement: https://leetcode.com/problems/valid-sudoku/

Solution: We first check row by row if there is any duplicate element.
Then we check each column. At the end we check each 3*3 square for duplicate elements.
If we don't find any duplicates then it is a Valid sudoku, Otherwise not.

Time Complexity: O(1) as there is no variamce in the input.

Space Complexity: O(1) as we're creating a set that is at most of size 9.
"""
classSolution:
defisValidSudoku(self, board: List[List[str]]) ->bool:
curr_ele=set()
foriinrange(9):
forjinrange(9):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()

curr_ele=set()

foriinrange(9):
forjinrange(9):
ifboard[j][i] incurr_ele:
returnFalse
ifboard[j][i] !=".":
curr_ele.add(board[j][i])
curr_ele=set()

curr_ele=set()

sub_matrix_start_inds= [0, 3, 6]

forh_startinsub_matrix_start_inds:
forv_startinsub_matrix_start_inds:
foriinrange(h_start, h_start+3):
forjinrange(v_start, v_start+3):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()
returnTrue
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""
Problem Statement: https://leetcode.com/problems/valid-sudoku/

Solution: We first check row by row if there is any duplicate element.
Then we check each column. At the end we check each 3*3 square for duplicate elements.
If we don't find any duplicates then it is a Valid sudoku, Otherwise not.

Time Complexity: O(1) as there is no variamce in the input.

Space Complexity: O(1) as we're creating a set that is at most of size 9.
"""
classSolution:
defisValidSudoku(self, board: List[List[str]]) ->bool:
curr_ele=set()
foriinrange(9):
forjinrange(9):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()

curr_ele=set()

foriinrange(9):
forjinrange(9):
ifboard[j][i] incurr_ele:
returnFalse
ifboard[j][i] !=".":
curr_ele.add(board[j][i])
curr_ele=set()

curr_ele=set()

sub_matrix_start_inds= [0, 3, 6]

forh_startinsub_matrix_start_inds:
forv_startinsub_matrix_start_inds:
foriinrange(h_start, h_start+3):
forjinrange(v_start, v_start+3):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()
returnTrue
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""
Problem Statement: https://leetcode.com/problems/valid-sudoku/

Solution: We first check row by row if there is any duplicate element.
Then we check each column. At the end we check each 3*3 square for duplicate elements.
If we don't find any duplicates then it is a Valid sudoku, Otherwise not.

Time Complexity: O(1) as there is no variamce in the input.

Space Complexity: O(1) as we're creating a set that is at most of size 9.
"""
classSolution:
defisValidSudoku(self, board: List[List[str]]) ->bool:
curr_ele=set()
foriinrange(9):
forjinrange(9):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()

curr_ele=set()

foriinrange(9):
forjinrange(9):
ifboard[j][i] incurr_ele:
returnFalse
ifboard[j][i] !=".":
curr_ele.add(board[j][i])
curr_ele=set()

curr_ele=set()

sub_matrix_start_inds= [0, 3, 6]

forh_startinsub_matrix_start_inds:
forv_startinsub_matrix_start_inds:
foriinrange(h_start, h_start+3):
forjinrange(v_start, v_start+3):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()
returnTrue
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""
Problem Statement: https://leetcode.com/problems/valid-sudoku/

Solution: We first check row by row if there is any duplicate element.
Then we check each column. At the end we check each 3*3 square for duplicate elements.
If we don't find any duplicates then it is a Valid sudoku, Otherwise not.

Time Complexity: O(1) as there is no variamce in the input.

Space Complexity: O(1) as we're creating a set that is at most of size 9.
"""
classSolution:
defisValidSudoku(self, board: List[List[str]]) ->bool:
curr_ele=set()
foriinrange(9):
forjinrange(9):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()

curr_ele=set()

foriinrange(9):
forjinrange(9):
ifboard[j][i] incurr_ele:
returnFalse
ifboard[j][i] !=".":
curr_ele.add(board[j][i])
curr_ele=set()

curr_ele=set()

sub_matrix_start_inds= [0, 3, 6]

forh_startinsub_matrix_start_inds:
forv_startinsub_matrix_start_inds:
foriinrange(h_start, h_start+3):
forjinrange(v_start, v_start+3):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()
returnTrue
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""
Problem Statement: https://leetcode.com/problems/valid-sudoku/

Solution: We first check row by row if there is any duplicate element.
Then we check each column. At the end we check each 3*3 square for duplicate elements.
If we don't find any duplicates then it is a Valid sudoku, Otherwise not.

Time Complexity: O(1) as there is no variamce in the input.

Space Complexity: O(1) as we're creating a set that is at most of size 9.
"""
classSolution:
defisValidSudoku(self, board: List[List[str]]) ->bool:
curr_ele=set()
foriinrange(9):
forjinrange(9):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()

curr_ele=set()

foriinrange(9):
forjinrange(9):
ifboard[j][i] incurr_ele:
returnFalse
ifboard[j][i] !=".":
curr_ele.add(board[j][i])
curr_ele=set()

curr_ele=set()

sub_matrix_start_inds= [0, 3, 6]

forh_startinsub_matrix_start_inds:
forv_startinsub_matrix_start_inds:
foriinrange(h_start, h_start+3):
forjinrange(v_start, v_start+3):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()
returnTrue
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
"""
Problem Statement: https://leetcode.com/problems/valid-sudoku/

Solution: We first check row by row if there is any duplicate element.
Then we check each column. At the end we check each 3*3 square for duplicate elements.
If we don't find any duplicates then it is a Valid sudoku, Otherwise not.

Time Complexity: O(1) as there is no variamce in the input.

Space Complexity: O(1) as we're creating a set that is at most of size 9.
"""
classSolution:
defisValidSudoku(self, board: List[List[str]]) ->bool:
curr_ele=set()
foriinrange(9):
forjinrange(9):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()

curr_ele=set()

foriinrange(9):
forjinrange(9):
ifboard[j][i] incurr_ele:
returnFalse
ifboard[j][i] !=".":
curr_ele.add(board[j][i])
curr_ele=set()

curr_ele=set()

sub_matrix_start_inds= [0, 3, 6]

forh_startinsub_matrix_start_inds:
forv_startinsub_matrix_start_inds:
foriinrange(h_start, h_start+3):
forjinrange(v_start, v_start+3):
ifboard[i][j] incurr_ele:
returnFalse
ifboard[i][j] !=".":
curr_ele.add(board[i][j])
curr_ele=set()
returnTrue