1301. Number of Paths with Max Score


Problem Description

In this problem, you're given a board represented as a square grid of characters where each cell contains either a character 'S' (start), 'E' (end), a digit ('1' to '9'), or an 'X' which represents an obstacle. Your task is to move from the bottom right corner of the board (marked with 'S') to the top left corner (marked with 'E'), along the way collecting as many points as possible. You can only move up, left, or diagonally up-left at each step. You cannot move through an obstacle.

Your goal is not only to find the maximum sum of numeric characters you can collect on your way to the 'E' but also to count how many different paths can yield that maximum sum. Because the result could be very large, the number of paths should be returned modulo (10^9 + 7). If no such path exists because obstacles block the way, the result should be [0, 0].

Intuition

For the solution, we employ dynamic programming to keep track of two key pieces of information at each cell (i, j) in the grid:

  1. f[i][j] represents the maximum sum one can collect ending at that cell.
  2. g[i][j] represents the number of paths to that cell which yield the maximum sum.

To compute f[i][j] and g[i][j], we look at the three nearest neighbors where we could have come from: directly below (i+1, j), directly to the right (i, j+1), and diagonally below-right (i+1, j+1). We then update f[i][j] to the maximum of these three values, and update g[i][j] to the sum of the number of paths from these neighbors - but only if this doesn't take us through an obstacle, and only if f[i][j] actually gets updated, ensuring we don't count invalid or suboptimal paths.

The algorithm starts from the end cell (bottom right, marked 'S') which is initialized to a sum of 0 and a path count of 1 (as the journey starts there, there is 1 trivial path that stays at 'S'). We then iterate through the grid in reverse order, from bottom-right to top-left, filling out the f and g matrices based on the mentioned rules.

The final answer will be the contents of f[0][0] and g[0][0] at the end, which contain the maximum sum and the number of those optimal paths (modulo (10^9 + 7)), as by then all paths that reach the 'E' cell will have been considered. If f[0][0] is still -1 at the end, it means there was no valid path from 'S' to 'E', and [0, 0] should be returned.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution implements a bottom-up dynamic programming approach to solve the problem.

First, two matrices f and g of the same size as the input board are initialized. f[i][j] is initialized to -1 to represent an unprocessable or unreachable cell, except for f[n-1][n-1] which is initialized to 0 because that's the starting point (bottom-right corner). Similarly, g[i][j] is initialized to 0 for all cells except g[n-1][n-1], which is set to 1, representing that there is exactly one way to start the path from 'S'.

The function update(i, j, x, y) is crucial to this implementation. It checks if a neighbor cell is valid (not out of bounds and not an obstacle) and, if so, whether it can contribute to the path to cell (i, j). If the sum f[x][y] from a neighboring cell is higher than the current f[i][j], it means we've found a better path to cell (i, j), so f[i][j] and g[i][j] are updated accordingly. If f[x][y] is equal to f[i][j], then there is more than one optimal path to cell (i, j) and g[i][j] is incremented by the count of paths to (x, y).

