Title:

Find All Unique Paths

Specification:

A robot is located at the top-left corner of a m x n grid.
The robot can only move either down or right at any point in time.
The robot is trying to reach the bottom-right corner of the grid.
How many possible unique paths are there?

Constarints:
1 <= m, n <= 100
It's guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.

Examples:

Example 1:

Input: m = 3, n = 2
Output: 3

Explanation: From the top-left corner,
there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

Initial Code and Signature:

``` public interface PathFinder { public int uniquePaths(int m, int n); } ```

Algorithm:

1. Start from the destination cell and move upward over the diameter of the matrix.
2. Count unique paths from the cell to destination.
3. Count unique paths from all the cells that are in the same row with the cell.
4. Count unique paths from all the cells that are in the same column with the cell.
5. # unique paths from a cell to the destination = # unique paths from the right neighbor + # unique path from the bottom neighbor.
6. Go the next cell on the diameter of the matrix.
7. Return the # unique paths from cell [0][0] to the destination.

Run-Time Analysis:

GitHub Project:

Code:

``` /** * * @author Mahsa Sadi * * @since 2020 - 04 - 01 * * License: Creative Commons * * Copyright by Mahsa Sadi * * */ public class PathFinderV2 implements PathFinder { /** * Problem: Find All Unique Paths * * Description: * * A robot is located at the top-left corner of a m x n grid. * The robot can only move either down or right at any point in time. * The robot is trying to reach the bottom-right corner of the grid. * How many possible unique paths are there? * * * * Solution: * * 1- Start from the destination cell and move upward over the diameter of the matrix. * 2- Count unique paths from the cell to destination. * 3- Count unique paths from all the cells that are in the same row with the cell. * 4- Count unique paths from all the cells that are in the same column with the cell. * * # unique paths from a cell to the destination * = # unique paths from the right neighbor * + # unique path from the bottom neighbor. * * 5- Go the next cell on the diameter of the matrix. * * 6-Return the # unique paths from cell [0][0] to the destination. * */ int[][] numberOfUniquePathsFromNode; int numberOfRows; int numberOfColumns; @Override public int uniquePaths(int m, int n) { numberOfUniquePathsFromNode = new int[m][n]; numberOfRows = m; numberOfColumns = n; int x = numberOfRows - 1; int y = numberOfColumns - 1; while (x >= 0 && y >= 0) { for (int i = x; i >= 0; i--) countPathsFromNode(i, y); for (int j = y - 1; j >= 0; j--) countPathsFromNode(x, j); x--; y--; } return numberOfUniquePathsFromNode[0][0]; } public void countPathsFromNode(int x, int y) { if (x == numberOfRows - 1) { if (y == numberOfColumns - 1) numberOfUniquePathsFromNode[x][y] = 1; else numberOfUniquePathsFromNode[x][y] = numberOfUniquePathsFromNode[x][y + 1]; } else if (y == numberOfColumns - 1) numberOfUniquePathsFromNode[x][y] = numberOfUniquePathsFromNode[x + 1][y]; else numberOfUniquePathsFromNode[x][y] = numberOfUniquePathsFromNode[x + 1][y] + numberOfUniquePathsFromNode[x][y + 1]; } } ```