Number of Paths with Max Score

Hard
1555.

Number of Paths with Max Score

Number of Paths with Max Score is a hard coding problem on arrays, dynamic programming and matrix, asked in Google and Samsung interviews.

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 <= 100
  • board[0][0] == 'E' and board[n-1][n-1] == 'S'
  • every other cell is 'X' or a digit '1' to '9'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} board
 * @return {number[]}
 */
var pathsWithMaxScore = function(board) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 100
  • board[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

  1. 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.

  2. Hint 2

    Process cells from the bottom-right corner towards the top-left, so those three neighbours are always finished first.

  3. 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

  1. 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).
  2. Visit cells from bottom-right to top-left, skipping obstacles.
  3. Look at the three predecessors (below, right, below-right). Among the reachable ones take the maximum best; ways is the sum, modulo 10^9 + 7, of the predecessors that share that maximum.
  4. Add the cell's digit to the best score (0 for 'E'). Leave the cell unreachable if no predecessor is reachable.
  5. 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 modulo 10^9 + 7 for 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