DSA-095 · FOCUSED PRACTICE

Flood Fill

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 93757 deterministic checks. Learner drafts are not executed.

Understand the problem

Recolor exactly the orthogonally connected original-color component containing a seed coordinate. Mutate the image in place and return the same outer array.

The outer array is nonnull and rectangular with nonnull rows, at most 100,000 rows and 100,000 cells. Size bounds are preconditions; null outer input throws NullPointerException and null/ragged rows throw IllegalArgumentException. A valid seed is required, so an empty or zero-column image has no valid call.
Image cells and replacement color may be any int. The seed must be in bounds; invalid seed throws IllegalArgumentException. Rows must be distinct objects: reject aliases, ragged/null rows and invalid seeds before any mutation, even if replacement equals the seed color.
Preserve the outer array and every original row reference. Only cells connected to the seed through its original color may change. If replacement equals original, return the validated image unchanged; no recursion or separate visited matrix is required.

Examples

Input: image=[[1,1,0],[1,0,0],[2,2,1]], seed=(0,0), color=7
Output: same image; [[7,7,0],[7,0,0],[2,2,1]]
The disconnected bottom-right 1 is outside the seed component.
Input: image=[[MIN,0],[MIN,MAX]], seed=(0,0), color=MIN
Output: same unchanged image
The no-op guard is essential when color would otherwise fail to distinguish discovered cells.

Before you start

Connected components and mutation ownership
Discovery marking before enqueue and same-value no-op guards

Recognize the structure

A fill is a component update, not a global replacement of all equal values. Because replacement differs from original, writing the replacement can serve as the visited mark and remove the need for a second cell matrix.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 171/20,000 characters

Self-review

Can I explain why the new color acts as discovery state?Can I identify the aliasing failure of an otherwise correct flood traversal?Can I preserve the same outer and row identities?

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

Which equal-colored cells are actually connected to the seed?

Hint 2

A different replacement color can act as the visited mark.

Hint 3

Validate ownership, guard equal colors, then paint each coordinate before enqueueing it.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Compute a synchronous membership closure before painting

Mark only the seed in a boolean selected matrix. Repeatedly scan original-color cells and copy in any cell adjacent to the previous round’s selected set, stopping at a fixed point. Then paint selected cells. This makes original-component membership explicit but can rescan the whole image for every extra path step.

Improve the baseline

Validate row ownership and seed first

An in-place cell write on an aliased row could change a different coordinate outside the component. Validate distinct row objects and the complete shape before reading or painting the seed.

Handle equal colors before traversal

If original==color, return unchanged. Otherwise a painted cell immediately fails the original-color eligibility test and cannot be rediscovered.

Paint before enqueueing

Paint the seed, then repeatedly pop coordinates and paint/queue each in-bounds original-color neighbor. The source itself records discovery; return the same image reference.

Why it is correct

Eligible-component invariant

Every queued cell belonged to the seed’s original-color component and has already been painted. A new eligible neighbor extends a valid original-color path from the seed.

No duplicate ownership

Replacement differs from original. Once a coordinate is painted it fails all later original-color checks, so it is enqueued at most once without a separate visited matrix.

Exact mutation and completion

