Revisions to Unique Paths II, dynamic programming problem, O(n^2) time, O(n^2) space

deleted 6 characters in body; deleted 1 character in body

Source Link

edited Apr 12, 2021 at 0:32

Marc

5.7k
2
15
35

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

    if obstacleGrid[m obstacleGrid[- 1][n 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)

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

    if obstacleGrid[m - 1][n - 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)

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)

added 53 characters in body

Source Link

edited Apr 11, 2021 at 10:59

Marc

5.7k
2
15
35

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. Another alternative, which I find more readable, is rows and cols.
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].
Last element of a list: instead of memo[len(memo)-1] you can use memo[-1].
Input validation: this input validation:
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:
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.
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:
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 _.
the variables i and j are not used. They can be replaced with _.
Type hints: the helper function is missing the type hints.
Type hints: the helper function is missing the type hints.
LRU cache: there is a handy annotation that does the memoization automatically, @lru_cache.
LRU cache: there is a handy annotation that does the memoization automatically, @lru_cache. Or the unbounded @cache in Python 3.9.

def uniquePathsWithObstaclesuniquePathsWithObstacles2(self, obstacleGrid: List[List[int]]) -> int:
    rowsm = len(obstacleGrid)
    colsn = len(obstacleGrid[0])

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

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

    return helper(0, 0)

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. Another alternative, which I find more readable, is rows and cols.
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.

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

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

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

    return helper(0, 0)

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.

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

    if obstacleGrid[m - 1][n - 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)

Source Link

answered Apr 11, 2021 at 4:18

Marc

5.7k
2
15
35

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. Another alternative, which I find more readable, is rows and cols.
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.

An example using @lru_cache:

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

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

    @lru_cache
    def helper(row: int, col: int) -> int:
        if 0 <= row < rows and 0 <= col < cols:
            if row == rows - 1 and col == cols - 1:
                return 1
            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.

Stack Exchange Network

Return to Answer