D
DevExCode

LeetCode 490: The Maze Solution

Master LeetCode problem 490 (The Maze), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

Problem Explanation

Explanation:

The problem "The Maze" can be solved using a breadth-first search (BFS) algorithm. The idea is to start from the starting position and explore all possible directions until we reach the destination. We will keep track of the visited positions to avoid revisiting them.

Here are the steps to solve the problem:

  1. Initialize a queue to store the positions to be explored.
  2. Add the starting position to the queue.
  3. While the queue is not empty:
    • Remove the position from the front of the queue.
    • Check if this position is the destination. If it is, return true.
    • Explore all possible directions (up, down, left, right) from the current position.
    • Move in each direction until hitting a wall or the edge of the maze.
    • If the destination is reached in any direction, add the new position to the queue.
  4. If the queue becomes empty and the destination is not reached, return false.

The time complexity of this algorithm is O(mn) where m is the number of rows and n is the number of columns in the maze. The space complexity is also O(mn) due to the queue used for BFS.

: :

Solution Code

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int m = maze.length, n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(start);
        visited[start[0]][start[1]] = true;
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            
            if (curr[0] == destination[0] && curr[1] == destination[1]) {
                return true;
            }
            
            for (int[] dir : dirs) {
                int x = curr[0] + dir[0];
                int y = curr[1] + dir[1];
                
                while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0) {
                    x += dir[0];
                    y += dir[1];
                }
                
                if (!visited[x - dir[0]][y - dir[1]]) {
                    queue.offer(new int[]{x - dir[0], y - dir[1]});
                    visited[x - dir[0]][y - dir[1]] = true;
                }
            }
        }
        
        return false;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 490 (The Maze)?

This page provides optimized solutions for LeetCode problem 490 (The Maze) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 490 (The Maze)?

The time complexity for LeetCode 490 (The Maze) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 490 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 490 in Java, C++, or Python.

Back to LeetCode Solutions