The key steps in the algorithm are as follows:

  1. Initialize the f and g matrices.
  2. Iterate over the grid in reverse row-major order (bottom-right to top-left).
  3. For each cell (i, j), attempt to update its values based on the three potential previous cells: (i+1, j), (i, j+1), and (i+1, j+1).
  4. Add the numeric value of the current cell (if it's a digit) to f[i][j] after updating it based on its neighbors.
  5. After processing the entire board, check the values at f[0][0] and g[0][0]. If f[0][0] is not -1, this contains the maximum sum that can be obtained. g[0][0] contains the count of paths that yield this maximum sum modulo 10^9 + 7.
  6. If f[0][0] is still -1 (which means no path was found to 'E'), return [0, 0].

By using dynamic programming, the algorithm effectively collects the sums and counts the paths in a manner that avoids recalculating the same information repeatedly. This implementation allows it to handle the potential exponential nature of the problem in polynomial time, specifically, O(n^2) where n is the size of one dimension of the board.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small 3x3 board as our example:

1X 1 E
24 X 2
3S 3 X

We are starting from 'S' at (2, 0) and trying to reach 'E' at (0, 2), collecting points along the way. We can only move up, left, or diagonally up-left, and we cannot pass through 'X'.

We initialize two 3x3 matrices, f for sums and g for the number of paths:

f (initialized with -1):

1-1 -1 -1
2-1 -1 -1
3 0 -1 -1

g (initialized with 0, except g[2][0] which is 1):

1 0  0  0
2 0  0  0
3 1  0  0

Starting from 'S' at (2, 0), we move to (2, 1) which has '3'. Since '3' is a number, it can potentially add to the sum, and thus:

f[2][1] becomes 3 (f[2][0] + '3'), and g[2][1] becomes 1, as there is only one path from 'S' to this point.

Next, we cannot move from (2, 1) up or up-left since there are obstacles. The only option is to move left to (2, 2) where we encounter an 'X', which is inaccessible. So f[2][2] and g[2][2] remain unchanged at -1 and 0 respectively.

Moving to the second row (1, 0) and (1, 1), we cannot access these since they are both 'X'.

For (1, 2), which is '2', there are no points to collect from the row below because of the obstacle at (2, 2). Thus, it remains -1.

In the top row (0, 0) and (0, 1), these are inaccessible due to them being 'X' and not having a valid path from below or to the right.

Lastly, we reach (0, 2) where 'E' is located. Since the only possible path here is diagonally from (1, 1), which is also blocked by an 'X', we cannot reach 'E' successfully, and it remains at -1.

Final f and g matrices:

1-1 -1 -1
2-1 -1 -1
3 0  3 -1

Since our end goal 'E' at f[0][2] is still -1, this means there was no valid path to 'E'. Therefore, according to our approach, the answer is [0, 0], indicating no maximum sum and no valid paths from 'S' to 'E'.

Solution Implementation

1from typing import List
2
3class Solution:
4    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
5        def update_dp_values(i, j, next_i, next_j):
6            # Skip if out of bounds, cell is blocked, or the next cell is not reachable
7            if next_i >= board_size or next_j >= board_size or dp[next_i][next_j] == -1 or board[i][j] in "XS":
8                return
9            # Update maximum score and count if next cell has a greater score
10            if dp[next_i][next_j] > dp[i][j]:
11                dp[i][j] = dp[next_i][next_j]
12                count[i][j] = count[next_i][next_j]
13            # If scores are equal, increment path count
14            elif dp[next_i][next_j] == dp[i][j]:
15                count[i][j] += count[next_i][next_j]
16
17        board_size = len(board)
18        # Initialize DP arrays with -1, indicating unreachable cells
19        dp = [[-1] * board_size for _ in range(board_size)]
20        count = [[0] * board_size for _ in range(board_size)]
21        # Starting point with score 0 and 1 way to get here
22        dp[-1][-1], count[-1][-1] = 0, 1
23
24        # Traverse the board in reverse order
25        for i in range(board_size - 1, -1, -1):
26            for j in range(board_size - 1, -1, -1):
27                # Update dp values considering moves to the right, down, and diagonal
28                update_dp_values(i, j, i + 1, j)
29                update_dp_values(i, j, i, j + 1)
30                update_dp_values(i, j, i + 1, j + 1)
31                # If the current cell is a digit, add it to the score
32                if dp[i][j] != -1 and board[i][j].isdigit():
33                    dp[i][j] += int(board[i][j])
34        # Define modulo as per problem statement
35        mod = 10**9 + 7
36        # If start cell is unreachable return [0, 0], else return score and ways modulo mod
37        return [0, 0] if dp[0][0] == -1 else [dp[0][0], count[0][0] % mod]
38
1import java.util.List;
2import java.util.Arrays;
3
4class Solution {
5    private List<String> board;
6    private int boardSize;
7    private int[][] maxScoreGrid;
8    private int[][] pathsCountGrid;
9    private final int MOD = (int) 1e9 + 7; // Define the MOD constant for path count calculations
10
11    public int[] pathsWithMaxScore(List<String> board) {
12        boardSize = board.size();
13        this.board = board;
14        maxScoreGrid = new int[boardSize][boardSize];
15        pathsCountGrid = new int[boardSize][boardSize];
16
17        // Initialize grid values to -1 indicating unreachable cells
18        for (int[] row : maxScoreGrid) {
19            Arrays.fill(row, -1);
20        }
21
22        // Starting point at the bottom-right has a score of 0 and 1 path.
23        maxScoreGrid[boardSize - 1][boardSize - 1] = 0;
24        pathsCountGrid[boardSize - 1][boardSize - 1] = 1;
25
26        // Calculate maximum score and paths count from bottom-right to top-left
27        for (int i = boardSize - 1; i >= 0; --i) {
28            for (int j = boardSize - 1; j >= 0; --j) {
29                updateScoresAndPaths(i, j, i + 1, j);
30                updateScoresAndPaths(i, j, i, j + 1);
31                updateScoresAndPaths(i, j, i + 1, j + 1);
32                if (maxScoreGrid[i][j] != -1) {
33                    char cell = board.get(i).charAt(j);
34                    if (cell >= '0' && cell <= '9') {
35                        maxScoreGrid[i][j] += (cell - '0'); // Update score for numeric cells
36                    }
37                }
38            }
39        }
40
41        // Prepare and return the results
42        int[] result = new int[2];
43        if (maxScoreGrid[0][0] != -1) {
44            result[0] = maxScoreGrid[0][0]; // Maximum score
45            result[1] = pathsCountGrid[0][0]; // Number of paths with the maximum score
46        }
47        return result;
48    }
49
50    // Helper function to update the maximum score and paths count
51    private void updateScoresAndPaths(int currentRow, int currentCol, int prevRow, int prevCol) {
52        // Skip update if out of bounds, previous cell was unreachable, or current cell is blocked or the start
53        if (prevRow >= boardSize || prevCol >= boardSize
54            || maxScoreGrid[prevRow][prevCol] == -1
55            || board.get(currentRow).charAt(currentCol) == 'X'
56            || board.get(currentRow).charAt(currentCol) == 'S') {
57            return;
58        }
59      
60        // Update if a higher score is found
61        if (maxScoreGrid[prevRow][prevCol] > maxScoreGrid[currentRow][currentCol]) {
62            maxScoreGrid[currentRow][currentCol] = maxScoreGrid[prevRow][prevCol];
63            pathsCountGrid[currentRow][currentCol] = pathsCountGrid[prevRow][prevCol];
64        }
65        // If the current score is equal, add the paths count
66        else if (maxScoreGrid[prevRow][prevCol] == maxScoreGrid[currentRow][currentCol]) {
67            pathsCountGrid[currentRow][currentCol] = (pathsCountGrid[currentRow][currentCol] + pathsCountGrid[prevRow][prevCol]) % MOD;
68        }
69    }
70}
71
1#include <vector>
2#include <string>
3#include <cstring>
4using namespace std;
5
6class Solution {
7public:
8    vector<int> pathsWithMaxScore(vector<string>& board) {
9        int n = board.size(); // Get the size of the board
10        const int mod = 1e9 + 7; // Modulus for the number of ways to avoid integer overflow
11        int maxScores[n][n]; // Matrix to store the maximum scores up to each cell
12        int ways[n][n]; // Matrix to store the number of ways to reach each cell with the max score
13        // Initialize matrices with -1 for scores and 0 for ways
14        memset(maxScores, -1, sizeof(maxScores));
15        memset(ways, 0, sizeof(ways));
16
17        // Starting point (bottom-right of the board)
18        maxScores[n - 1][n - 1] = 0;
19        ways[n - 1][n - 1] = 1;
20
21        // Lambda function to update scores and ways for current (i, j) from neighbor (x, y)
22        auto update = [&](int i, int j, int x, int y) {
23            // Don't proceed if out of bounds, unreachable, or starting point
24            if (x >= n || y >= n || maxScores[x][y] == -1 || board[i][j] == 'X' || board[i][j] == 'S') {
25                return;
26            }
27            // If the score from neighbor (x, y) is greater, update current cell (i, j)
28            if (maxScores[x][y] > maxScores[i][j]) {
29                maxScores[i][j] = maxScores[x][y];
30                ways[i][j] = ways[x][y];
31            } 
32            // If equal, add to the number of ways
33            else if (maxScores[x][y] == maxScores[i][j]) {
34                ways[i][j] = (ways[i][j] + ways[x][y]) % mod;
35            }
36        };
37
38        // Iterate through the board in reverse order
39        for (int i = n - 1; i >= 0; --i) {
40            for (int j = n - 1; j >= 0; --j) {
41                // Update current cell based on the three possible moves
42                update(i, j, i + 1, j); // Down
43                update(i, j, i, j + 1); // Right
44                update(i, j, i + 1, j + 1); // Diagonally
45                // Add score for the current cell if it's a digit
46                if (maxScores[i][j] != -1 && board[i][j] >= '0' && board[i][j] <= '9') {
47                    maxScores[i][j] += (board[i][j] - '0');
48                }
49            }
50        }
51
52        // Prepare the answer in a vector
53        vector<int> answer(2);
54        if (maxScores[0][0] != -1) { // If the top-left cell is reachable
55            answer[0] = maxScores[0][0]; // Maximum score
56            answer[1] = ways[0][0]; // Number of ways
57        }
58        return answer;
59    }
60};
61
1// TypeScript does not have an exact equivalent of C++'s <vector>, so we'll use arrays.
2// The input board is an array of strings representing the game board.
3
4// Define constants for dimensions and modulus.
5const MOD = 1e9 + 7;
6
7// Function to calculate the paths with max score from the given board.
8function pathsWithMaxScore(board: string[]): number[] {
9    const n: number = board.length; // Get the size of the board.
10    let maxScores: number[][] = []; // Matrix to store the maximum scores to each cell.
11    let ways: number[][] = []; // Matrix to store the number of ways to reach each cell with the max score.
12
13    // Initialize the matrices.
14    for (let i = 0; i < n; i++) {
15        maxScores[i] = [];
16        ways[i] = [];
17        for (let j = 0; j < n; j++) {
18            maxScores[i][j] = -1; // Initialize scores with -1.
19            ways[i][j] = 0; // Initialize ways with 0.
20        }
21    }
22
23    // Starting point (bottom-right of the board).
24    maxScores[n - 1][n - 1] = 0;
25    ways[n - 1][n - 1] = 1;
26
27    // Lambda function to update scores and ways for the current cell from neighbor.
28    const update = (i: number, j: number, x: number, y: number) => {
29        // Don't proceed if out of bounds, unreachable, or at the starting point.
30        if (x >= n || y >= n || maxScores[x][y] === -1 || board[i][j] === 'X' || board[i][j] === 'S') {
31            return;
32        }
33        // If the score from the neighbor is greater, update the current cell.
34        if (maxScores[x][y] > maxScores[i][j]) {
35            maxScores[i][j] = maxScores[x][y];
36            ways[i][j] = ways[x][y];
37        }
38        // If the score is equal, add to the number of ways.
39        else if (maxScores[x][y] === maxScores[i][j]) {
40            ways[i][j] = (ways[i][j] + ways[x][y]) % MOD;
41        }
42    };
43
44    // Iterate through the board in reverse order to find max scores and ways.
45    for (let i = n - 1; i >= 0; --i) {
46        for (let j = n - 1; j >= 0; --j) {
47            // Update the current cell based on the three possible moves: down, right, and diagonally.
48            update(i, j, i + 1, j); // Down
49            update(i, j, i, j + 1); // Right
50            update(i, j, i + 1, j + 1); // Diagonally
51            // Add the score for the current cell if it's a digit.
52            if (maxScores[i][j] !== -1 && !isNaN(parseInt(board[i][j]))) {
53                maxScores[i][j] += parseInt(board[i][j]);
54            }
55        }
56    }
57
58    // Prepare the answer in an array.
59    let answer: number[] = [0, 0]; // Initialize answer with 0s for cases where the top-left cell is not reachable.
60    if (maxScores[0][0] !== -1) { // If the top-left cell is reachable.
61        answer[0] = maxScores[0][0]; // Maximum score.
62        answer[1] = ways[0][0]; // Number of ways.
63    }
64    return answer;
65}
66
67// Example usage:
68// const board: string[] = ['E23', '2X2', '12S'];
69// pathsWithMaxScore(board); // Should return the max score and number of ways to reach the end.
70

Time and Space Complexity

The provided code is designed to find the paths with the highest score on a board. Here's an analysis of its computational complexity:

Time Complexity

The main processing loop of the algorithm goes through the board which is an n x n grid. It iterates over the grid in reverse (starting from the bottom-right corner and moving to the top-left corner). In each iteration, the update function is called three times to check and update the values for the current cell based on the adjacent cells (right, down, and diagonal). Since update has constant time operations and is called three times, we can consider it as O(1) for each cell.

Since there are n*n cells and the update function is called three times for each cell, the overall time complexity is O(3*n*n) which simplifies to O(n^2).

Space Complexity

The space complexity is determined by the space required to store the f and g grids, which are both of size n x n. There are no other data structures that grow with the size of the input.

Therefore, the total space required is for two n x n grids, which gives us a space complexity of O(2*n*n), simplified to O(n^2).

In summary:

  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2)

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used to implement recursion?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