1091. Shortest Path in Binary Matrix

#bfs #graph

Problem

Shortest Path in Binary Matrix - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

class Solution {
    // Directions on which it has to search
    int[][] dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}, {-1, -1}, {1, 1}, {-1, 1}, {1, -1}};

    public int shortestPathBinaryMatrix(int[][] grid) {
        // M -> No. of rows, N -> No. of cols
        // Time Complexity: O(m*n), for BFS in worst case
        // Space Complexity: O(m*n), for visited array and queue

        // Check if the grid is empty or null
        if (grid == null || grid.length == 0) {
            return -1;
        }

        int m = grid.length;
        int n = grid[0].length;

        // Check if the start or end point is blocked
        if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) {
            return -1;
        }

        boolean[][] visited = new boolean[m][n]; // Keep track of visited cells
        Deque<int[]> queue = new ArrayDeque<>(); // Queue for cells that needs to be processed

        queue.add(new int[]{0, 0});
        visited[0][0] = true;
        int count = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            count++;

            for (int i = 0; i < size; i++) {
                int[] currentPos = queue.poll();

                // Check if reached the destination
                if (currentPos[0] == m - 1 && currentPos[1] == n - 1) {
                    return count;
                }

                // Explore all possible directions
                for (int[] dir : dirs) {
                    int X = currentPos[0] + dir[0];
                    int Y = currentPos[1] + dir[1];

                    // Check if the next position is valid and not visited
                    if (X < 0 || X >= m || Y < 0 || Y >= n || visited[X][Y] || grid[X][Y] == 1) {
                        continue;
                    }

                    // Add the next position to the queue and mark it as visited
                    queue.add(new int[]{X, Y});
                    visited[X][Y] = true;
                }
            }
        }

        // No path found
        return -1;
    }
}