DSA-098 · FOCUSED PRACTICE

Walls and Gates — Nearest Gate Distance

Core · Java 21 · Version 1 · editorial draft

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

Understand the problem

Return a fresh matrix giving each empty room its minimum orthogonal distance to any gate, while preserving walls, gates and unreachable-room sentinels.

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. Zero rows or zero columns are allowed.
Cell codes are exactly -1 for wall, 0 for gate, and Integer.MAX_VALUE for an unassigned room. Reject other values before traversal; positive precomputed distances are not accepted as source input. Distance counts edges/moves from a gate, not visited cells.
Preserve all source cell values and row references; shared input row objects are allowed because coordinates, not row objects, identify vertices. Return a fresh outer matrix and distinct fresh rows, including zero-length rows. Walls stay -1, gates stay 0, and rooms unreachable from every gate remain MAX.

Examples

Input: [[MAX,-1,0],[MAX,MAX,MAX],[0,-1,MAX]]
Output: [[2,-1,0],[1,2,1],[0,-1,2]]
Both gates start at zero; first room discovery minimizes across either source.
Input: [[MAX,-1,0],[-1,-1,-1],[MAX,MAX,MAX]]
Output: unchanged values in fresh rows
Walls separate the unassigned rooms from the only gate.

Before you start

Unweighted BFS distance and discovery ownership
Multi-source initialization (DSA-097) and fresh matrix output

Recognize the structure

Running a separate search from every room repeats the same geometry. Reverse the viewpoint: all gates have distance zero, and one shared BFS wave assigns each room the first time any gate can reach it.

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 · 153/20,000 characters

Self-review

Can I prove first discovery minimizes over all sources?Can I separate temporary undiscovered MAX from final unreachable MAX?Can I verify every returned row is independent of input aliases?

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

Try before revealing

Hint 1

Could all gates act as sources at the same time?

Hint 2

Copy the source, queue every gate at zero, then expand one FIFO.

Hint 3

Assign a MAX room before enqueueing it; that first distance is minimum.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Search for the nearest gate from each room

For each MAX room, run an independent BFS through nonwalls until a gate is popped; retain MAX if no gate exists in its component. Gates and walls are copied unchanged. This is correct but can inspect most cells for every room, giving quadratic work.

Improve the baseline

Validate and copy the full source

Accept only the declared codes and allocate a distinct copy of every input row. Updating this copy does not change aliased source rows.

Queue all gates before any expansion

Every gate enters at distance zero. Treat this as simultaneous sources; starting complete independent traversals one after another can assign a nonminimum result.

Claim only undiscovered MAX rooms

When a finite-distance cell reaches a MAX neighbor, assign parentDistance+1 before enqueueing. Never enqueue walls or already assigned rooms.

Why it is correct

Distance-layer invariant

The FIFO contains discovered coordinates in nondecreasing distance from the nearest gate. All gates initialize the minimum layer zero.

First discovery is optimal

If a newly claimed room had a shorter route from another gate, that route’s predecessor would have been expanded in an earlier layer and claimed it already. Thus its first value is final.

Unreachable and ownership correctness

When the queue empties, every gate-reachable room has been claimed and every remaining MAX room is disconnected from all gates. Only fresh output rows were written, preserving all source references and values.

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[][] grid) {
        Objects.requireNonNull(grid,"grid");
        int columns=grid.length==0?0:grid[0]==null?-1:grid[0].length;
        for(int[] row:grid) {
            if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular grid");
            for(int value:row) if(value!=-1&&value!=0&&value!=Integer.MAX_VALUE)throw new IllegalArgumentException("invalid cell");
        }
        return columns;
    }
    private static int[][] copy(int[][] input){int[][] out=new int[input.length][];for(int r=0;r<input.length;r++)out[r]=input[r].clone();return out;}
    public static int[][] distances(int[][] rooms) {
        int columns=validate(rooms);int[][] result=copy(rooms);ArrayDeque<int[]> queue=new ArrayDeque<>();
        for(int r=0;r<rooms.length;r++)for(int c=0;c<columns;c++)if(result[r][c]==0)queue.addLast(new int[]{r,c});
        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>=rooms.length||nc<0||nc>=columns||result[nr][nc]!=Integer.MAX_VALUE)continue;
                result[nr][nc]=result[cell[0]][cell[1]]+1;queue.addLast(new int[]{nr,nc});
            }
        }
        return result;
    }
    public static int[][] baseline(int[][] rooms) {
        int columns=validate(rooms);int[][] result=copy(rooms);
        for(int r=0;r<rooms.length;r++)for(int c=0;c<columns;c++)if(rooms[r][c]==Integer.MAX_VALUE) {
            boolean[][] visited=new boolean[rooms.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c,0});
            while(!queue.isEmpty()){int[] cell=queue.removeFirst();if(rooms[cell[0]][cell[1]]==0){result[r][c]=cell[2];break;}for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<rooms.length&&nc>=0&&nc<columns&&rooms[nr][nc]!=-1&&!visited[nr][nc]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc,cell[2]+1});}}}
        }
        return result;
    }
}

