Solution to LeetCode 116 Populating Next Right Pointers in Each Node, LeetCode 542 01 Matrix, LeetCode 617 Merge Two Binary Trees, LeetCode 695 Max Area of Island, LeetCode 733 Flood Fill, LeetCode 994 Rotting Oranges.
LeetCode 116
Populating Next Right Pointers in Each Node (Medium) [link]
BFS. Time complexity O(n). Space complexity O(n).
"""
# Definition for a Node.
class Node:
def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
self.val = val
self.left = left
self.right = right
self.next = next
"""
class Solution:
def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
if not root: return root
queue = collections.deque([root])
while queue:
n = len(queue)
for i in range(n):
x = queue.popleft()
if i < n-1:
x.next = queue[0]
if x.left:
queue.append(x.left)
if x.right:
queue.append(x.right)
return root
LeetCode 542
01 Matrix (Medium) [link]
Using BFS. Consider all zeros to be a super zero. Time complexity O(nm). Space complexity O(nm).
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
n = len(mat)
m = len(mat[0])
ans = [[0] * m for _ in range(n)]
zeros = [(i, j) for i in range(n) for j in range(m) if mat[i][j] == 0]
queue = collections.deque(zeros)
seen = set(zeros)
while queue:
x,y = queue.popleft()
for (mx, my) in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
if 0 <= mx < n and 0 <= my < m and (mx,my) not in seen:
ans[mx][my] = ans[x][y] + 1
queue.append((mx,my))
seen.add((mx,my))
return ans
LeetCode 617
Merge Two Binary Trees (Easy) [link]
Using DFS (much simpler and easier than BFS). Time complexity O(min(n,m)).
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
if not root1:
return root2
if not root2:
return root1
merged = TreeNode(root1.val + root2.val)
merged.left = self.mergeTrees(root1.left, root2.left)
merged.right = self.mergeTrees(root1.right, root2.right)
return merged
LeetCode 695
Max Area of Island (Medium) [link]
Using BFS. Time complexity O(nm).
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid[0])
ans = 0
for i in range(n):
for j in range(m):
cur = 0
queue = collections.deque([(i,j)])
while queue:
x, y = queue.popleft()
if x < 0 or y < 0 or x == n or y == m or grid[x][y] == 0:
continue
cur += 1
grid[x][y] = 0
for mi, mj in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
queue.append((mi,mj))
ans = max(ans, cur)
return ans
Using DFS. Time complexity O(nm).
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid[0])
cnt_max = 0
def dfs(grid, x, y):
if x < 0 or y < 0 or grid[x][y] == 0:
return 0
cnt = 1
grid[x][y] = 0
for (mx, my) in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
if 0 <= mx < n and 0 <= my < m and grid[mx][my] == 1:
cnt += dfs(grid, mx, my)
return cnt
for i in range(n):
for j in range(m):
cnt_max = max(dfs(grid,i,j), cnt_max)
return cnt_max
LeetCode 733
Flood Fill (Easy) [link]
BFS. Use collections.deque() with popleft and append. Time complexity O(nm). Space complexity O(nm).
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
curColor = image[sr][sc]
if curColor == newColor:
return image
else:
image[sr][sc] = newColor
n = len(image) # rows
m = len(image[0]) # cols
queue = collections.deque([(sr,sc)])
while queue:
x, y = queue.popleft()
for (mx, my) in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
if 0 <= mx < n and 0 <= my < m and image[mx][my] == curColor:
queue.append((mx, my))
image[mx][my] = newColor
return image
DFS. Define recursion function. Time complexity O(nm). Space complexity O(nm).
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
n = len(image) # rows
m = len(image[0]) # cols
curColor = image[sr][sc]
def dfs(x,y):
if image[x][y] == curColor:
image[x][y] = newColor
for (mx, my) in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
if 0 <= mx < n and 0 <= my < m and image[mx][my] == curColor:
dfs(mx, my)
if curColor != newColor:
dfs(sr,sc)
return image
LeetCode 994
Rotting Oranges (Medium) [link]
BFS, similar to LC 542. The difference is that we need to
1 count the minutes by keeping track of tree depth
2 check whether there is 1 remains in the grid
Time complexity O(nm). Space complexity O(nm).
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid[0])
d = 0
rotten = [(i,j,d) for i in range(n) for j in range(m) if grid[i][j] == 2]
seen = set(rotten)
queue = collections.deque(rotten)
cnt = 0
while queue:
x, y, d = queue.popleft()
cnt += 1
for mx, my in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
if 0 <= mx < n and 0 <= my < m and (mx,my) not in seen and grid[mx][my] == 1:
grid[mx][my] = 2
queue.append((mx,my,d+1))
seen.add((mx,my))
if any(1 in row for row in grid):
return -1
return d
