2257. Count Unguarded Cells in the Grid | 1709
I can’t afford my CTO to discover my leetcode posts. I had to privatize my repo for now.
My initial thoughts TLEs. This is essentially a O(m*n*(m+n)) because worst case scenario a corridor can be scanned n times. Consider m = 1, n = 100000 and there is only a guard at (0, 0) and a wall at (0, 1).
1class Solution:
2 def countUnguarded(
3 self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]
4 ) -> int:
5 # intuition: start from each empty cell
6 # if guarded, skip; else:
7 # for each direction, track path
8 # if hits Guard, mark all path cell guarded
9
10 # guards = 1, wall = 2; guarded = 0, unguarded = -1
11 grid = [[-1 for _ in range(n)] for _ in range(m)]
12 for x, y in guards:
13 grid[x][y] = 1
14 for x, y in walls:
15 grid[x][y] = 2
16
17 for i in range(m):
18 for j in range(n):
19 if grid[i][j] == -1:
20 # north
21 path = [[i, j]]
22 guarded = False
23 ti, tj = i - 1, j
24 while ti > -1:
25 cell = grid[ti][tj]
26 if cell == 2:
27 break
28 elif cell == 1:
29 guarded = True
30 break
31 path.append([ti, tj])
32 ti -= 1
33 if guarded:
34 for x, y in path:
35 grid[x][y] = 0
36
37 # east
38 path = [[i, j]]
39 guarded = False
40 ti, tj = i, j + 1
41 while tj < n:
42 cell = grid[ti][tj]
43 if cell == 2:
44 break
45 elif cell == 1:
46 guarded = True
47 break
48 path.append([ti, tj])
49 tj += 1
50 if guarded:
51 for x, y in path:
52 grid[x][y] = 0
53
54 # south
55 path = [[i, j]]
56 guarded = False
57 ti, tj = i + 1, j
58 while ti < m:
59 cell = grid[ti][tj]
60 if cell == 2:
61 break
62 elif cell == 1:
63 guarded = True
64 break
65 path.append([ti, tj])
66 ti += 1
67 if guarded:
68 for x, y in path:
69 grid[x][y] = 0
70
71 # west
72 path = [[i, j]]
73 guarded = False
74 ti, tj = i, j - 1
75 while tj > -1:
76 cell = grid[ti][tj]
77 if cell == 2:
78 break
79 elif cell == 1:
80 guarded = True
81 break
82 path.append([ti, tj])
83 tj -= 1
84 if guarded:
85 for x, y in path:
86 grid[x][y] = 0
87
88 result = 0
89 for i in range(m):
90 for j in range(n):
91 if grid[i][j] == -1:
92 result += 1
93
94 return result
Consulted for a hint: is it possible to scan each row and col only once.
1class Solution:
2 def countUnguarded(
3 self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]
4 ) -> int:
5 # intuition:
6 # for each row/col, keep path
7 # go until hits wall, if ever seen guard, mark all empty cells guarded
8 # this trims the runtime to O(m*n)
9 UNGUARDED = 0
10 GUARDED = 1
11 GUARD = 2
12 WALL = 3
13
14 grid = [[UNGUARDED for _ in range(n)] for _ in range(m)]
15 for x, y in guards:
16 grid[x][y] = GUARD
17 for x, y in walls:
18 grid[x][y] = WALL
19
20 for i in range(m):
21 j = 0
22 path = []
23 seen_guard = False
24 while j < n:
25 if grid[i][j] == UNGUARDED:
26 path.append([i, j])
27 elif grid[i][j] == GUARD:
28 seen_guard = True
29 elif grid[i][j] == WALL:
30 if seen_guard:
31 for x, y in path:
32 grid[x][y] = GUARDED
33 seen_guard = False
34 if path:
35 path = []
36 j += 1
37 # remainings till the end
38 if seen_guard:
39 for x, y in path:
40 grid[x][y] = GUARDED
41
42 for j in range(n):
43 i = 0
44 path = []
45 seen_guard = False
46 while i < m:
47 if grid[i][j] == UNGUARDED:
48 path.append([i, j])
49 elif grid[i][j] == GUARD:
50 seen_guard = True
51 elif grid[i][j] == WALL:
52 if seen_guard:
53 for x, y in path:
54 grid[x][y] = GUARDED
55 seen_guard = False
56 if path:
57 path = []
58 i += 1
59 # remainings till the end
60 if seen_guard:
61 for x, y in path:
62 grid[x][y] = GUARDED
63
64 result = 0
65 for i in range(m):
66 for j in range(n):
67 if grid[i][j] == UNGUARDED:
68 result += 1
69
70 return result
This is passing, but there is the “optimal” solution, which is to do a O(4mn) - like casting a flashlight from each direction, marking all cells after seeing a guard guarded and continue when hit a wall:
1class Solution:
2 def countUnguarded(
3 self, m: int, n: int, guards: List[List[int]], walls: List[List[int]]
4 ) -> int:
5 # optimal: cast in 4 directions
6 UNGUARDED = 0
7 GUARDED = 1
8 GUARD = 2
9 WALL = 3
10
11 grid = [[0 for _ in range(n)] for _ in range(m)]
12
13 for i, j in guards:
14 grid[i][j] = GUARD
15 for i, j in walls:
16 grid[i][j] = WALL
17
18 # east
19 for i in range(m):
20 seen = False
21 for j in range(n):
22 if grid[i][j] == WALL:
23 seen = False
24 elif grid[i][j] == GUARD:
25 seen = True
26 elif grid[i][j] == UNGUARDED and seen:
27 grid[i][j] = GUARDED
28
29 # south
30 for j in range(n):
31 seen = False
32 for i in range(m):
33 if grid[i][j] == WALL:
34 seen = False
35 elif grid[i][j] == GUARD:
36 seen = True
37 elif grid[i][j] == UNGUARDED and seen:
38 grid[i][j] = GUARDED
39
40 # west
41 for i in range(m):
42 seen = False
43 for j in range(n - 1, -1, -1):
44 if grid[i][j] == WALL:
45 seen = False
46 elif grid[i][j] == GUARD:
47 seen = True
48 elif grid[i][j] == UNGUARDED and seen:
49 grid[i][j] = GUARDED
50
51 # north
52 for j in range(n):
53 seen = False
54 for i in range(m - 1, -1, -1):
55 if grid[i][j] == WALL:
56 seen = False
57 elif grid[i][j] == GUARD:
58 seen = True
59 elif grid[i][j] == UNGUARDED and seen:
60 grid[i][j] = GUARDED
61
62 result = 0
63 for i in range(m):
64 for j in range(n):
65 if grid[i][j] == UNGUARDED:
66 result += 1
67
68 return result
#Array #Matrix #Simulation #Python