1926. Nearest Exit from Entrance in Maze

Hello, reader 👋🏽 ! Welcome to day 51 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 1926. Nearest Exit from Entrance in Maze.

🤔 Problem Statement

Given an m x n matrix maze (0-indexed) with empty cells (represented as '.') and walls (represented as '+'), and an entry cell entrance = [entrancerow, entrancecol] denoting the starting point, find the nearest exit from the entrance.
An exit is defined as an empty cell that is at the border of the maze.
In one step, the allowed directions are: one cell up, down, left, or right.
The steps need to be within the boundaries of the maze and a cell with a wall cannot be stepped into.
The entrance does not count as an exit.
Return the number of steps in the shortest path from the entrance to the nearest exit, or -1 if no such path exists.
E.g.:
- [["+","+",".","+"],[".",".",".","+"],["+","+","+","."]], entrance = [1,2] => 1
- [[".", "+"]], entrance = [0,0] => -1

💬 Thought Process - Breadth First Search

This is similar to finding the shortest route given a graph as a matrix, but with constrainsts.
We'll use a queue to mark the nodes that need to be visited along with a set or a matrix to represent if cells have been visited or not.
- Note: Here in this approach, I'll be using extra space that is a copy of the input matrix. Every time a valid cell is visited, we'll be changing it to a cell with wall (to a '+') to mark it as visited.
- But you can avoid this and do the same in the input matrix as well. But this isn't considered to be good practice.
Initially, we'll add the starting point indices along with the current step, which is 0. So the queue will contain a list of integers to represent the following: rowIndex, colIndex, stepsTakenToReachCell.
We'll then process every valid point in the queue and try to move along the four directions until the queue is empty.
But before checking if this cell can be further processed, we'll have to check if we have landed on a valid cell.
A valid cell is within boundaries of the maze, and doe not contain a wall.
- Note:: We don't have to separately check for visited cells as we are marking changing them to a cell with wall once processed.
For every valid step from the currently processing node, we'll also check if it's a boundary cell.
A boundary cell is one which has either:
- row index as 0 => cell in the first row
- row index as m-1, where m = number of rows => cell in the last row
- col index as 0 => cell in the first column
- co index as n-1, where n = number of cols => cell in the last column
If any of the above is true, we will return the total steps immediately. Which is the number of steps taken to reach the node being processed currently + 1.
If we're unable to find a boundary cell and the queue becomes empty, we'll simply return -1.

👩🏽‍💻 Solution - Breadth First Search

Below is the code for the above discussed approach.

class Cell {
    int row, col;
    Cell(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

class Solution {
    public int nearestExit(char[][] maze, int[] entrance) {
        if(maze == null || maze.length == 0) return -1;

        int m = maze.length, n = maze[0].length;
        char[][] mazeCopy = new char[m][n];
        for(int i = 0; i<m; i++) {
            mazeCopy[i] = maze[i].clone();
        }

        Queue<List<Integer>> paths = new LinkedList<>();        
        int startRow = entrance[0], startCol = entrance[1];
        int[][] directions = new int[][] {
            {-1,0}, {1,0}, {0,-1}, {0,1}
        };

        List<Integer> startCell = new ArrayList();
        startCell.add(startRow);
        startCell.add(startCol);
        startCell.add(0);

        paths.add(startCell);
        mazeCopy[startRow][startCol] = '+';
        int smallestPath = 0;
        while(!paths.isEmpty()) {
            List<Integer> currCell = paths.poll();
            int currRow = currCell.get(0), currCol = currCell.get(1);
            int currStep = currCell.get(2);

            for(int[] dir: directions) {
                int nextRow = currRow + dir[0];
                int nextCol = currCol + dir[1];
                int nextStep = currStep + 1;

                List<Integer> nextCell  = new ArrayList<>();
                nextCell.add(nextRow);
                nextCell.add(nextCol);
                nextCell.add(nextStep);

                if(isInvalidCell(nextCell, nextRow, 
                  nextCol, mazeCopy)) {
                    continue;
                }

                if(nextRow == 0 || nextRow == m-1 || 
                nextCol == 0 || nextCol == n-1) {
                    return nextStep;
                }

                paths.add(nextCell);
                mazeCopy[nextRow][nextCol] = '+';
            }
        }

        return -1;
    }

    private boolean isInvalidCell(List<Integer> cell, int row, 
int col, char[][] maze) {
        int m = maze.length, n = maze[0].length;
        if(row < 0 || col < 0 || row >= m || 
          col >= n || maze[row][col] == '+') {
            return true;
        }

        return false;
    }
}

Time Complexity: O(m*n)
    - m = number of rows in matrix
    - n = number of cols in matrix
Space Complexity: O(m*n)
    - m = number of rows in matrix
    - n = number of cols in matrix

You can find the link to the GitHub repo for this question here: 1926. Nearest Exit from Entrance in Maze.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian