Crack the Backend

Problem Statement

Given an image (2D array of integers), a start pixel (sr, sc), and a color, perform a flood fill: replace the color of the connected component containing (sr, sc) (all pixels 4-directionally connected with the same original color) with color. Return the modified image. If the new color is the same as the original color at (sr, sc), no change is needed (or we must avoid infinite recursion).

Same idea as the "paint bucket" tool: we only spread to neighbors that have the same color as the starting pixel. We can use DFS or BFS from (sr, sc), changing each visited cell to color. If image[sr][sc] == color, we can return immediately to avoid re-processing.

Key Observations

DFS/BFS: Let old = image[sr][sc]. If old == color, return image (nothing to do). Otherwise, from (sr, sc), traverse all 4-directional neighbors that have value old; set each to color and recurse (or enqueue). Mark as filled when we change the value (so we don't revisit).
DFS: at (r,c), set image[r][c]=color; for each of 4 neighbors, if in bounds and image[nr][nc]==old, recurse. BFS: queue (sr,sc), set image[sr][sc]=color; while queue not empty, pop, for each neighbor with old color set and enqueue.

Approach

High-level: old = image[sr][sc]. If old == color return image. DFS(sr, sc): set image[sr][sc] = color; for each 4-directional neighbor in bounds with image[nr][nc] == old, recurse DFS(nr, nc). Return image.

Steps: if image[sr][sc] == color return image. int old = image[sr][sc]. Call dfs(sr, sc) where dfs(r,c) sets image[r][c]=color and recurses on neighbors (in bounds, image[nr][nc]==old). Return image.

Implementation

Java

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

    if (old == color) {
        return image;
    }

    dfs(image, sr, sc, old, color);
    return image;
}

void dfs(int[][] img, int r, int c, int old, int color) {

    if (r<0||r>=img.length||c<0||c>=img[0].length||img[r][c]!=old) {
        return;
    }

    img[r][c] = color;
    dfs(img,r+1,c,old,color); dfs(img,r-1,c,old,color);
    dfs(img,r,c+1,old,color); dfs(img,r,c-1,old,color);
}

Test Cases

Example 1

Input

image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2

Expected

[[2,2,2],[2,2,0],[2,0,1]]

Explanation

Connected (1,1) component becomes 2.

Complexity Analysis

Time: O(m*n).
Space: O(m*n).

Follow-ups

8-direction flood fill.