Unique Paths

A robot is located at the top-left corner of a m*n grid(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?

Example 1:

start   x       x       x       x       x       x

x       x       x       x       x       x       x

x       x       x       x       x       x   Finish

 

Solution: Approach 1

 

class Solution:  
 
      # o(n * m) time complexity | O(n * m) space complexity
      def unique_paths(self, m, n):
            g = [[0 for c in range(n +1)] for r in range(m + 1)]
            g[m-1][n] =1
 
            for r in range(m-1, -1, -1):
                  for c in range(n-1, -1, -1):
                        g[r][c] = g[r+1][c] + g[r][c+1]
            return g[0][0]
 
 
 

Solution: Approach 2

class Solution:
 
      # o(n * m) time complexity | O(n) space complexity where n is the lengthROW of a row
      def unique_paths(self, m:int, n:int)-> int:
            row =[1] * n
 
            for i in range(m-1):
                  newRow =[1] * n
                  for j in range(n-2, -1, -1):
                        newRow[j] = newRow[j + 1] + row[j]
                   row = newRow
            return row[0]
 

Testing

 
Here's a unit test for the code provided above. Use it for testing either of the approaches provided.
 
class TestUniquePaths(unittest.TestCase):
 
      def __init__(self, methodName: str = "runTest") -> None:
            super().__init__(methodName)
            self.sol = Solution()
 
      def test_unique_paths(self):
            self.assertEqual(28, self.sol.uniquePaths(3, 7))
 
if __name__=="__main__":
unittest.main()

 

Join the Discussion

No comments yet. Be the first to share your thoughts!