Problem

Maze puzzleA 1 in input matrix means “allowed”; 0 means “blocked”. Given such a matrix, find the route from the 1st quadrant to the last (n-1, n-1).

I would like to get some feedback to optimize and make this code cleaner. Also let me know if O(n!) is the complexity, where n is the dimension of the maze.

```
final class Coordinate {
private final int x;
private final int y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
public int getX() {
return x;
}
public int getY() {
return y;
}
}
public class Maze {
private final int[][] maze;
public Maze(int[][] maze) {
if (maze == null) {
throw new NullPointerException("The input maze cannot be null");
}
if (maze.length == 0) {
throw new IllegalArgumentException("The size of maze should be greater than 0");
}
this.maze = maze;
}
public List<Coordinate> solve() {
return getMazePath(0, 0, new Stack<Coordinate>());
}
private List<Coordinate> getMazePath(int row, int col, Stack<Coordinate> stack) {
assert stack != null;
stack.add(new Coordinate(row, col));
if ((row == maze.length - 1) && (col == maze[0].length - 1)) {
Coordinate[] coordinateArray = stack.toArray(new Coordinate[stack.size()]);
return Arrays.asList(coordinateArray);
}
for (int j = col; j < maze[row].length; j++) {
if ((j + 1) < maze[row].length && maze[row][j + 1] == 1) {
return getMazePath(row, j + 1, stack);
}
if ((row + 1) < maze.length && maze[row + 1][col] == 1) {
return getMazePath(row + 1, col, stack);
}
}
return Collections.emptyList();
}
public static void main(String[] args) {
int[][] m = { {1, 0, 0},
{1, 1, 0},
{0, 1, 1} };
Maze maze = new Maze(m);
for (Coordinate coord : maze.solve()) {
System.out.println(coord.getX() + " : " + coord.getY());
}
}
}
```

Solution

First of all I don’t think the time complexity is `O(n!)`

. You are doing DFS(unknowingly). So the time complexity would be O(n + m) and AFAIK you can’t solve maze problem less than that unless you are using BFS. But nevertheless it will not make any difference.

Now your code has some bug, I think you didn’t consider that way and it’s ok if you are a beginner like me. Try to change the maze matrix to

```
int[][] m = {{1, 1, 1},
{1, 0, 1},
{1, 1, 0},
{0, 1, 1}};
```

and you will get the picture. Maze can be solved but still it’s not printing anything.

So what is the solution? **BACK-TRACK**.

Moreover you are only taking account of possibilities of going *right* and *down*, why not *up* and *left*?

You have hard-coded that the start point will be always (0,0) and end point will be (N-1, N-1)… yeah your puzzle says that but this will not be same for every puzzle right? So think of a general solving technique…

**SPOILER ALERT**

## Code Cleaning Tips

`getMazePath`

method can be cleaned. In 1st`if`

you are checking if you have reached the goal or not. Now move the checking condition to another method and return`true`

if you have reached the goal.- In for loop(no need of this if you are using recursion) you are checking if
*you are in the maze*and*path exists or not*… see how you are repeating yourself for every condition… think of a general solution. - No need for maintaining a
`Stack`

, since you are not using any of Stack’s method but only`add`

, which you can also use with a`List`

. - Override
`toString`

method in`Coordinate`

class. And get rid of long`S.o.p`

s.

Good Luck!

Your logic is just not correct, with the for-loop. Consider the following maze:

```
1000001
0000001
0000001
0000001
```

Your code will find a “solution” by jumping to the upper-right, then taking a path down to the finish.

Fix that, and the issues raised by @tintinmj, and then we might be able to analyze the complexity. Until then, it would be a meaningless discussion.