Read the meaningful blocks

MAX has phase-dependent meaning

During traversal it means undiscovered, not yet proven unreachable. Only frontier exhaustion justifies the unreachable interpretation.

Do not compute MAX+1

Only finite discovered cells are popped. Under the cell bound, finite distances are at most B−1 and fit int.

Output copying is not auxiliary queue space

The returned matrix occupies row/cell storage even for zero-column inputs; queue memory is a separate cost.

Complexity

Let R be row count, B total cells, and N=R+B, so validation/row allocation still count when rows have zero columns. Main time is O(N); queue workspace is O(B+1) excluding the O(N) fresh returned matrix. Shape/code validation and copying count every row/cell, while each discovered coordinate is expanded once.

The per-room baseline uses O(N(B+1)) worst-case time and O(N) peak visited/frontier workspace in addition to its fresh output. For nonempty rectangles this is the usual O(B²) versus O(B) traversal comparison.

Exact-state walkthroughs

Reveal normal and boundary traces

All gates share the zero-distance frontier

Input: [[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]] · Fresh gate-distance matrix: [[2,-1,0],[1,2,1],[0,-1,2]]

Step 1 of 15: Seed every gate at distance zero in a fresh output matrix.

All sources are queued before expansion. MAX means not yet discovered during traversal, and unreachable only after the queue exhausts.

Nearest gate — simultaneous distance sources

Phase: seed.

Unchanged source grid

MAX-10

MAXMAXMAX

0-1MAX

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, 2)
(2, 0)

Fresh output — gate distances count edges

MAX-10

MAXMAXMAX

0-1MAX

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

−1 = wall; 0 = gate; MAX = not discovered yet. All gates are seeded together. A finite value is already minimum when assigned; the input stays unchanged.

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

