Coding Week 9 - Tree Flashcards
Problem 1) The Maze
There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the m x n maze, the ball’s start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return true if the ball can stop at the destination, otherwise return false.
You may assume that the borders of the maze are all walls (see examples).
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
Algorithm:
We can view the given search space in the form of a tree. The root node of the tree represents the starting position. Four different routes are possible from each position i.e. left, right, up or down. These four options can be represented by 4 branches of each node in the given tree. Thus, the new node reached from the root traversing over the branch represents the new position occupied by the ball after choosing the corresponding direction of travel.
In order to do this traversal, one of the simplest schemes is to undergo depth first search. In this case, we choose one path at a time and try to go as deep as possible into the levels of the tree before going for the next path. In order to implement this, we make use of a recursive function dfs(maze, start, destination, visited). This function takes the given maze array, the start position and the destination position as its arguments along with a visited array.
visited array is a 2-D boolean array of the same size as that of maze. A True value at visited[i][j] represents that the current position has already been reached earlier during the path traversal. We make use of this array so as to keep track of the same paths being repeated over and over. We mark a True at the current position in the visited array once we reach that particular position in the maze.
From every start position, we can move continuously in either left, right, upward or downward direction till we reach the boundary or a wall. Thus, from the start position, we determine all the end points which can be reached by choosing the four directions. For each of the cases, the new endpoint will now act as the new start point for the traversals. The destination, obviously remains unchanged. Thus, now we call the same function four times for the four directions, each time with a new start point obtained previously.
If any of the function call returns a True value, it means we can reach the destination.
Question 1)
What do you think will be the time and auxiliary space of the above approach?
(M -> number of rows and N -> number of columns)
A) Time - O(M * N), Space - O(M * N)
B) Time - O(M * N), Space - O(M + N)
C) Time - O(M ^ N), Space - O(M + N)
D) Time - O(M + N), Space - O(M + N)
A) Time - O(M * N), Space - O(M * N)
We will have to completely traverse the maze in the worst case. Hence, the time complexity will be O(M * N).
We will use an visited array of size M * N. Hence, the space complexity will be O(M * N).
