Shortest Path in Binary Matrix — Coding Interview Question

In this post, we will go through the solution for “Shorted Path in Binary Matrix” leetcode interview question.

Problem Statement

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

• All the visited cells of the path are 0.
• All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Solution

First, let’s understand the problem. We are given a binary matrix, which is essentially a grid where each cell can be either 0 or 1. A starting cell located at the top-left corner of the grid and a target cell located at the bottom-right corner of the grid. The goal is to find the length of the shortest path from the starting cell to the target cell.

Now, let’s discuss how we can navigate through the grid. From any given cell, you can move to any of its eight adjacent cells: up, down, left, right, and the four diagonal directions. However, there’s a catch! You can only move to a cell if it contains a 0. If a cell contains a 1, it is considered an obstacle and you cannot pass through it.

To solve this problem, we can use a popular algorithm called Breadth-First Search (BFS). We start from the top-left cell and perform a BFS traversal of the grid. During the traversal, we keep track of the distance from the starting cell to each visited cell.

Here are the steps to solve this problem:

1. We will maintain a queue to keep track of the cells we need to visit.
2. Initially, we enqueue the starting cell and mark it as visited.
3. Then, while the queue is not empty, we dequeue a cell, explore its neighbors, and enqueue the unvisited neighboring cells.
4. We continue this process until we reach the target cell or exhaust all possible paths.

Here is the solution in Java for this problem:

    public int shortestPathBinaryMatrix(int[][] grid) {
        // Check for invalid input
        if (grid == null) {
            return -1; 
        }
        
        int rows = grid.length;
        int cols = grid[0].length;

        // Check if the grid is empty or the starting/ending cells are blocked
        if (rows == 0 || cols == 0 || grid[0][0] == 1 || grid[rows - 1][cols - 1] == 1) {
            return -1; // No valid path exists
        }
        
        // Create a queue to perform BFS traversal
        Queue<int[]> queue = new LinkedList<>();
        
        // Starting cell coordinates (row, col) and distance from the starting cell
        queue.offer(new int[]{0, 0, 1}); // Add the starting cell to the queue
        grid[0][0] = 1; // Mark the starting cell as visited
        
        // Define eight directions: up, down, left, right, and the four diagonal directions
        int[][] directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
        
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0];
            int col = cell[1];
            int distance = cell[2];
            
            // Check if we have reached the target cell
            if (row == rows - 1 && col == cols - 1) {
                return distance; // Return the shortest path distance
            }
            
            // Explore the eight neighboring cells
            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                
                // Check if the neighboring cell is within the grid boundaries and not visited
                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == 0) {
                    queue.offer(new int[]{newRow, newCol, distance + 1}); // Add the neighboring cell to the queue
                    grid[newRow][newCol] = 1; // Mark the neighboring cell as visited
                }
            }
        }
        
        return -1; // No valid path exists
    }

This solution uses a BFS approach to find the shortest path in the binary matrix. We start from the top-left cell and perform a BFS traversal, exploring the neighboring cells and updating the distance as we go. We mark the visited cells as 1 to avoid revisiting them.