State after this step
Variable	Value
source	`[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]`
grid	`[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]`
queue	`[[0,2],[2,0]]`
output	`[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]`
phase	`"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[][] grid) {
 5         Objects.requireNonNull(grid,"grid");
 6         int columns=grid.length==0?0:grid[0]==null?-1:grid[0].length;
 7         for(int[] row:grid) {
 8             if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular grid");
 9             for(int value:row) if(value!=-1&&value!=0&&value!=Integer.MAX_VALUE)throw new IllegalArgumentException("invalid cell");
10         }
11         return columns;
12     }
13     private static int[][] copy(int[][] input){int[][] out=new int[input.length][];for(int r=0;r<input.length;r++)out[r]=input[r].clone();return out;}
14     public static int[][] distances(int[][] rooms) {
15         int columns=validate(rooms);int[][] result=copy(rooms);ArrayDeque<int[]> queue=new ArrayDeque<>();
16         for(int r=0;r<rooms.length;r++)for(int c=0;c<columns;c++)if(result[r][c]==0)queue.addLast(new int[]{r,c});
17         while(!queue.isEmpty()) {
18             int[] cell=queue.removeFirst();
19             for(int[] d:DIRECTIONS) {
20                 int nr=cell[0]+d[0],nc=cell[1]+d[1];
21                 if(nr<0||nr>=rooms.length||nc<0||nc>=columns||result[nr][nc]!=Integer.MAX_VALUE)continue;
22                 result[nr][nc]=result[cell[0]][cell[1]]+1;queue.addLast(new int[]{nr,nc});
23             }
24         }
25         return result;
26     }
27     public static int[][] baseline(int[][] rooms) {
28         int columns=validate(rooms);int[][] result=copy(rooms);
29         for(int r=0;r<rooms.length;r++)for(int c=0;c<columns;c++)if(rooms[r][c]==Integer.MAX_VALUE) {
30             boolean[][] visited=new boolean[rooms.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c,0});
31             while(!queue.isEmpty()){int[] cell=queue.removeFirst();if(rooms[cell[0]][cell[1]]==0){result[r][c]=cell[2];break;}for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<rooms.length&&nc>=0&&nc<columns&&rooms[nr][nc]!=-1&&!visited[nr][nc]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc,cell[2]+1});}}}
32         }
33         return result;
34     }
35 }
36

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

Read the full static trace

Seed every gate at distance zero in a fresh output matrix.
All sources are queued before expansion. MAX means not yet discovered during traversal, and unreachable only after the queue exhausts.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[[0,2],[2,0]]
output
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
phase
"seed"
current
null
Expand the next nondecreasing-distance coordinate.
A queued cell has a finite established distance; walls and undiscovered MAX values are never expanded.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[[2,0]]
output
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
phase
"visit"
current
[0,2]
Assign the first gate distance and claim this room.
First discovery is minimum across all gates, including ties. Output rows are fresh even when input rows alias.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[[2,0],[1,2]]
output
[[2147483647,-1,0],[2147483647,2147483647,1],[0,-1,2147483647]]
phase
"claim"
current
[0,2]
claimed
[1,2]
Expand the next nondecreasing-distance coordinate.
A queued cell has a finite established distance; walls and undiscovered MAX values are never expanded.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[[1,2]]
output
[[2147483647,-1,0],[2147483647,2147483647,1],[0,-1,2147483647]]
phase
"visit"
current
[2,0]
Assign the first gate distance and claim this room.
First discovery is minimum across all gates, including ties. Output rows are fresh even when input rows alias.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[[1,2],[1,0]]
output
[[2147483647,-1,0],[1,2147483647,1],[0,-1,2147483647]]
phase
"claim"
current
[2,0]
claimed
[1,0]
Expand the next nondecreasing-distance coordinate.
A queued cell has a finite established distance; walls and undiscovered MAX values are never expanded.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[[1,0]]
output
[[2147483647,-1,0],[1,2147483647,1],[0,-1,2147483647]]
phase
"visit"
current
[1,2]
Assign the first gate distance and claim this room.
First discovery is minimum across all gates, including ties. Output rows are fresh even when input rows alias.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[[1,0],[2,2]]
output
[[2147483647,-1,0],[1,2147483647,1],[0,-1,2]]
phase
"claim"
current
[1,2]
claimed
[2,2]
Assign the first gate distance and claim this room.
First discovery is minimum across all gates, including ties. Output rows are fresh even when input rows alias.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[[1,0],[2,2],[1,1]]
output
[[2147483647,-1,0],[1,2,1],[0,-1,2]]
phase
"claim"
current
[1,2]
claimed
[1,1]
Expand the next nondecreasing-distance coordinate.
A queued cell has a finite established distance; walls and undiscovered MAX values are never expanded.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[[2,2],[1,1]]
output
[[2147483647,-1,0],[1,2,1],[0,-1,2]]
phase
"visit"
current
[1,0]
Assign the first gate distance and claim this room.
First discovery is minimum across all gates, including ties. Output rows are fresh even when input rows alias.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[[2,2],[1,1],[0,0]]
output
[[2,-1,0],[1,2,1],[0,-1,2]]
phase
"claim"
current
[1,0]
claimed
[0,0]
Expand the next nondecreasing-distance coordinate.
A queued cell has a finite established distance; walls and undiscovered MAX values are never expanded.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[[1,1],[0,0]]
output
[[2,-1,0],[1,2,1],[0,-1,2]]
phase
"visit"
current
[2,2]
Expand the next nondecreasing-distance coordinate.
A queued cell has a finite established distance; walls and undiscovered MAX values are never expanded.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[[0,0]]
output
[[2,-1,0],[1,2,1],[0,-1,2]]
phase
"visit"
current
[1,1]
Expand the next nondecreasing-distance coordinate.
A queued cell has a finite established distance; walls and undiscovered MAX values are never expanded.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[]
output
[[2,-1,0],[1,2,1],[0,-1,2]]
phase
"visit"
current
[0,0]
Keep walls and truly unreachable rooms at their declared sentinels.
The empty frontier certifies that remaining MAX rooms cannot reach a gate.
source
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
grid
[[2147483647,-1,0],[2147483647,2147483647,2147483647],[0,-1,2147483647]]
queue
[]
output
[[2,-1,0],[1,2,1],[0,-1,2]]
phase
"complete"
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
[[2,-1,0],[1,2,1],[0,-1,2]]

Unreachable rooms keep MAX after exhaustion

Input: [[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]] · Fresh gate-distance matrix: [[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]

Step 1 of 4: Seed every gate at distance zero in a fresh output matrix.

All sources are queued before expansion. MAX means not yet discovered during traversal, and unreachable only after the queue exhausts.

Nearest gate — simultaneous distance sources

Phase: seed.

Unchanged source grid

MAX-10

-1-1-1

MAXMAXMAX

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, 2)

Fresh output — gate distances count edges

MAX-10

-1-1-1

MAXMAXMAX

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

−1 = wall; 0 = gate; MAX = not discovered yet. All gates are seeded together. A finite value is already minimum when assigned; the input stays unchanged.

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

State after this step
Variable	Value
source	`[[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]`
grid	`[[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]`
queue	`[[0,2]]`
output	`[[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]`
phase	`"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[][] grid) {
 5         Objects.requireNonNull(grid,"grid");
 6         int columns=grid.length==0?0:grid[0]==null?-1:grid[0].length;
 7         for(int[] row:grid) {
 8             if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular grid");
 9             for(int value:row) if(value!=-1&&value!=0&&value!=Integer.MAX_VALUE)throw new IllegalArgumentException("invalid cell");
10         }
11         return columns;
12     }
13     private static int[][] copy(int[][] input){int[][] out=new int[input.length][];for(int r=0;r<input.length;r++)out[r]=input[r].clone();return out;}
14     public static int[][] distances(int[][] rooms) {
15         int columns=validate(rooms);int[][] result=copy(rooms);ArrayDeque<int[]> queue=new ArrayDeque<>();
16         for(int r=0;r<rooms.length;r++)for(int c=0;c<columns;c++)if(result[r][c]==0)queue.addLast(new int[]{r,c});
17         while(!queue.isEmpty()) {
18             int[] cell=queue.removeFirst();
19             for(int[] d:DIRECTIONS) {
20                 int nr=cell[0]+d[0],nc=cell[1]+d[1];
21                 if(nr<0||nr>=rooms.length||nc<0||nc>=columns||result[nr][nc]!=Integer.MAX_VALUE)continue;
22                 result[nr][nc]=result[cell[0]][cell[1]]+1;queue.addLast(new int[]{nr,nc});
23             }
24         }
25         return result;
26     }
27     public static int[][] baseline(int[][] rooms) {
28         int columns=validate(rooms);int[][] result=copy(rooms);
29         for(int r=0;r<rooms.length;r++)for(int c=0;c<columns;c++)if(rooms[r][c]==Integer.MAX_VALUE) {
30             boolean[][] visited=new boolean[rooms.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c,0});
31             while(!queue.isEmpty()){int[] cell=queue.removeFirst();if(rooms[cell[0]][cell[1]]==0){result[r][c]=cell[2];break;}for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<rooms.length&&nc>=0&&nc<columns&&rooms[nr][nc]!=-1&&!visited[nr][nc]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc,cell[2]+1});}}}
32         }
33         return result;
34     }
35 }
36

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

