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:
f[i][j]represents the maximum sum one can collect ending at that cell.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.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
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:
- Initialize the
fandgmatrices. - Iterate over the grid in reverse row-major order (bottom-right to top-left).
- 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). - Add the numeric value of the current cell (if it's a digit) to
f[i][j]after updating it based on its neighbors. - After processing the entire board, check the values at
f[0][0]andg[0][0]. Iff[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 modulo10^9 + 7. - 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.
How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).
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]
381import 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}
711#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};
611// 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.
70Which of the following uses divide and conquer strategy?
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.
Which two pointer technique does Quick Sort use?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching 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.