LeetCode Solutions
733. Flood Fill
Time: $O(n^2)$ Space: $O(n^2)$
class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc,
int newColor) {
dfs(image, sr, sc,
vector<vector<bool>>(image.size(), vector<bool>(image[0].size())),
image[sr][sc], newColor);
return image;
}
private:
void dfs(vector<vector<int>>& image, int i, int j,
vector<vector<bool>>&& seen, int startColor, int newColor) {
if (i < 0 || i == image.size() || j < 0 || j == image[0].size())
return;
if (image[i][j] != startColor || seen[i][j])
return;
image[i][j] = newColor;
seen[i][j] = true;
dfs(image, i + 1, j, move(seen), startColor, newColor);
dfs(image, i - 1, j, move(seen), startColor, newColor);
dfs(image, i, j + 1, move(seen), startColor, newColor);
dfs(image, i, j - 1, move(seen), startColor, newColor);
}
};
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
boolean[][] seen = new boolean[image.length][image[0].length];
dfs(image, sr, sc, seen, image[sr][sc], newColor);
return image;
}
private void dfs(int[][] image, int i, int j, boolean[][] seen, int startColor, int newColor) {
if (i < 0 || i == image.length || j < 0 || j == image[0].length)
return;
if (image[i][j] != startColor || seen[i][j])
return;
image[i][j] = newColor;
seen[i][j] = true;
dfs(image, i + 1, j, seen, startColor, newColor);
dfs(image, i - 1, j, seen, startColor, newColor);
dfs(image, i, j + 1, seen, startColor, newColor);
dfs(image, i, j - 1, seen, startColor, newColor);
}
}
class Solution:
def floodFill(self, image: List[List[int]],
sr: int, sc: int, newColor: int) -> List[List[int]]:
startColor = image[sr][sc]
seen = set()
def dfs(i: int, j: int) -> None:
if i < 0 or i == len(image) or j < 0 or j == len(image[0]):
return
if image[i][j] != startColor or (i, j) in seen:
return
image[i][j] = newColor
seen.add((i, j))
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
dfs(sr, sc)
return image