4
\$\begingroup\$

This is based on this leetcode question. I get the correct answer, but I know it could be much, much cleaner. I also know there is supposed to be an O(n) space solution, but I'm not sure how to implement cleanly.

It is a dynamic programming problem, I tried to add some helpful code comments, I know it's pretty messy so thank you for your review.

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        #initialize memoization array
        memo = [[-1 for i in range(len(obstacleGrid[0]))] for j in range(len(obstacleGrid))]


        #add known values before any calculation (last row and last column)
        memo[len(memo)-1][len(memo[0])-1] = 1
        for i in range(len(memo[0])-2,-1,-1):
            if obstacleGrid[len(memo)-1][i] != 1:
                memo[len(memo)-1][i] = memo[len(memo)-1][i+1]
            else:
                memo[len(memo)-1][i] = 0 
        
        for j in range(len(memo)-2,-1,-1):
            if obstacleGrid[j][len(memo[0])-1] != 1:
                memo[j][len(memo[0])-1] = memo[j+1][len(memo[0])-1]
            else:
                memo[j][len(memo[0])-1] = 0
        
        if obstacleGrid[len(memo)-1][len(memo[0])-1] == 1:
            return 0 
        
        #does calculations
        def helper(row,col):
            nonlocal memo
            if obstacleGrid[row][col] == 1:
                return 0 
            if memo[row][col] == -1:
                memo[row][col] = helper(row+1,col) + helper(row,col+1)
            return memo[row][col]
        
        return helper(0,0)
\$\endgroup\$

2 Answers 2

Reset to default
3
\$\begingroup\$

Nice solution, few suggestions:

  • Duplicated code: the functions len(memo) and len(memo[0]) are called several times. When working with a matrix is common to call m the number of rows (len(memo)) and n the number of columns (len(memo[0])). This can help to reduce the duplicated code. As @Manuel mentioned in the comments, m and n are also defined in the problem description.

  • Last element of a list: instead of memo[len(memo)-1] you can use memo[-1].

  • Input validation: this input validation:

    if obstacleGrid[len(memo)-1][len(memo[0])-1] == 1:
    return 0

    is done too late in the code, after the memo matrix is fully built. Better to move it up at the beginning of the function. BTW, with the previous suggestion, it can be shortened to:

    if obstacleGrid[-1][-1] == 1:
    return 0

  • Naming: the row is called row in the helper function and j in the rest of the code. Same for the column. Use the same name to be consistent.

  • Throwaway variables: in the initialization of memo:

    memo = [[-1 for i in range(len(obstacleGrid[0]))] for j in range(len(obstacleGrid))]

    the variables i and j are not used. They can be replaced with _.

  • Type hints: the helper function is missing the type hints.

  • LRU cache: there is a handy annotation that does the memoization automatically, @lru_cache. Or the unbounded @cache in Python 3.9.

An example using @lru_cache:

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
    m = len(obstacleGrid)
    n = len(obstacleGrid[0])

    if obstacleGrid[-1][-1] == 1:
        return 0

    @lru_cache(maxsize=None)
    def helper(row: int, col: int) -> int:
        if row == m - 1 and col == n - 1:
            return 1
        if row < m and col < n:
            if obstacleGrid[row][col] == 1:
                return 0
            return helper(row + 1, col) + helper(row, col + 1)
        return 0

    return helper(0, 0)

For dynamic programming solutions, you can have a look at the "Solution" section or "Discussion" section using tags python and dynamic programming.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ This is exactly what I was looking for I always struggle with these 2-D DP problems, this will make it a lot easier, thanks! \$\endgroup\$ Commented Apr 11, 2021 at 16:19
1
\$\begingroup\$

For O(n) space, I think you need to switch from your top-down DP to bottom-up DP. That lets you control the evaluation order so you can for example go row by row, and store only the numbers of paths for the current row.

To simplify things, start with an imaginary row above the grid and say you have one path right above the real start cell and zero paths above the rest. Then just update these numbers by going through the grid's rows.

def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
    paths = [1] + [0] * (len(obstacleGrid[0]) - 1)
    for row in obstacleGrid:
        for j, obstacle in enumerate(row):
            if j:
                paths[j] += paths[j - 1]
            if obstacle:
                paths[j] = 0
    return paths[-1]

Btw, you're not O(n^2) but O(mn).

\$\endgroup\$
3
  • \$\begingroup\$ Just to test my understanding would the first row then be set to all 1's in the first iteration of the row loop? \$\endgroup\$ Commented Apr 11, 2021 at 16:19
  • 1
    \$\begingroup\$ @JosephGutstadt Only if there are no obstacles. If there are obstacles, it would be ones until the first obstacle, and zeros starting at the first obstacle. That's the advantage of that imaginary extra row: I don't have to duplicate the logic of handling obstacles, like you do in your initialization. \$\endgroup\$ Commented Apr 11, 2021 at 16:32
  • \$\begingroup\$ Ahhh, very nice, that was my next question, Thank you \$\endgroup\$ Commented Apr 11, 2021 at 17:45

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.