Every original-color path from the seed is eventually followed, so all and only that component is painted. Distinct source rows ensure a coordinate write cannot mutate an unrelated coordinate through aliasing.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
    private static int validate(int[][] image,int sr,int sc) {
        Objects.requireNonNull(image,"image");int columns=image.length==0?0:image[0]==null?-1:image[0].length;
        Set<int[]> rows=Collections.newSetFromMap(new IdentityHashMap<>());
        for(int[] row:image)if(row==null||row.length!=columns||!rows.add(row))throw new IllegalArgumentException("nonrectangular or aliased rows");
        if(sr<0||sr>=image.length||sc<0||sc>=columns)throw new IllegalArgumentException("seed outside image");
        return columns;
    }
    public static int[][] fill(int[][] image,int sr,int sc,int color) {
        int columns=validate(image,sr,sc),original=image[sr][sc];
        if(original==color)return image;
        ArrayDeque<int[]> queue=new ArrayDeque<>();
        image[sr][sc]=color;queue.addLast(new int[]{sr,sc});
        while(!queue.isEmpty()) {
            int[] cell=queue.removeFirst();
            for(int[] d:DIRECTIONS) {
                int nr=cell[0]+d[0],nc=cell[1]+d[1];
                if(nr<0||nr>=image.length||nc<0||nc>=columns||image[nr][nc]!=original)continue;
                image[nr][nc]=color;queue.addLast(new int[]{nr,nc});
            }
        }
        return image;
    }
    public static int[][] baseline(int[][] image,int sr,int sc,int color) {
        int columns=validate(image,sr,sc),original=image[sr][sc];if(original==color)return image;
        boolean[][] selected=new boolean[image.length][columns];selected[sr][sc]=true;
        boolean changed;
        do {
            changed=false;boolean[][] next=new boolean[image.length][];for(int r=0;r<image.length;r++)next[r]=selected[r].clone();
            for(int r=0;r<image.length;r++)for(int c=0;c<columns;c++)if(image[r][c]==original&&!selected[r][c])for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<image.length&&nc>=0&&nc<columns&&selected[nr][nc]){next[r][c]=true;changed=true;break;}}
            selected=next;
        }while(changed);
        for(int r=0;r<image.length;r++)for(int c=0;c<columns;c++)if(selected[r][c])image[r][c]=color;
        return image;
    }
}

Read the meaningful blocks

Save the original color before any write

Neighbor eligibility always uses the original value, not whichever value the current cell now holds.

Same-color return still validates ownership

Invalid aliases must not be conditionally accepted merely because one requested color would be a no-op.

Output reuse is explicit

Returning a copy would violate the same-outer contract; replacing row arrays would also violate identity preservation.

Complexity

For R rows and A cells in the changed component, main time is O(R+A): shape/alias validation checks rows but arbitrary int cell values need no full scan. Auxiliary storage is O(R+A) for the row-identity set and queue, excluding the reused image. A validated same-color call takes O(R) time/space for validation and allocates no traversal queue.

For B cells in a valid nonempty image, the synchronous baseline can take O(B²) time with O(B) membership matrices; row validation adds O(R), with R<=B. Its rounds use copied membership, so the explanation does not hide within-round cascades.

Exact-state walkthroughs

Reveal normal and boundary traces

Only the original seed component is painted

Input: {"image":[[1,1,0],[1,0,0],[2,2,1]],"sr":0,"sc":0,"color":7} · Mutated image / thrown outcome: [[7,7,0],[7,0,0],[2,2,1]]

Step 1 of 7: Recolor the seed as its discovery mark.

New color differs from original; recolored cells cannot pass the original-color neighbor test again.

Flood fill — replacement color owns discovery

Phase: seed.

Current mutable grid

710

100

221

Coordinate queue — front at left; already claimed

(0, 0)

