Why choose the BFS implementation over the DFS here?
Could the wording on the problem be updated to reflect that you don’t just need to change pixels connected to the input that are the same color, but also pixels connected to those pixels that are the same color?
is visited needed if color is changed? we would never insert same r, c to q since getneighbor condition will evaluate to false the second time, right?
You would need the visited set in the case where the replacement color is the same as the original color in [r, c]
true, but we could return immediately if replace == original since there would be nothing to do
Isn’t this drastically easier using a simple DFS algorithm?
DFS approach
def flood_fill(r: int, c: int, replacement: int, image: List[List[int]]) -> List[List[int]]:
num_rows, num_cols = len(image), len(image[0])
color = image[r][c]
def get_neighbors(row, col):
row_delta = [-1, 0, 1, 0]
col_delta = [0, 1, 0, -1]
for i in range(len(row_delta)):
neighbor_row = row + row_delta[i]
neighbor_col = col + col_delta[i]
if 0 <= neighbor_row < num_rows and 0 <= neighbor_col < num_cols:
if image[neighbor_row][neighbor_col] == color:
yield neighbor_row, neighbor_col
def dfs(row, col, visited):
image[row][col] = replacement
visited.add((row, col))
for n_row, n_col in get_neighbors(row, col):
if (n_row, n_col) in visited:
continue
dfs(n_row, n_col, visited)
dfs(r, c, set())
return image
Also the time complexity of either approach is O(M) where M is the number of pixels in the image, since at worst you have to replace every pixel.
Think DFS would be a much better solution here…
def flood_fill(r: int, c: int, replacement: int, image: List[List[int]]) → List[List[int]]:
coord = [r,c]
val = image[r][c]
image[r][c] = replacement
neighbors = get_neighbors(coord, image)
for coord in neighbors:
r,c = coord
if image[r][c] == val:
flood_fill(r, c, replacement, image)
return image
you are welcome
public static List<List<Integer>> floodFill(int r, int c, int replacement, List<List<Integer>> image) {
// WRITE YOUR BRILLIANT CODE HERE
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int target = image.get(r).get(c);
Queue<int[]> q = new LinkedList();
boolean[][] visited = new boolean[image.size()][image.get(0).size()];
q.add(new int[]{r,c});
while(!q.isEmpty())
{
int[] n = q.remove();
for(int[] d:directions)
{
int nr = n[0] + d[0];
int nc = n[1] + d[1];
if(nr < 0 || nc < 0 || nr >= image.size() || nc >= image.get(0).size()
|| image.get(nr).get(nc) != target)
{
continue;
}
if(visited[nr][nc]) continue;
visited[nr][nc] = true;
image.get(nr).set(nc,replacement);
q.add(new int[]{nr,nc});
}
}
return image;
}
Structured Programming JS Solution:
function getMatchingNeighbors(
row,
col,
image,
numRows,
numCols,
initialColor
) {
const DELTA_ROW = [-1, 0, 1, 0];
const DELTA_COL = [0, 1, 0, -1];
const result = [];
for (let i = 0; i < DELTA_ROW.length; i++) {
const neighborRow = row + DELTA_ROW[i];
const neighborCol = col + DELTA_COL[i];
if (
0 <= neighborRow
&& 0 <= neighborCol
&& neighborRow < numRows
&& neighborCol < numCols
&& image[neighborRow][neighborCol] === initialColor
) {
result.push([neighborRow, neighborCol]);
}
}
return result;
}
function floodFill(row, col, replacement, image) {
const numRows = image.length;
const numCols = image[0].length;
const visited = Array.from({ length: numRows }, () => Array(numCols).fill(false));
const queue = [[row, col]];
const initialColor = image[row][col];
image[row][col] = replacement;
visited[row][col] = true;
while (queue.length > 0) {
const [nodeRow, nodeCol] = queue.shift();
for (const neighbor of getMatchingNeighbors(
nodeRow,
nodeCol,
image,
numRows,
numCols,
initialColor
)) {
const [rowIndex, colIndex] = neighbor;
if (!visited[rowIndex][colIndex]) {
image[rowIndex][colIndex] = replacement;
queue.push(neighbor);
visited[rowIndex][colIndex] = true;
}
}
}
return image;
}
DFS can lead to very large stack
BFS + Outer code same. Changed the getNeighbours to also visit diagonal to save potentially 4 unnecessary traversals worst case.
public static List getNeighbours(Coordinate coord, int maxrow, int maxcol, List<List> image, int color) {
List list = new LinkedList<>();
int row = coord.row;
int col = coord.col;
int[] dRow = {-1, 0, 1, 0, -1, 1, -1, -1};
int[] dCol = {0, 1, 0, -1, -1, 1, 1, -1};
for (int i = 0; i < dRow.length; i++) {
int neighbour_row = row + dRow[i];
int neighbour_col = col + dCol[i];
if (0 <= neighbour_row && neighbour_row < maxrow && 0 <= neighbour_col && neighbour_col < maxcol) {
if (image.get(neighbour_row).get(neighbour_col) == color) {
list.add(new Coordinate(neighbour_row, neighbour_col));
}
}
}
return list;
}
May have made an even better optimization. Realized that going diagonal means I would be saving 4 extra nodes and after the first traversal, I would be double adding almost 3 nodes in the getNeighbours every extra traversal.
My changes:
- Boolean visited set is now public and add an additional check next to where we check if image[r][c] == color that checks with the visited set.
Initialization as a public var:
public static boolean[][] visited = new boolean[1][1];
reallocate the array to fit correct dimensions (should be inside bfs):
visited = new boolean[image.size()][image.get(0).size()];
Adjusted conditional check to getNeighbours:
if (image.get(neighbour_row).get(neighbour_col) == color && !visited[neighbour_row][neighbour_col]) {
list.add(new Coordinate(neighbour_row, neighbour_col));
}
Guess I made a mistake. I don’t go diagonal because the flood cannot infect that array index. It can only fill up, left, right, down strictly.
I feel like I’m going crazy trying to understand test case #2. if the input is
1
1
9
4
0 1 6 4
2 3 3 5
3 3 3 3
6 4 3 4
and for some reason this lesson has the rows and columns 1-indexed, we should be replacing the top left most 0 with a 9. There are no adjacent 0s, so that’s it. My code produces the following which seems correct to me
9 1 6 4
2 3 3 5
3 3 3 3
6 4 3 4
but i’m being told that is incorrect and the expected output is
0 1 6 4
2 9 9 5
9 9 9 9
6 4 9 4
which you only get by beginning with r=2, c=2
Sorry for the poor formatting. Fixing in this comment.
Input:
1
1
9
4
0 1 6 4
2 3 3 5
3 3 3 3
6 4 3 4
My output which seems correct to me
9 1 6 4
2 3 3 5
3 3 3 3
6 4 3 4
Expected output
0 1 6 4
2 9 9 5
9 9 9 9
6 4 9 4
@Brandon Ah, I think I see what the problem is. This lesson is not actually 1-indexed but 0th indexed. I think it may seemed to be 1-indexed because of AlgoMonster’s line count to the left of the matrices in the “Explanation” of the question text. [AM team if you’re reading this, maybe yall can remove those line counts]
Concise DFS approach:
def flood_fill(r: int, c: int, replacement: int, image: List[List[int]]) -> List[List[int]]:
old_color = image[r][c]
image[r][c] = replacement
for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nr = r + dr
nc = c + dc
if nr >= 0 and nc >= 0 and nr < len(image) and nc < len(image[0]):
if image[nr][nc] == old_color:
flood_fill(nr, nc, replacement, image)
return image
Don’t think we need to maintain the visited array for this one. Anybody sees any flaws with this solution? Feedback appreciated, thanks a lot!
function floodFill(r, c, replacement, image) {
var originColor = image[r][c];
if(replacement == originColor)
return image;
var numOfRows = image.length;
var numOfCOlumns = image[0].length;
var rowDeltaArray = [-1, 0, 1, 0];
var colDeltaArray = [0, 1, 0, -1];
var queue=[[r,c]];
while(queue.length > 0) {
let [currR, currC] = queue.shift();
image[currR][currC] = replacement;
for(var i = 0 ; i < rowDeltaArray.length; i++) {
var rToAdd = currR + rowDeltaArray[i];
var cToAdd = currC + colDeltaArray[i];
if(rToAdd >= 0 && rToAdd < numOfRows && cToAdd >=0 && cToAdd < numOfCOlumns && image[rToAdd][cToAdd] == originColor) {
queue.push([rToAdd, cToAdd]);
}
}
}
return image;
}