The Maze I

/*
BFS Solution

Time Complexity:
O(V + E)
V = number of vertices traveresed = m*n
E = number of edges * time to find each edge = m*n * max(m,n)
TC = O(mn + mn*max(m,n)) = O(mn*max(m,n))

Space Complexity = O(m*n) - visited array + queue can take m*n space in worst case.
*/
class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        if (maze == null || maze.length == 0 || maze[0].length == 0) {
            return false;
        }
        if (start == null || destination == null || start.length != 2 || destination.length != 2) {
            return false;
        }
        if (maze[start[0]][start[1]] == 1 || maze[destination[0]][destination[1]] == 1) {
            return false;
        }
        if (start[0] == destination[0] && start[1] == destination[1]) {
            return true;
        }

        int rowNum = maze.length;
        int colNum = maze[0].length;

        boolean[][] visited = new boolean[rowNum][colNum];
        int[][] directions = new int[][] {{-1,0},{1,0},{0,-1},{0,1}};
        Queue<int[]> queue = new LinkedList<>();

        queue.offer(start);
        visited[start[0]][start[1]] = true;

        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            for (int[] dir : directions) {
                int x = point[0];
                int y = point[1];
                while (x >= 0 && x < rowNum && y >= 0 && y < colNum && maze[x][y] == 0) {
                    x += dir[0];
                    y += dir[1];
                }

                // Back to valid point;
                x -= dir[0];
                y -= dir[1];
                if (visited[x][y] == true) {
                    continue;
                }
                visited[x][y] = true;
                if (x == destination[0] && y == destination[1]) {
                    return true;
                }
                queue.offer(new int[]{x,y});
            }
        }
        return false;
    }
}

/*
DFS Solution

Time Complexity:
O(V + E)
V = number of vertices traveresed = m*n
E = number of edges * time to find each edge = m*n * max(m,n)
TC = O(mn + mn*max(m,n)) = O(mn*max(m,n))

Space Complexity = O(m*n) - visited array + queue can take m*n space in worst case.
*/
// class Solution {
//     public boolean hasPath(int[][] maze, int[] start, int[] destination) {
//         if (maze == null || maze.length == 0 || maze[0].length == 0) {
//             return false;
//         }
//         if (start == null || destination == null || start.length != 2 || destination.length != 2) {
//             return false;
//         }
//         if (maze[start[0]][start[1]] == 1 || maze[destination[0]][destination[1]] == 1) {
//             return false;
//         }
//         if (start[0] == destination[0] && start[1] == destination[1]) {
//             return true;
//         }

//         boolean[][] visited = new boolean[maze.length][maze[0].length];
//         int[][] directions = new int[][] {{-1,0},{1,0},{0,-1},{0,1}};

//         return dfsHelper(maze, start, destination, visited, directions);
//     }

//     public boolean dfsHelper(int[][] maze, int[] start, int[] destination, boolean[][] visited, int[][] directions) {
//         if (visited[start[0]][start[1]] == true) {
//             return false;
//         }
//         if (start[0] == destination[0] && start[1] == destination[1]) {
//             return true;
//         }

//         visited[start[0]][start[1]] = true;

//         for (int[] dir : directions) {
//             int x = start[0];
//             int y = start[1];
//             while (x >= 0 && x < maze.length && y >= 0 && y < maze[0].length && maze[x][y] == 0) {
//                 x += dir[0];
//                 y += dir[1];
//             }
//             // Back to valid point
//             x -= dir[0];
//             y -= dir[1];
//             if (dfsHelper(maze, new int[] {x,y}, destination, visited, directions)) {
//                 return true;
//             }
//         }
//         return false;
//     }
// }