Number of Paths with Max Score
HardPrompt
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'.
You need to reach the top left square marked with the character 'E'. The rest of the squares are labeled either with a numeric character 1, 2, ..., 9 or with an obstacle 'X'. In one move you can go up, left or up-left (diagonally) only if there is no obstacle there.
Return a list of two integers: the first integer is the maximum sum of numeric characters you can collect, and the second is the number of such paths that you can take to get that maximum sum, taken modulo 10^9 + 7.
In case there is no path, return [0, 0].
Example 1:
Input: board = ["E23","2X2","12S"]
Output: [7,1]Example 2:
Input: board = ["E12","1X1","21S"]
Output: [4,2]Example 3:
Input: board = ["E11","XXX","11S"]
Output: [0,0]
Constraints:
2 <= board.length == board[i].length <= 100
Approaches
4 approaches with complexity analysis and trade-offs.
This approach uses a simple recursive function to explore all possible paths from the starting square 'S' to the ending square 'E'. For each path, it calculates the sum of collected numbers. It then finds the maximum sum among all valid paths and counts how many paths achieve this maximum sum.
Algorithm
- Define a recursive function
dfs(row, col)that returns[max_score, path_count]for paths from(row, col)toE(0, 0). - Base Case 1 (Invalid Path): If
(row, col)is out of bounds or an obstacle 'X', return[-1, 0]to signify an impossible path. - Base Case 2 (Destination): If
(row, col)is(0, 0)(the 'E' square), return[0, 1]. The score collected at 'E' is 0, and we've found one path. - Recursive Step: From the current cell
(row, col), make recursive calls for the three possible moves towards 'E':up = dfs(row-1, col),left = dfs(row, col-1), anddiag = dfs(row-1, col-1). - Combine Results:
- Find the maximum score (
max_next_score) among the results from the three recursive calls. - If
max_next_scoreis -1, it means 'E' is unreachable from this cell, so return[-1, 0]. - Calculate the total score from the current cell:
(value of board[row][col]) + max_next_score. The value is 0 for 'S' and 'E'. - Sum the path counts from all neighbors that contributed to
max_next_score. Apply modulo arithmetic to the sum.
- Find the maximum score (
- Initial Call: Start the process by calling
dfs(n-1, n-1).
Walkthrough
We define a recursive function, say dfs(row, col), which represents the problem of finding the max score and path count starting from cell (row, col) to the destination 'E' at (0, 0). The base case for the recursion is when we reach the destination 'E'. In the recursive step, from the current cell (row, col), we can move up, left, or diagonally up-left. We make recursive calls for these three neighbors. We then compare the maximum scores returned by these three recursive calls. The best score from the current cell will be the maximum of these scores plus the value of the current cell. The number of paths for the current cell is the sum of the path counts from the neighbors that yield the maximum score. The initial call would be dfs(n-1, n-1). This approach is inefficient because it recomputes the results for the same cells multiple times, leading to an exponential number of calls.
Complexity
Time
O(3^(N^2)). In the worst-case scenario without obstacles, each cell exploration branches into three recursive calls, leading to an exponential number of path explorations.
Space
O(N^2), where N is the dimension of the board. This is due to the maximum depth of the recursion stack.
Trade-offs
Pros
Conceptually simple and a direct translation of the problem statement.
Cons
Extremely inefficient due to a massive number of redundant computations for the same cells.
Will result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
Solutions
Solution
class Solution {private List<String> board;private int n;private int[][] f;private int[][] g;private final int mod = (int)1 e9 + 7;public int[] pathsWithMaxScore(List<String> board) { n = board.size(); this.board = board; f = new int[n][n]; g = new int[n][n]; for (var e : f) { Arrays.fill(e, -1); } f[n - 1][n - 1] = 0; g[n - 1][n - 1] = 1; for (int i = n - 1; i >= 0; --i) { for (int j = n - 1; j >= 0; --j) { update(i, j, i + 1, j); update(i, j, i, j + 1); update(i, j, i + 1, j + 1); if (f[i][j] != -1) { char c = board.get(i).charAt(j); if (c >= '0' && c <= '9') { f[i][j] += (c - '0'); } } } } int[] ans = new int[2]; if (f[0][0] != -1) { ans[0] = f[0][0]; ans[1] = g[0][0]; } return ans; }private void update(int i, int j, int x, int y) { if (x >= n || y >= n || f[x][y] == -1 || board.get(i).charAt(j) == 'X' || board.get(i).charAt(j) == 'S') { return; } if (f[x][y] > f[i][j]) { f[i][j] = f[x][y]; g[i][j] = g[x][y]; } else if (f[x][y] == f[i][j]) { g[i][j] = (g[i][j] + g[x][y]) % mod; } }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.