A warehouse floor plan is a binary raster: 0 empty dock, 1 occupied. Ops wants, for every cell, the hops to the nearest empty dock — a distance field, not a single SLA minute. The intern, for every 1, ran a BFS until they hit a 0. A 3×3 fixture in staging returned in milliseconds. A thousand-cell floor in production was still walking when the request timed out.
01 Matrix asks for the 4-adjacent distance from every cell to the nearest 0. This is an interview writeup, not a layout lecture. The graphs post owns the layout; the BFS post owns the queue. Here we only care about seeding every 0 before the first hop, marking when we enqueue, and writing hops into a grid. Same multi-source walk as Rotting Oranges; minutes there were one integer, here the hop count is the payload in every cell.
The problem
Given an int[][] mat of 0 and 1, return an int[][] of the same shape where each cell holds the 4-adjacent hop count to the nearest 0. Distance of a 0 is 0. Four directions — up, down, left, right — not diagonals. There is at least one 0.
0 0 0
0 1 0
0 0 0 → 0 0 0
0 1 0
0 0 0
0 0 0
0 1 0
1 1 1 → 0 0 0
0 1 0
1 2 1
1 1
1 0 → 2 1
1 0First floor: only the center is occupied, and it already shares an edge with a dock. Second: the bottom-middle cell waits two hops. Third: the far 1 is two hops from the single 0.
Note: Nothing here is a wall. 0 is the target, not empty space you skip the way Rotting Oranges skips a 0. Bounds-check first, then skip cells you have already marked. A 4-direction int[][] dirs table is the neighbor list; do not special-case four ifs unless the board asks you to name them.
A nearest-zero walk from every one is the honest brute force
For each 1, run a BFS until you hit a 0, write that hop count, and leave every 0 as 0. Correct. Quadratic.
int[][] updateMatrixRestart(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int[][] dist = new int[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (mat[r][c] == 1) {
dist[r][c] = nearestZero(mat, r, c, dirs);
}
}
}
return dist;
}
int nearestZero(int[][] mat, int sr, int sc, int[][] dirs) {
int m = mat.length;
int n = mat[0].length;
boolean[][] seen = new boolean[m][n];
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[] { sr, sc });
seen[sr][sc] = true;
int hops = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] cur = q.poll();
if (mat[cur[0]][cur[1]] == 0) {
return hops;
}
for (int[] d : dirs) {
int nr = cur[0] + d[0];
int nc = cur[1] + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) {
continue;
}
seen[nr][nc] = true;
q.offer(new int[] { nr, nc });
}
}
hops++;
}
throw new IllegalStateException("no zero");
}At a 3×3 fixture this is a rounding error. On a floor of K occupied cells you restart a walk that can visit every cell K times: you paid a full BFS per 1 for a question that only needs one walk from every 0 at once.
Seed every zero, then one BFS
Scan once. Offer every 0 onto an ArrayDeque and mark it seen. Those cells are hop 0; a new int[][] already holds 0 there, so you do not write them. Then drain by count: each wave is one hop. When a neighbor is unseen, write the current hop count, mark, and offer. Distances are the hop count; do not re-derive that here.
0 0 0
0 1 0
1 1 1
seed all 0s dist stays 0 on those cells
wave 1 (1,1)=1 (2,0)=1 (2,2)=1
wave 2 (2,1)=2
→ [[0,0,0],[0,1,0],[1,2,1]]Four deltas, bounds-check, skip seen. Do not mutate mat to store distance: a written 1 and an original 1 are the same integer. A boolean[][] is the mark. The Java is that walk. Use Deque and ArrayDeque, not java.util.Stack, not ArrayList.remove(0).
int[][] updateMatrix(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int[][] dist = new int[m][n];
boolean[][] seen = new boolean[m][n];
Deque<int[]> q = new ArrayDeque<>();
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (mat[r][c] == 0) {
q.offer(new int[] { r, c });
seen[r][c] = true;
}
}
}
int hops = 0;
while (!q.isEmpty()) {
int size = q.size();
hops++;
for (int i = 0; i < size; i++) {
int[] cur = q.poll();
for (int[] d : dirs) {
int nr = cur[0] + d[0];
int nc = cur[1] + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || seen[nr][nc]) {
continue;
}
seen[nr][nc] = true;
dist[nr][nc] = hops;
q.offer(new int[] { nr, nc });
}
}
}
return dist;
}Time is O(mn) — each cell is offered at most once, and each offered cell looks at four neighbors. Space is O(mn) for the queue and the seen grid when the floor is packed.
Note: Mark when you enqueue. Write seen and dist before offer. Wait until poll and two docks both enqueue the same 1, and that cell’s distance is no longer first-touch. Seed every 0 before the first wave. One source sequences two simultaneous fronts. Leave a 0 as distance 0. You never offer it as a 1, and you never start a brute walk from it.
What interviewers usually poke next
- Rotting Oranges. Same seed-all-sources BFS. That prompt returns one integer of minutes and
-1if something never rots; this one returns a grid of hops and every cell is reachable because a0exists. - Two-pass DP. Sweep top-left (only up/left), then bottom-right (only down/right), taking
min(self, neighbor + 1). Follow-up, not the default — the queue is what you write first, and walls break the sweep. - Walls / blocked cells. Manhattan to every
0is then wrong, and the DP sweep is too. Multi-source BFS still works if you refuse to enqueue a wall. - In-place, no
seen. A written distance of1collides with an original1. Use a sentinel (Integer.MAX_VALUE) on the1s, or keep the extra grid. Ask before you overwritemat.
You are done with this problem when you can say, out loud, why a BFS from each 1 is quadratic, why every 0 belongs in the queue before the first hop, and why this is Rotting Oranges with a distance grid instead of a minute count.