-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathValidSudoku.py
185 lines (161 loc) · 6.68 KB
/
ValidSudoku.py
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
# Source : https://leetcode.com/problems/valid-sudoku
# Author : Hamza Mogni
# Date : 2022-01-20
#####################################################################################################
#
# Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to
# the following rules:
#
# Each row must contain the digits 1-9 without repetition.
# Each column must contain the digits 1-9 without repetition.
# Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
#
# Note:
#
# A Sudoku board (partially filled) could be valid but is not necessarily solvable.
# Only the filled cells need to be validated according to the mentioned rules.
#
# Example 1:
#
# Input: board =
# [["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"]]
# Output: true
#
# Example 2:
#
# Input: 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"]]
# Output: false
# Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since
# there are two 8's in the top left 3x3 sub-box, it is invalid.
#
# Constraints:
#
# board.length == 9
# board[i].length == 9
# board[i][j] is a digit 1-9 or '.'.
#####################################################################################################
from typing import List
class Solution:
# time: o(9x9)
# Space: o(9x9x3)
def isValidSudoku(self, board: List[List[str]]) -> bool:
"""
My first dumb solution:
- I make 3 passes, and on each one I use a hashmap
to keep track of the numbers I have already visited
- The first pass checks each line if it is valid
- The second pass checks each column if it is valid
- The third pass checks each sub box of (3x3) if it is valid
- The time complexity of this is o(9x9x3x3)
- Space complexity though is o(9)
Code
~~~~~~~~~~
# First pass
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
for line in board:
visited = set()
for char in line:
if char not in visited:
if char != ".":
visited.add(char)
else:
return False
# Second pass
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
columns = len(board[0])
for column in range(columns):
visited = set()
for line in board:
char = line[column]
if char not in visited:
if char != ".":
visited.add(char)
else:
return False
# Third pass
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
indices_x = [(0, 2), (3, 5), (6, 8)]
indices_y = [(0, 2), (3, 5), (6, 8)]
for x in indices_x:
for y in indices_y:
visited = set()
for i in range(x[0], x[1]+1):
for j in range(y[0], y[1]+1):
char = board[j][i]
if char not in visited:
if char != ".":
visited.add(char)
else:
return False
return True
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
After making one little observation, I have noticed I could hugely improve this
and make it converge in one pass over the board.
The idea is to use one single hashmap, in which we store tuples,
those tuples contains each number we visit and its position:
for each number, we store 3 tuples in the hashmap:
- (line_position, number)
- (number, column_position)
- (line_position / 3, column_position / 3, number)
- the first tuple stores the number and its position alongside the lines,
- the second stores the number alongside the columns (we flip the ordering to avoid
duplicates between lines and columns)
- the third one stores the number and the coordinates of the sub-box.
as soon as we find a tuple that already exists on the hashmap we return False
otherwise the board is valid.
Time: o(9x9)
Space: o(9x9x3)
"""
visited = set()
for i in range(0, 9):
for j in range(0, 9):
current = board[i][j]
if current != ".":
if (i, current) in visited or (current, j) in visited or (i // 3, j // 3, current) in visited:
return False
visited.add((i, current))
visited.add((current, j))
visited.add((i // 3, j // 3, current))
return True
s = Solution()
test1 = s.isValidSudoku([
["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"]
])
test2 = s.isValidSudoku([
[".", ".", ".", ".", "5", ".", ".", "1", "."],
[".", "4", ".", "3", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", "3", ".", ".", "1"],
["8", ".", ".", ".", ".", ".", ".", "2", "."],
[".", ".", "2", ".", "7", ".", ".", ".", "."],
[".", "1", "5", ".", ".", ".", ".", ".", "."],
[".", ".", ".", ".", ".", "2", ".", ".", "."],
[".", "2", ".", "9", ".", ".", ".", ".", "."],
[".", ".", "4", ".", ".", ".", ".", ".", "."]
])
assert test1 == True
assert test2 == False