Read the full static trace

Seed every gate at distance zero in a fresh output matrix.
All sources are queued before expansion. MAX means not yet discovered during traversal, and unreachable only after the queue exhausts.
source
[[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]
grid
[[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]
queue
[[0,2]]
output
[[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]
phase
"seed"
current
null
Expand the next nondecreasing-distance coordinate.
A queued cell has a finite established distance; walls and undiscovered MAX values are never expanded.
source
[[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]
grid
[[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]
queue
[]
output
[[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]
phase
"visit"
current
[0,2]
Keep walls and truly unreachable rooms at their declared sentinels.
The empty frontier certifies that remaining MAX rooms cannot reach a gate.
source
[[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]
grid
[[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]
queue
[]
output
[[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]
phase
"complete"
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
[[2147483647,-1,0],[-1,-1,-1],[2147483647,2147483647,2147483647]]

Fresh zero-column rows

Input: [[],[]] · Fresh gate-distance matrix: [[],[]]

Step 1 of 3: Seed every gate at distance zero in a fresh output matrix.

All sources are queued before expansion. MAX means not yet discovered during traversal, and unreachable only after the queue exhausts.

Nearest gate — simultaneous distance sources

Phase: seed.

Unchanged source grid

No cells.

Coordinate queue — front at left; already claimed

Empty.

Fresh output — gate distances count edges

No cells.

−1 = wall; 0 = gate; MAX = not discovered yet. All gates are seeded together. A finite value is already minimum when assigned; the input stays unchanged.

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	`[]`
output	`[[],[]]`
phase	`"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[][] grid) {
 5         Objects.requireNonNull(grid,"grid");
 6         int columns=grid.length==0?0:grid[0]==null?-1:grid[0].length;
 7         for(int[] row:grid) {
 8             if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular grid");
 9             for(int value:row) if(value!=-1&&value!=0&&value!=Integer.MAX_VALUE)throw new IllegalArgumentException("invalid cell");
10         }
11         return columns;
12     }
13     private static int[][] copy(int[][] input){int[][] out=new int[input.length][];for(int r=0;r<input.length;r++)out[r]=input[r].clone();return out;}
14     public static int[][] distances(int[][] rooms) {
15         int columns=validate(rooms);int[][] result=copy(rooms);ArrayDeque<int[]> queue=new ArrayDeque<>();
16         for(int r=0;r<rooms.length;r++)for(int c=0;c<columns;c++)if(result[r][c]==0)queue.addLast(new int[]{r,c});
17         while(!queue.isEmpty()) {
18             int[] cell=queue.removeFirst();
19             for(int[] d:DIRECTIONS) {
20                 int nr=cell[0]+d[0],nc=cell[1]+d[1];
21                 if(nr<0||nr>=rooms.length||nc<0||nc>=columns||result[nr][nc]!=Integer.MAX_VALUE)continue;
22                 result[nr][nc]=result[cell[0]][cell[1]]+1;queue.addLast(new int[]{nr,nc});
23             }
24         }
25         return result;
26     }
27     public static int[][] baseline(int[][] rooms) {
28         int columns=validate(rooms);int[][] result=copy(rooms);
29         for(int r=0;r<rooms.length;r++)for(int c=0;c<columns;c++)if(rooms[r][c]==Integer.MAX_VALUE) {
30             boolean[][] visited=new boolean[rooms.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c,0});
31             while(!queue.isEmpty()){int[] cell=queue.removeFirst();if(rooms[cell[0]][cell[1]]==0){result[r][c]=cell[2];break;}for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<rooms.length&&nc>=0&&nc<columns&&rooms[nr][nc]!=-1&&!visited[nr][nc]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc,cell[2]+1});}}}
32         }
33         return result;
34     }
35 }
36

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

Read the full static trace

Seed every gate at distance zero in a fresh output matrix.
All sources are queued before expansion. MAX means not yet discovered during traversal, and unreachable only after the queue exhausts.
source
[[],[]]
grid
[[],[]]
queue
[]
output
[[],[]]
phase
"seed"
current
null
Keep walls and truly unreachable rooms at their declared sentinels.
The empty frontier certifies that remaining MAX rooms cannot reach a gate.
source
[[],[]]
grid
[[],[]]
queue
[]
output
[[],[]]
phase
"complete"
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
[[],[]]

Test the contract

Input: No gates
Output: MAX rooms remain MAX
Unreachable source components.
Input: Several equidistant gates
Output: minimum distance once
Multi-source tie correctness.
Input: Walls isolate a room
Output: MAX
No wall crossing.
Input: 100,000-cell gate corridor
Output: distances 0 through 99999
No overflow or recursive depth risk.

Common mistakes and counterexamples

Run one gate to completion before seeding the others

Counterexample: A room may get a longer source-specific distance first.

Initialize every gate in the same zero layer.

Treat gates as distance one

Counterexample: The API measures moves from a gate, so a gate is zero.

Keep source zero and assign neighbor+1.

Overwrite walls or add to MAX

Counterexample: Walls are impassable and unassigned rooms are not finite-distance parents.

Expand only queued finite cells and claim only MAX neighbors.

Follow-ups

Return the nearest gate identity too.

Carry source ownership with each wave and define ties, for example smallest gate row/column. Initial source order alone needs a clear tie proof and tests.

Allow weighted room transitions.

FIFO first discovery no longer finalizes arbitrary nonnegative weights. Use Dijkstra or a restricted-weight deque algorithm and state the revised relaxation rule.

Update distances when gates change.

Adding a gate can improve existing distances, while removal may invalidate an entire region. A static one-shot BFS does not provide efficient deletion maintenance.

Related foundations

BFS: discovery, layers, and multiple sources

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.