How hard is LeetCode 1301. Number of Paths with Max Score?

LeetCode 1301. Number of Paths with Max Score is rated Hard on LeetCode.

What topics does LeetCode 1301. Number of Paths with Max Score cover?

LeetCode 1301. Number of Paths with Max Score is tagged Array, Dynamic Programming and Matrix on LeetCode.

Number of Paths with Max Score — LeetCode 1301 Python Solution

HardArrayDynamic ProgrammingMatrix

Problem: #1301
Pattern: Matrix and Grid
Reading time: 4 min
Source: leetcode.com

The problem

You are given a square board of characters. You can move on the board starting at the bottom right square marked with the character 'S'.

Example

Input: board = ["E23","2X2","12S"]
Output: [7,1]

Python solution

Python

class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        def update(i, j, x, y):
            if x >= n or y >= n or f[x][y] == -1 or board[i][j] in "XS":
                return
            if f[x][y] > f[i][j]:
                f[i][j] = f[x][y]
                g[i][j] = g[x][y]
            elif f[x][y] == f[i][j]:
                g[i][j] += g[x][y]

        n = len(board)
        f = [[-1] * n for _ in range(n)]
        g = [[0] * n for _ in range(n)]
        f[-1][-1], g[-1][-1] = 0, 1
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                update(i, j, i + 1, j)
                update(i, j, i, j + 1)
                update(i, j, i + 1, j + 1)
                if f[i][j] != -1 and board[i][j].isdigit():
                    f[i][j] += int(board[i][j])
        mod = 10**9 + 7
        return [0, 0] if f[0][0] == -1 else [f[0][0], g[0][0] % mod]

Complexity

Measure	Complexity
Time	O(n·m) (typical)
Space	O(n·m) or optimized auxiliary

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1301. Number of Paths with Max Score is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1301. Number of Paths with Max Score?: LeetCode 1301. Number of Paths with Max Score is rated Hard on LeetCode.
What topics does LeetCode 1301. Number of Paths with Max Score cover?: LeetCode 1301. Number of Paths with Max Score is tagged Array, Dynamic Programming and Matrix on LeetCode.