The O(n) Club: Shortest Path in Binary Matrix—Why BFS Is Your Best Frenemy

The O(n) Club: Shortest Path in Binary Matrix—Why BFS Is Your Best Frenemy

⚡ TL;DR

Need the shortest way from top-left to bottom-right in a binary grid with 8-directional moves? Practically made for BFS—unless you’re trying to relive every debugging nightmare you’ve ever had. Brute-force will crush your soul (and your runtime). Here’s the sad path:

// Brute force: Only if you hate happiness
int shortestPath(int[][] grid) {
    // Recursively try all paths. Drink coffee. Recurse more. Regret.
    // Backtrack, hit TLE, send resignation email.
}
// Instead, let BFS do the heavy lifting.

🧠 How Devs Usually Mess This Up

🔍 What’s Actually Going On

Imagine you’re a robot in a warehouse. You can mozy around in eight directions—straight lines and snazzy diagonals. But some squares are blocked (yes, the universe is rude), and you need the shortest path to the finish. BFS acts like an ever-expanding ripple: it explores all possible moves one layer at a time, so the first time you hit your destination, it’s guaranteed to be the minimum number of steps. DFS, on the other hand, would just wander off, call its mom, and forget why it started.

🛠️ PseudoCode

• Early exit if start or destination is blocked:

  // Walls at the gate? Give up immediately.
  if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
  

• Kick off the BFS queue with (0,0) and path length 1:

  Queue<int[]> q = new LinkedList<>();
  q.offer(new int[]{0, 0, 1});
  

• Set up all 8 directions—diagonals included!

  int[] dx = {-1,-1,-1,0,0,1,1,1};
  int[] dy = {-1,0,1,-1,1,-1,0,1};
  

• While queue is not empty:

  while(!q.isEmpty()) {
      int[] cell = q.poll();
      // If at the end, return distance
      // For all 8 neighbors:
          // If valid and open, mark visited and queue
  }

• Return -1 if the queue is exhausted wasted—no path exists.

💻 The Code

public int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;
    if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
    int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};
    Queue<int> queue = new LinkedList<>();
    queue.offer(new int[]{0, 0, 1});
    grid[0][0] = 1; // Visited!
    while (!queue.isEmpty()) {
        int[] curr = queue.poll();
        int x = curr[0], y = curr[1], dist = curr[2];
        if (x == n - 1 && y == n - 1) return dist;
        for (int dir = 0; dir < 8; dir++) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx >= 0 && ny >= 0 && nx < n && ny < n && grid[nx][ny] == 0) {
                queue.offer(new int[]{nx, ny, dist + 1});
                grid[nx][ny] = 1;
            }
        }
    }
    return -1;
}
</int>

⚠️ Pitfalls, Traps & Runtime Smacks

• Miss the diagonals? You’ll wonder why random tests fail.
• Out-of-bounds? Java’s arrays won’t forgive you—or warn you politely.
• Remember: Start and end cells both count in path length. This isn’t a fencepost problem; it’s an everyone-gets-counted problem.
• Visited array? Not needed. Overwrite the grid in-place; your memory will thank you.
• Time/Space: Both O(n²). Optimal and refreshingly boring.

🧠 Interviewer Brain-Tattoo

“DFS explores like a curious toddler; BFS actually brings home groceries.”