Count Paths on a Game Board
You're given a game board that has m x n squares on it, represented by an m x n array. Write a method -
Note:
Your method should output the result in a reasonable amount of time for large values of m and n. If you're thinking of using DFS, consider the tree depth and branching factor for
countPaths that takes in m and n and returns the number of possible paths from the top left corner to the bottom right corner. Only down and right directions of movement are permitted. Note:
Your method should output the result in a reasonable amount of time for large values of m and n. If you're thinking of using DFS, consider the tree depth and branching factor for
m and n > 15!m = number of rows, n = number of columnsExample:
countPaths(m = 2, n = 2) => 2
as on the following 2x2 Board, the two paths are A->C->D and A->B->D
A B
C D
Need a hand? Try out these hints, one at a time.
This problem may appear trivial at first. In fact, it has a one line recursive solution of this form :
This will, however, result in an exponential time complexity and will most probably timeout for large values of
if(m==1 || n==1) return 1;
else return countPaths(m-1, n) + countPaths(m, n-1);
This will, however, result in an exponential time complexity and will most probably timeout for large values of
m and n. If you consider the recursion tree for the above solution, you'll notice many overlapping problems. There are many recursive branches branching off each board cell, with inevitable overlap between the branches of nearby cells. Since the direction of movement is heavily restricted, consider using Dynamic Programming with a memo matrix that stores the number of solutions for each cell as you move across the board.
1) Create a 2D m x n
2) Fill the first row and column of
3) Traverse
4) The last cell of the game board holds the answer to the problem.
memo pad matrix : int memo[][] = new int[m][n]2) Fill the first row and column of
memo with 1s. This is because the direction of movement is limited to down and right when moving from start to finish. If you reverse the direction of movement and think about the number of paths from a cell to the starting cell, all cells in the first row have exactly 1 path (straight left) and all cells in the first column have exactly one path as well (straight up). So the strategy here is to build on this knowledge as you move across and down memo. As you reach the last cell, it will eventually have the number of paths to the starting cell.3) Traverse
memo in a loop starting from memo[1][1], while filling in each cell using the information from cells directly above and to the left of the current cell. To see why this works - consider memo[0][0], which is originally 1. Now, if you're at memo[1][1], you can either move up a row and then follow the path left or move left a column and follow the path above. Therefore, you must sum memo[0][1] and memo[1][0] to get the total number of paths possible :
for (int i = 1; i < m; i++){
for (int j = 1; j < n; j++){
memo[i][j] = memo[i-1][j] + memo[i][j-1];
}
}
4) The last cell of the game board holds the answer to the problem.
public int countPaths(int m, int n){
}
This Coding Interview Question is available with an answer in the following programming languages :
C
Java
Python