Search in a Maze
Problem Statement
Given a N×N maze represented as a 2D grid where 1 means open path and 0 means wall, find a path from the top-left corner (0,0) to the bottom-right corner (N-1, N-1). You can move in 4 directions: Up, Down, Left, Right.
Example:
- Input:
maze = [[1, 0, 0, 0], [1, 1, 0, 1], [0, 1, 0, 0], [1, 1, 1, 1]] - Output:
[[1,0,0,0],[1,1,0,0],[0,1,0,0],[0,1,1,1]](one valid path)
Noob-Friendly Explanation
Imagine you're a mouse in a maze trying to reach the cheese at the bottom-right corner. You start at the top-left. Some cells are walls (0) and some are open paths (1). You can move up, down, left, or right, but only through open cells.
You try each direction. If you hit a wall or go out of bounds, you backtrack (go back) and try another direction. It's like solving a real maze — you keep trying paths until you find one that works.
Approach 1: Brute Force (Backtracking - All Paths)
Intuition
Try every possible path from source to destination using recursion. At each cell, try all 4 directions. Mark cells as visited to avoid revisiting. This explores ALL possible paths.
Algorithm
- Start from (0, 0).
- If current cell is destination, save the path.
- Try all 4 directions.
- If the next cell is valid (in bounds, open, not visited), move there.
- Backtrack if no direction works.
import java.util.ArrayList;
import java.util.List;
public class MazeBruteForce {
static int[] dx = {-1, 1, 0, 0}; // Up, Down, Left, Right
static int[] dy = {0, 0, -1, 1};
static String[] dir = {"U", "D", "L", "R"};
public static List<String> findAllPaths(int[][] maze) {
int n = maze.length;
List<String> paths = new ArrayList<>();
if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return paths;
boolean[][] visited = new boolean[n][n];
solve(maze, 0, 0, n, visited, new StringBuilder(), paths);
return paths;
}
static void solve(int[][] maze, int row, int col, int n,
boolean[][] visited, StringBuilder path, List<String> paths) {
if (row == n - 1 && col == n - 1) {
paths.add(path.toString());
return;
}
visited[row][col] = true;
for (int i = 0; i < 4; i++) {
int newRow = row + dx[i];
int newCol = col + dy[i];
if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n
&& maze[newRow][newCol] == 1 && !visited[newRow][newCol]) {
path.append(dir[i]);
solve(maze, newRow, newCol, n, visited, path, paths);
path.deleteCharAt(path.length() - 1); // backtrack
}
}
visited[row][col] = false; // backtrack
}
public static void main(String[] args) {
int[][] maze = {
{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
System.out.println(findAllPaths(maze));
}
}Complexity Analysis
- Time Complexity: O(2^(N^2)) — in the worst case, we explore exponentially many paths.
- Space Complexity: O(N^2) — for the visited array and recursion stack.
Approach 2: Optimal (BFS — Shortest Path)
Intuition
Use BFS to find the shortest path from source to destination. BFS guarantees the shortest path in an unweighted grid because it explores level by level.
Algorithm
- Start BFS from (0, 0).
- Use a queue storing (row, col) and the path so far.
- For each cell, try all 4 directions.
- If a direction leads to a valid, unvisited, open cell, add it to the queue.
- Return the path when we reach (N-1, N-1).
import java.util.LinkedList;
import java.util.Queue;
public class MazeOptimal {
public static String findShortestPath(int[][] maze) {
int n = maze.length;
if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return "";
int[] dx = {-1, 1, 0, 0};
int[] dy = {0, 0, -1, 1};
String[] dir = {"U", "D", "L", "R"};
boolean[][] visited = new boolean[n][n];
Queue<int[]> queue = new LinkedList<>(); // {row, col}
Queue<String> pathQueue = new LinkedList<>();
visited[0][0] = true;
queue.add(new int[]{0, 0});
pathQueue.add("");
while (!queue.isEmpty()) {
int[] cell = queue.poll();
String path = pathQueue.poll();
if (cell[0] == n - 1 && cell[1] == n - 1) {
return path;
}
for (int i = 0; i < 4; i++) {
int newRow = cell[0] + dx[i];
int newCol = cell[1] + dy[i];
if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n
&& maze[newRow][newCol] == 1 && !visited[newRow][newCol]) {
visited[newRow][newCol] = true;
queue.add(new int[]{newRow, newCol});
pathQueue.add(path + dir[i]);
}
}
}
return ""; // no path found
}
public static void main(String[] args) {
int[][] maze = {
{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
System.out.println(findShortestPath(maze)); // DDRDR or similar
}
}Complexity Analysis
- Time Complexity: O(N^2) — each cell is visited at most once.
- Space Complexity: O(N^2) — for the visited array and queue.