The O(n) Club: 01 Matrix: Why BFS Always Gets the Invite (and DFS Sits Out)

The O(n) Club: 01 Matrix — Why BFS Always Gets the Invite (and DFS Sits Out)

⚡ TL;DR

The mission: For every 1 in your binary grid, find the Manhattan distance to the nearest 0—without creating a gridlock in your CPU. Old-school brute force means BFS from every 1, which will melt your runtime. Instead: multi-source BFS from all zero-cells at once and let that optimism ripple out. Java sample for the impatient:

// Please don’t do this
total = 0;
for (cell in all_cells) {
  if (matrix[cell] == 1) {
    // BFS or DFS from here — get ready for a vacation... from your job
  }
}

🧠 How Devs Usually Mess This Up

Raise your hand if you ever BFS’d from every 1. (No judgment. Okay, a little.) That’s O(mn)*O(mn) — which is just TLE dressed in formal attire. Some also think diagonals count (they don’t, sorry chess fans) or skip marking when a cell’s distance is settled, accidentally racking up step counts like FitBit addicts.

🔍 What’s Actually Going On

Picture your matrix as a city grid. The 0s are pizza shops, and every 1 is a hungry dev. Instead of 1s aimlessly roaming for carbs, all the pizza shops yell, “Free slices!” at once, and the scent wafts block by block out to the starving coders. Multi-source BFS, baby: the shortest path to nourishment arrives with maximum efficiency and minimal runtime heartburn.

🛠️ PseudoCode

• Build a result matrix. 0s set to 0, 1s sent to Java’s version of the abyss: Integer.MAX_VALUE.
• Queue up all (r, c) where matrix[r][c] == 0. (Pizza shops get dibs on broadcasting!)

  Queue<int[]> queue = new LinkedList<>();
  for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
      if (mat[i][j] == 0) queue.add(new int[]{i, j});
    }
  }

• Process every entry in the queue. For each, check only 4 directions (up, down, left, right):
• If a neighbor’s stored distance is more than current + 1, update it and throw it into the queue for the next roundtrip.
• Repeat until zero hungry devs remain (queue empty).

💻 The Code

public int[][] updateMatrix(int[][] mat) {
    int rows = mat.length, cols = mat[0].length;
    int[][] dist = new int[rows][cols];
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (mat[i][j] == 0) {
                dist[i][j] = 0;
                queue.offer(new int[]{i, j});
            } else {
                dist[i][j] = Integer.MAX_VALUE;
            }
        }
    }
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!queue.isEmpty()) {
        int[] cell = queue.poll();
        for (int[] d : dirs) {
            int r = cell[0] + d[0], c = cell[1] + d[1];
            if (r >= 0 && r < rows && c >= 0 && c < cols) {
                if (dist[r][c] > dist[cell[0]][cell[1]] + 1) {
                    dist[r][c] = dist[cell[0]][cell[1]] + 1;
                    queue.offer(new int[]{r, c});
                }
            }
        }
    }
    return dist;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Diagonal wanderlust? No diagonals allowed. Stick to cardinal directions unless your interview suddenly turns into Pac-Man.
• Re-BFS from every 1: Pro tip: Prepare for a well-earned TLE slap.
• Forgot to mark visited/shortest path? Expect wild results and the joy of debugging after midnight.
• Initialization flop: Not setting 1s to Integer.MAX_VALUE is like letting invalid data seep in with no floodgates.
• Time & Space: O(mn) — both for runtime and space. Efficient enough that you could actually leave work on time.

🧠 Interviewer Brain-Tattoo

“Start from the zeros. Let your pizza aroma spread. Save every dev from starvation—efficiently.”