Number of Paths with Max Score — Problem & Solution
Number of Paths with Max Score solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Number of Paths with Max Score is a hard coding problem on arrays, dynamic programming and matrix, asked in Google and Samsung interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Google, Samsung
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
board is a square grid given as n strings of length n. The bottom-right cell is the start 'S' and the top-left cell is the end 'E'. Every other cell is either an obstacle 'X' or a digit '1'–'9'.
From any cell you may move up, left, or diagonally up-left, never onto an obstacle. A path from 'S' to 'E' scores the sum of the digits it passes over ('S' and 'E' count as 0).
Return [maxScore, ways]: the highest score of any path, and how many different paths achieve it, taken modulo 10^9 + 7. If 'E' cannot be reached, return [0, 0].
Example 1
Input: board = ["E31","1X2","42S"]
Output: [7,1]
Explanation: S → left onto 2 → left onto 4 → up onto 1 → up to E scores 2 + 4 + 1 = 7.
Example 2
Input: board = ["E11","121","11S"]
Output: [4,4]
Explanation: Four different paths each pass over the 2 and two of the 1s.
Example 3
Input: board = ["E9X","XXX","X1S"]
Output: [0,0]
Constraints
2 <= board.length == board[i].length <= 100board[0][0] == 'E' and board[n-1][n-1] == 'S'every other cell is 'X' or a digit '1' to '9'
Hints for Number of Paths with Max Score
Hint 1
Every move goes up, left or up-left, so a cell can only be entered from the cell below it, to its right, or diagonally below-right.
Hint 2
Process cells from the bottom-right corner towards the top-left, so those three neighbours are always finished first.
Hint 3
Keep two numbers per cell: the best score to reach it and the number of ways to get that score. Among reachable neighbours take the best score and add up the ways of every neighbour that ties it.
How to solve Number of Paths with Max Score
A DP that carries a pair per cell — the best score reaching the cell and the count of paths achieving it — solves both questions in one sweep.
Approach
- Pad the board with an unreachable extra row and column; mark
best[n-1][n-1] = 0,ways[n-1][n-1] = 1, everything else unreachable (best = -1). - Visit cells from bottom-right to top-left, skipping obstacles.
- Look at the three predecessors (below, right, below-right). Among the reachable ones take the maximum
best;waysis the sum, modulo10^9 + 7, of the predecessors that share that maximum. - Add the cell's digit to the best score (0 for
'E'). Leave the cell unreachable if no predecessor is reachable. - Return
[best[0][0], ways[0][0]], or[0, 0]if'E'is unreachable.
Why it works
Every path into a cell arrives through exactly one predecessor, so the optimal paths into the cell are the optimal paths into its best predecessors extended by one step — the counts add and nothing is counted twice. The cell's own digit is added to every such path equally, so it does not change which predecessor is best.
Complexity
- Time —
O(n²) - Space —
O(n²)
Pitfalls
- Use a separate "unreachable" marker rather than
ways == 0: a count can be 0 modulo10^9 + 7for a reachable cell. - When two predecessors tie, both counts are added; when one is strictly better, the other's count is discarded.
'E'and'S'are not digits — they add nothing to the score.
Reference solution
Python
from typing import List
def pathsWithMaxScore(board: List[str]) -> List[int]:
n = len(board)
MOD = 10 ** 9 + 7
best = [[-1] * (n + 1) for _ in range(n + 1)]
ways = [[0] * (n + 1) for _ in range(n + 1)]
best[n - 1][n - 1] = 0
ways[n - 1][n - 1] = 1
for i in range(n - 1, -1, -1):
for j in range(n - 1, -1, -1):
ch = board[i][j]
if ch == 'X' or (i == n - 1 and j == n - 1):
continue
top, cnt = -1, 0
for a, b in ((i + 1, j), (i, j + 1), (i + 1, j + 1)):
s = best[a][b]
if s < 0:
continue
if s > top:
top, cnt = s, ways[a][b]
elif s == top:
cnt = (cnt + ways[a][b]) % MOD
if top < 0:
continue
best[i][j] = top + (int(ch) if ch.isdigit() else 0)
ways[i][j] = cnt
if best[0][0] < 0:
return [0, 0]
return [best[0][0], ways[0][0]]Java
public static int[] pathsWithMaxScore(String[] board) {
int n = board.length, MOD = 1000000007;
int[][] best = new int[n + 1][n + 1], ways = new int[n + 1][n + 1];
for (int[] row : best) Arrays.fill(row, -1);
best[n - 1][n - 1] = 0;
ways[n - 1][n - 1] = 1;
int[][] moves = {{1, 0}, {0, 1}, {1, 1}};
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
char ch = board[i].charAt(j);
if (ch == 'X' || (i == n - 1 && j == n - 1)) continue;
int top = -1, cnt = 0;
for (int[] mv : moves) {
int s = best[i + mv[0]][j + mv[1]];
if (s < 0) continue;
if (s > top) { top = s; cnt = ways[i + mv[0]][j + mv[1]]; }
else if (s == top) cnt = (cnt + ways[i + mv[0]][j + mv[1]]) % MOD;
}
if (top < 0) continue;
best[i][j] = top + (ch >= '1' && ch <= '9' ? ch - '0' : 0);
ways[i][j] = cnt;
}
}
return best[0][0] < 0 ? new int[]{0, 0} : new int[]{best[0][0], ways[0][0]};
}C++
vector<int> pathsWithMaxScore(vector<string>& board) {
int n = board.size();
const int MOD = 1000000007;
vector<vector<int>> best(n + 1, vector<int>(n + 1, -1)), ways(n + 1, vector<int>(n + 1, 0));
best[n - 1][n - 1] = 0;
ways[n - 1][n - 1] = 1;
int moves[3][2] = {{1, 0}, {0, 1}, {1, 1}};
for (int i = n - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
char ch = board[i][j];
if (ch == 'X' || (i == n - 1 && j == n - 1)) continue;
int top = -1, cnt = 0;
for (auto& mv : moves) {
int s = best[i + mv[0]][j + mv[1]];
if (s < 0) continue;
if (s > top) { top = s; cnt = ways[i + mv[0]][j + mv[1]]; }
else if (s == top) cnt = (cnt + ways[i + mv[0]][j + mv[1]]) % MOD;
}
if (top < 0) continue;
best[i][j] = top + (ch >= '1' && ch <= '9' ? ch - '0' : 0);
ways[i][j] = cnt;
}
}
if (best[0][0] < 0) return {0, 0};
return {best[0][0], ways[0][0]};
}JavaScript
var pathsWithMaxScore = function(board) {
var n = board.length, MOD = 1000000007;
var best = [], ways = [];
for (var r = 0; r <= n; r++) { best.push(new Array(n + 1).fill(-1)); ways.push(new Array(n + 1).fill(0)); }
best[n - 1][n - 1] = 0;
ways[n - 1][n - 1] = 1;
for (var i = n - 1; i >= 0; i--) {
for (var j = n - 1; j >= 0; j--) {
var ch = board[i][j];
if (ch === 'X' || (i === n - 1 && j === n - 1)) continue;
var top = -1, cnt = 0;
var cand = [[i + 1, j], [i, j + 1], [i + 1, j + 1]];
for (var t = 0; t < 3; t++) {
var s = best[cand[t][0]][cand[t][1]];
if (s < 0) continue;
if (s > top) { top = s; cnt = ways[cand[t][0]][cand[t][1]]; }
else if (s === top) cnt = (cnt + ways[cand[t][0]][cand[t][1]]) % MOD;
}
if (top < 0) continue;
best[i][j] = top + (ch >= '1' && ch <= '9' ? ch.charCodeAt(0) - 48 : 0);
ways[i][j] = cnt;
}
}
return best[0][0] < 0 ? [0, 0] : [best[0][0], ways[0][0]];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming