62 Unique Paths

A robot is located at the top-left corner of amxngrid (marked 'Start' in the diagram below).

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 (marked 'Finish' in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note :m and n will be at most 100.

Approach 1: Brute Force

The Idea: One solution is to look options we have available at every cell (i,j). Since we have the option to only move down or right this simplifies the problem. For example, if we are in row 2, and there are 3 rows, then we only have the option to move down another row. Likewise, if we are on the 4th column and there are total of 7 columns, then we can move to the right 3 more places. In general, the cell we are under will provide us with available options we have left. Finally, the available paths can summarizes as the root to leaf paths, and the total number of paths are then just the number of leaves. There some obvious improvements here, but the purpose was just to demonstrate a brute force approach.

import queue

class Node:
    def __init__(self, count_D, count_R):
        self.count_D = count_D
        self.count_R = count_R
        self.D = None
        self.R = None


class Solution:

    def __countNumLeaves(self, root):
        """
        :param root: Node
        :return: int
        """
        if root is not None:
            if root.D is None and root.R is None:
                return 1
            return self.__countNumLeaves(root.D) + self.__countNumLeaves(root.R)
        return 0

    def uniquePaths(self, rows, cols):
        """
        :type m: int
        :type n: int
        :rtype: int
        """

        q = queue.Queue()
        root = Node(rows-1, cols-1)
        q.put(root)

        while not q.empty():
            front = q.get()
            if front.count_D > 0:
                front.D = Node(front.count_D-1, front.count_R)
                q.put(front.D)
            if front.count_R > 0:
                front.R = Node(front.count_R-1, front.count_D)
                q.put(front.R)

        return self.__countNumLeaves(root)

Approach 2: Dynamic Programming

Complexity: O(n*m) time and space. Space can actually be improved to be linear because if you think about it, the only cells we are interested in are the previous cells from above and to the right - and as long as we maintain a previous vector that consistently gets updated, we are good.

int uniquegrids(int m, int n) {
    vector<vector<int> > grid(m, vector<int>(n, 1));
    for (int i = 1; i < m; i++)
        for (int j = 1; j < n; j++)
            grid[i][j] = grid[i - 1][j] + grid[i][j - 1];
    return grid[m - 1][n - 1];
}

Last updated