733. Flood Fill

二刷 06/2022

Version #2 BFS

Time O(MN)

Space O(MN)

Runtime: 2 ms, faster than 33.39% of Java online submissions for Flood Fill.

Memory Usage: 48 MB, less than 55.82% of Java online submissions for Flood Fill.

class Solution {

    private static int[] dx = new int[]{1, 0, -1, 0};

    private static int[] dy = new int[]{0, -1, 0, 1};

    public int[][] floodFill(int[][] image, int sr, int sc, int color) {

        int originalColor = image[sr][sc];

        if (originalColor == color) {

            return image;

        }

        int rows = image.length;

        int cols = image[0].length;

        Queue<int[]> que = new ArrayDeque<>();

        que.offer(new int[]{sr, sc});

        image[sr][sc] = color;

        while (!que.isEmpty()) {

            int[] curr = que.poll();

            for (int i = 0; i < 4; i++) {

                int ny = curr[0] + dy[i];

                int nx = curr[1] + dx[i];

                if (ny < 0 || nx < 0 || ny >= rows || nx >= cols || image[ny][nx] != originalColor) {

                    continue;

                }

                image[ny][nx] = color;

                que.offer(new int[]{ny, nx});

            }

        }

        return image;

    }

}

一刷

Version #1 DFS
trap -> when newColor == image[sr][sc] it will lead to a stackoverflow
So we should return directly when this is satisfied

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        if (newColor == image[sr][sc]) return image;
dfs(image, sr, sc, newColor);
return image;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private void dfs(int[][] image, int y, int x, int newColor) {
int color =image[y][x];
image[y][x] = newColor;
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (nx >= 0 && nx < image[0].length && ny >= 0 && ny < image.length && image[ny][nx] == color) {
dfs(image, ny, nx, newColor);
}
}
}
}