Original seed color: 1. Replacement: 7. Recolored coordinates: 1. Recoloring before enqueueing provides ownership when these colors differ. The same-color case returns after validation. Java preserves the outer array and distinct row identities.

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
source	`[[1,1,0],[1,0,0],[2,2,1]]`
grid	`[[7,1,0],[1,0,0],[2,2,1]]`
queue	`[[0,0]]`
sr	`0`
sc	`0`
color	`7`
original	`1`
recolored	`[[0,0]]`
phase	`"seed"`
current	`[0,0]`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
 4     private static int validate(int[][] image,int sr,int sc) {
 5         Objects.requireNonNull(image,"image");int columns=image.length==0?0:image[0]==null?-1:image[0].length;
 6         Set<int[]> rows=Collections.newSetFromMap(new IdentityHashMap<>());
 7         for(int[] row:image)if(row==null||row.length!=columns||!rows.add(row))throw new IllegalArgumentException("nonrectangular or aliased rows");
 8         if(sr<0||sr>=image.length||sc<0||sc>=columns)throw new IllegalArgumentException("seed outside image");
 9         return columns;
10     }
11     public static int[][] fill(int[][] image,int sr,int sc,int color) {
12         int columns=validate(image,sr,sc),original=image[sr][sc];
13         if(original==color)return image;
14         ArrayDeque<int[]> queue=new ArrayDeque<>();
15         image[sr][sc]=color;queue.addLast(new int[]{sr,sc});
16         while(!queue.isEmpty()) {
17             int[] cell=queue.removeFirst();
18             for(int[] d:DIRECTIONS) {
19                 int nr=cell[0]+d[0],nc=cell[1]+d[1];
20                 if(nr<0||nr>=image.length||nc<0||nc>=columns||image[nr][nc]!=original)continue;
21                 image[nr][nc]=color;queue.addLast(new int[]{nr,nc});
22             }
23         }
24         return image;
25     }
26     public static int[][] baseline(int[][] image,int sr,int sc,int color) {
27         int columns=validate(image,sr,sc),original=image[sr][sc];if(original==color)return image;
28         boolean[][] selected=new boolean[image.length][columns];selected[sr][sc]=true;
29         boolean changed;
30         do {
31             changed=false;boolean[][] next=new boolean[image.length][];for(int r=0;r<image.length;r++)next[r]=selected[r].clone();
32             for(int r=0;r<image.length;r++)for(int c=0;c<columns;c++)if(image[r][c]==original&&!selected[r][c])for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<image.length&&nc>=0&&nc<columns&&selected[nr][nc]){next[r][c]=true;changed=true;break;}}
33             selected=next;
34         }while(changed);
35         for(int r=0;r<image.length;r++)for(int c=0;c<columns;c++)if(selected[r][c])image[r][c]=color;
36         return image;
37     }
38 }
39

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Recolor the seed as its discovery mark.
New color differs from original; recolored cells cannot pass the original-color neighbor test again.
source
[[1,1,0],[1,0,0],[2,2,1]]
grid
[[7,1,0],[1,0,0],[2,2,1]]
queue
[[0,0]]
sr
0
sc
0
color
7
original
1
recolored
[[0,0]]
phase
"seed"
current
[0,0]
Expand a discovered coordinate.
The queue stores only original-component coordinates; recolored is teaching history, not a Java visited matrix.
source
[[1,1,0],[1,0,0],[2,2,1]]
grid
[[7,1,0],[1,0,0],[2,2,1]]
queue
[]
sr
0
sc
0
color
7
original
1
recolored
[[0,0]]
phase
"visit"
current
[0,0]
Recolor one original-color neighbor before enqueueing.
Only the seed’s original-color component changes. Cells already equal to the new color do not become new traversal owners.
source
[[1,1,0],[1,0,0],[2,2,1]]
grid
[[7,7,0],[1,0,0],[2,2,1]]
queue
[[0,1]]
sr
0
sc
0
color
7
original
1
recolored
[[0,0],[0,1]]
phase
"claim"
current
[0,0]
claimed
[0,1]
Recolor one original-color neighbor before enqueueing.
Only the seed’s original-color component changes. Cells already equal to the new color do not become new traversal owners.
source
[[1,1,0],[1,0,0],[2,2,1]]
grid
[[7,7,0],[7,0,0],[2,2,1]]
queue
[[0,1],[1,0]]
sr
0
sc
0
color
7
original
1
recolored
[[0,0],[0,1],[1,0]]
phase
"claim"
current
[0,0]
claimed
[1,0]
Expand a discovered coordinate.
The queue stores only original-component coordinates; recolored is teaching history, not a Java visited matrix.
source
[[1,1,0],[1,0,0],[2,2,1]]
grid
[[7,7,0],[7,0,0],[2,2,1]]
queue
[[1,0]]
sr
0
sc
0
color
7
original
1
recolored
[[0,0],[0,1],[1,0]]
phase
"visit"
current
[0,1]
Expand a discovered coordinate.
The queue stores only original-component coordinates; recolored is teaching history, not a Java visited matrix.
source
[[1,1,0],[1,0,0],[2,2,1]]
grid
[[7,7,0],[7,0,0],[2,2,1]]
queue
[]
sr
0
sc
0
color
7
original
1
recolored
[[0,0],[0,1],[1,0]]
phase
"visit"
current
[1,0]
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
[[7,7,0],[7,0,0],[2,2,1]]

Same-color validated no-op

Input: {"image":[[-2147483648,0],[-2147483648,2147483647]],"sr":0,"sc":0,"color":-2147483648} · Mutated image / thrown outcome: [[-2147483648,0],[-2147483648,2147483647]]

Step 1 of 2: A same-color request is a validated no-op.

The guard prevents the replacement color from failing to distinguish discovered cells. Row-alias validation still runs before this return.

Flood fill — replacement color owns discovery

Phase: same-color.

Current mutable grid

MIN0

MINMAX

MIN = −2,147,483,648; MAX = 2,147,483,647. Their meaning follows this problem’s legend.

Coordinate queue — front at left; already claimed

Empty.

Original seed color: -2147483648. Replacement: -2147483648. Recolored coordinates: 0. Recoloring before enqueueing provides ownership when these colors differ. The same-color case returns after validation. Java preserves the outer array and distinct row identities.

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
source	`[[-2147483648,0],[-2147483648,2147483647]]`
grid	`[[-2147483648,0],[-2147483648,2147483647]]`
queue	`[]`
sr	`0`
sc	`0`
color	`-2147483648`
original	`-2147483648`
recolored	`[]`
phase	`"same-color"`
current	`[0,0]`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
 4     private static int validate(int[][] image,int sr,int sc) {
 5         Objects.requireNonNull(image,"image");int columns=image.length==0?0:image[0]==null?-1:image[0].length;
 6         Set<int[]> rows=Collections.newSetFromMap(new IdentityHashMap<>());
 7         for(int[] row:image)if(row==null||row.length!=columns||!rows.add(row))throw new IllegalArgumentException("nonrectangular or aliased rows");
 8         if(sr<0||sr>=image.length||sc<0||sc>=columns)throw new IllegalArgumentException("seed outside image");
 9         return columns;
10     }
11     public static int[][] fill(int[][] image,int sr,int sc,int color) {
12         int columns=validate(image,sr,sc),original=image[sr][sc];
13         if(original==color)return image;
14         ArrayDeque<int[]> queue=new ArrayDeque<>();
15         image[sr][sc]=color;queue.addLast(new int[]{sr,sc});
16         while(!queue.isEmpty()) {
17             int[] cell=queue.removeFirst();
18             for(int[] d:DIRECTIONS) {
19                 int nr=cell[0]+d[0],nc=cell[1]+d[1];
20                 if(nr<0||nr>=image.length||nc<0||nc>=columns||image[nr][nc]!=original)continue;
21                 image[nr][nc]=color;queue.addLast(new int[]{nr,nc});
22             }
23         }
24         return image;
25     }
26     public static int[][] baseline(int[][] image,int sr,int sc,int color) {
27         int columns=validate(image,sr,sc),original=image[sr][sc];if(original==color)return image;
28         boolean[][] selected=new boolean[image.length][columns];selected[sr][sc]=true;
29         boolean changed;
30         do {
31             changed=false;boolean[][] next=new boolean[image.length][];for(int r=0;r<image.length;r++)next[r]=selected[r].clone();
32             for(int r=0;r<image.length;r++)for(int c=0;c<columns;c++)if(image[r][c]==original&&!selected[r][c])for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<image.length&&nc>=0&&nc<columns&&selected[nr][nc]){next[r][c]=true;changed=true;break;}}
33             selected=next;
34         }while(changed);
35         for(int r=0;r<image.length;r++)for(int c=0;c<columns;c++)if(selected[r][c])image[r][c]=color;
36         return image;
37     }
38 }
39

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

A same-color request is a validated no-op.
The guard prevents the replacement color from failing to distinguish discovered cells. Row-alias validation still runs before this return.
source
[[-2147483648,0],[-2147483648,2147483647]]
grid
[[-2147483648,0],[-2147483648,2147483647]]
queue
[]
sr
0
sc
0
color
-2147483648
original
-2147483648
recolored
[]
phase
"same-color"
current
[0,0]
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
[[-2147483648,0],[-2147483648,2147483647]]

Existing replacement-colored cells are not new owners

Input: {"image":[[2147483647,-2147483648]],"sr":0,"sc":0,"color":-2147483648} · Mutated image / thrown outcome: [[-2147483648,-2147483648]]

Step 1 of 3: Recolor the seed as its discovery mark.

New color differs from original; recolored cells cannot pass the original-color neighbor test again.

Flood fill — replacement color owns discovery

Phase: seed.

Current mutable grid

MINMIN

MIN = −2,147,483,648; MAX = 2,147,483,647. Their meaning follows this problem’s legend.

Coordinate queue — front at left; already claimed

(0, 0)

Original seed color: 2147483647. Replacement: -2147483648. Recolored coordinates: 1. Recoloring before enqueueing provides ownership when these colors differ. The same-color case returns after validation. Java preserves the outer array and distinct row identities.

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
source	`[[2147483647,-2147483648]]`
grid	`[[-2147483648,-2147483648]]`
queue	`[[0,0]]`
sr	`0`
sc	`0`
color	`-2147483648`
original	`2147483647`
recolored	`[[0,0]]`
phase	`"seed"`
current	`[0,0]`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
 4     private static int validate(int[][] image,int sr,int sc) {
 5         Objects.requireNonNull(image,"image");int columns=image.length==0?0:image[0]==null?-1:image[0].length;
 6         Set<int[]> rows=Collections.newSetFromMap(new IdentityHashMap<>());
 7         for(int[] row:image)if(row==null||row.length!=columns||!rows.add(row))throw new IllegalArgumentException("nonrectangular or aliased rows");
 8         if(sr<0||sr>=image.length||sc<0||sc>=columns)throw new IllegalArgumentException("seed outside image");
 9         return columns;
10     }
11     public static int[][] fill(int[][] image,int sr,int sc,int color) {
12         int columns=validate(image,sr,sc),original=image[sr][sc];
13         if(original==color)return image;
14         ArrayDeque<int[]> queue=new ArrayDeque<>();
15         image[sr][sc]=color;queue.addLast(new int[]{sr,sc});
16         while(!queue.isEmpty()) {
17             int[] cell=queue.removeFirst();
18             for(int[] d:DIRECTIONS) {
19                 int nr=cell[0]+d[0],nc=cell[1]+d[1];
20                 if(nr<0||nr>=image.length||nc<0||nc>=columns||image[nr][nc]!=original)continue;
21                 image[nr][nc]=color;queue.addLast(new int[]{nr,nc});
22             }
23         }
24         return image;
25     }
26     public static int[][] baseline(int[][] image,int sr,int sc,int color) {
27         int columns=validate(image,sr,sc),original=image[sr][sc];if(original==color)return image;
28         boolean[][] selected=new boolean[image.length][columns];selected[sr][sc]=true;
29         boolean changed;
30         do {
31             changed=false;boolean[][] next=new boolean[image.length][];for(int r=0;r<image.length;r++)next[r]=selected[r].clone();
32             for(int r=0;r<image.length;r++)for(int c=0;c<columns;c++)if(image[r][c]==original&&!selected[r][c])for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<image.length&&nc>=0&&nc<columns&&selected[nr][nc]){next[r][c]=true;changed=true;break;}}
33             selected=next;
34         }while(changed);
35         for(int r=0;r<image.length;r++)for(int c=0;c<columns;c++)if(selected[r][c])image[r][c]=color;
36         return image;
37     }
38 }
39

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Recolor the seed as its discovery mark.
New color differs from original; recolored cells cannot pass the original-color neighbor test again.
source
[[2147483647,-2147483648]]
grid
[[-2147483648,-2147483648]]
queue
[[0,0]]
sr
0
sc
0
color
-2147483648
original
2147483647
recolored
[[0,0]]
phase
"seed"
current
[0,0]
Expand a discovered coordinate.
The queue stores only original-component coordinates; recolored is teaching history, not a Java visited matrix.
source
[[2147483647,-2147483648]]
grid
[[-2147483648,-2147483648]]
queue
[]
sr
0
sc
0
color
-2147483648
original
2147483647
recolored
[[0,0]]
phase
"visit"
current
[0,0]
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
[[-2147483648,-2147483648]]

An empty image has no valid seed

Input: {"image":[],"sr":0,"sc":0,"color":0} · Mutated image / thrown outcome: {"error":"IllegalArgumentException"}

Step 1 of 2: Reject an out-of-image seed before mutation.

The Java validator also checks complete row shape and distinct row ownership before any write.

Flood fill — replacement color owns discovery

Phase: invalid-seed.

Current mutable grid

No cells.

Coordinate queue — front at left; already claimed

Empty.

Original seed color: not read. Replacement: 0. Recolored coordinates: 0. Recoloring before enqueueing provides ownership when these colors differ. The same-color case returns after validation. Java preserves the outer array and distinct row identities.

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
source	`[]`
grid	`[]`
queue	`[]`
sr	`0`
sc	`0`
color	`0`
original	`null`
recolored	`[]`
phase	`"invalid-seed"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
 4     private static int validate(int[][] image,int sr,int sc) {
 5         Objects.requireNonNull(image,"image");int columns=image.length==0?0:image[0]==null?-1:image[0].length;
 6         Set<int[]> rows=Collections.newSetFromMap(new IdentityHashMap<>());
 7         for(int[] row:image)if(row==null||row.length!=columns||!rows.add(row))throw new IllegalArgumentException("nonrectangular or aliased rows");
 8         if(sr<0||sr>=image.length||sc<0||sc>=columns)throw new IllegalArgumentException("seed outside image");
 9         return columns;
10     }
11     public static int[][] fill(int[][] image,int sr,int sc,int color) {
12         int columns=validate(image,sr,sc),original=image[sr][sc];
13         if(original==color)return image;
14         ArrayDeque<int[]> queue=new ArrayDeque<>();
15         image[sr][sc]=color;queue.addLast(new int[]{sr,sc});
16         while(!queue.isEmpty()) {
17             int[] cell=queue.removeFirst();
18             for(int[] d:DIRECTIONS) {
19                 int nr=cell[0]+d[0],nc=cell[1]+d[1];
20                 if(nr<0||nr>=image.length||nc<0||nc>=columns||image[nr][nc]!=original)continue;
21                 image[nr][nc]=color;queue.addLast(new int[]{nr,nc});
22             }
23         }
24         return image;
25     }
26     public static int[][] baseline(int[][] image,int sr,int sc,int color) {
27         int columns=validate(image,sr,sc),original=image[sr][sc];if(original==color)return image;
28         boolean[][] selected=new boolean[image.length][columns];selected[sr][sc]=true;
29         boolean changed;
30         do {
31             changed=false;boolean[][] next=new boolean[image.length][];for(int r=0;r<image.length;r++)next[r]=selected[r].clone();
32             for(int r=0;r<image.length;r++)for(int c=0;c<columns;c++)if(image[r][c]==original&&!selected[r][c])for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<image.length&&nc>=0&&nc<columns&&selected[nr][nc]){next[r][c]=true;changed=true;break;}}
33             selected=next;
34         }while(changed);
35         for(int r=0;r<image.length;r++)for(int c=0;c<columns;c++)if(selected[r][c])image[r][c]=color;
36         return image;
37     }
38 }
39

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Reject an out-of-image seed before mutation.
The Java validator also checks complete row shape and distinct row ownership before any write.
source
[]
grid
[]
queue
[]
sr
0
sc
0
color
0
original
null
recolored
[]
phase
"invalid-seed"
current
null
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
{"error":"IllegalArgumentException"}

Test the contract

Input: Isolated seed
Output: one coordinate changes
No global replacement.
Input: Replacement equals original
Output: same unchanged object
Validated no-op.
Input: Invalid seed or aliased rows
Output: IllegalArgumentException before writes
Ownership and bounds contract.
Input: 100,000-cell corridor
Output: all component cells recolored
No recursive depth dependence.

Common mistakes and counterexamples

Omit the same-color guard

Counterexample: If unchanged cells are treated as unvisited, equal-color requests can enqueue neighbors repeatedly.

Return after validation when original==replacement.

Replace every matching value

Counterexample: An isolated equal-valued region must remain unchanged.

Traverse from the seed through only original-color edges.

Mutate aliased rows

Counterexample: One write can affect a distinct coordinate not reached by the fill.

Reject shared row objects before mutation.

Follow-ups

Support aliased row objects anyway.

Define whether the API detaches rows, returns a fresh image, or treats shared storage as shared pixels. Those are different ownership contracts; coordinate-local in-place writes alone cannot meet the current semantics.

Fill all values within a tolerance.

Define eligibility relative to the original seed or local neighbors and preserve an immutable source view if recoloring changes future comparisons. A separate visited structure may become necessary.

Return the changed coordinate list.

Track each first paint as output, accounting for O(A) returned storage. The current implementation retains only the frontier, not a permanent mutation history.

Related foundations

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform equivalence claims.