1301. Number of Paths with Max Score - Solution

Q: Is Number of Paths with Max Score easy or hard?

LeetCode classifies Number of Paths with Max Score as a Hard problem. The difficulty comes from combining two objectives—maximizing score and counting optimal paths—while handling obstacles and multiple movement directions in a grid.

Q: Number of Paths with Max Score Python/Java solution

Python and Java implementations typically build a 2D DP array storing score and path counts. Iterate through the grid in reverse order, update states using the three allowed directions, and apply modulo 1e9+7 for path counting. This approach runs in O(n^2) time.

Q: How to solve Number of Paths with Max Score in O(n^2)?

Use a DP table where each entry stores the best score and number of ways to reach that cell. Traverse the board from bottom-right toward the top-left, skipping obstacles and combining results from three reachable neighbors. Update the score and accumulate path counts when multiple neighbors produce the same maximum score.

Q: What is the best approach for Number of Paths with Max Score?

The best approach is dynamic programming on the grid. Track two values for each cell: the maximum score achievable and the number of paths that produce that score. By processing the grid from bottom-right to top-left and checking three neighbors (down, right, diagonal), the solution runs in O(n^2) time and O(n^2) space.

Q: Is Number of Paths with Max Score asked at Google/Amazon/Meta?

Grid dynamic programming problems similar to Number of Paths with Max Score appear frequently in interviews at companies like Amazon, Google, and Meta. The problem tests DP state design, handling multiple optimal paths, and matrix traversal patterns.

Q: What data structure is used in Number of Paths with Max Score?

The primary data structure is a 2D dynamic programming table that stores pairs of values (maximum score and path count). Some alternative solutions treat the board as a graph and use a priority queue for BFS-style traversal, but DP is the standard approach.

Q: What is the time complexity of Number of Paths with Max Score?

The optimal dynamic programming solution runs in O(n^2) time because each cell in the n x n grid is processed once while evaluating up to three transitions. The space complexity is also O(n^2) for storing the DP state containing maximum score and path counts.

The problem

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

Approach overview

Problem Overview: You are given an n x n board containing digits, obstacles (X), a start cell S, and an end cell E. Starting from S (bottom‑right), you can move up, left, or diagonally up‑left until reaching E. Each path collects numeric values from cells, and the goal is to compute the maximum possible score and the number of distinct paths that achieve that score.

Approach 1: Dynamic Programming (State Tracking) (Time: O(n²), Space: O(n²))

This solution uses a DP table where each cell stores two values: the maximum score achievable when reaching that cell and the number of ways to achieve that score. Starting from S, you iterate through the grid in reverse directions that match the allowed moves (up, left, diagonal). For every valid cell, check the three predecessor states and choose the one producing the highest score. If multiple predecessors produce the same score, sum their path counts (mod 1e9+7). This works well because each cell’s result depends only on previously computed states, a classic pattern in dynamic programming.

Approach 2: Dynamic Programming from Bottom‑Right to Top‑Left (Time: O(n²), Space: O(n²))

This is the most common implementation used in interviews. Instead of expanding from the start, the algorithm fills the DP table while scanning the grid from bottom‑right to top‑left. At each cell, examine the three reachable neighbors (down, right, and down‑right) that represent valid forward moves. Compute the best score among them, then update the current cell’s score and path count accordingly. Obstacles (X) immediately invalidate states. Because each cell is processed exactly once, the algorithm runs in O(n²) time and efficiently handles grids up to typical constraints. The grid traversal pattern is common in matrix DP problems.

Approach 3: Breadth‑First Search with Priority Queue (Time: O(n² log n), Space: O(n²))

This alternative models the board as a graph. Each cell is a node and edges represent valid moves. A max‑priority queue always expands the state with the highest accumulated score first, similar to a modified Dijkstra traversal. For each expansion, update neighbor states if a higher score is found or if an equal score adds additional paths. While conceptually intuitive for graph thinking, the priority queue introduces a log factor and makes it slower than pure DP. This approach highlights how grid traversal problems can also be framed as graph searches over an array structure.

Recommended for interviews: The bottom‑right to top‑left dynamic programming solution is what most interviewers expect. It shows you can translate grid movement constraints into DP state transitions and track both score and path counts simultaneously. A brute‑force search would explore exponentially many paths, so demonstrating the DP optimization proves strong algorithmic reasoning.

Approach 1: Dynamic Programming Approach

In this approach, the idea is to use dynamic programming to keep track of the maximum score and the number of ways to achieve it, starting from the end point 'S' and working backwards to the start point 'E'. We will initialize a dp array where each cell will store two values: the maximum score to reach this cell and the number of ways to achieve that score. We iterate over each cell and update its value based on possible movements from the neighboring cells (up, left, and up-left) that are not blocked by an obstacle 'X'.

Python

def paths_with_max_score(board):
    MOD = 10**9 + 7
    n = len(board)
    dp = [[(-1, 0) for _ in range(n)] for _ in range(n)]
    dp[-1][-1] = (0, 1)
    directions = [(-1, 0), (0, -1), (-1, -1)]

    for i in range(n-1, -1, -1):
        for j in range(n-1, -1, -1):
            if board[i][j] == 'X' or (i == n-1 and j == n-1):
                continue
            max_sum, path_count = 0, 0
            for d in directions:
                ni, nj = i + d[0], j + d[1]
                if 0 <= ni < n and 0 <= nj < n and dp[ni][nj][0] != -1:
                    if dp[ni][nj][0] > max_sum:
                        max_sum = dp[ni][nj][0]
                        path_count = dp[ni][nj][1]
                    elif dp[ni][nj][0] == max_sum:
                        path_count += dp[ni][nj][1]
            if board[i][j] != 'E':
                max_sum += int(board[i][j])
            dp[i][j] = (max_sum % MOD, path_count % MOD)

    return [dp[0][0][0], dp[0][0][1]] if dp[0][0][1] > 0 else [0, 0]

Java

import java.util.*;

public class Solution {
    public int[] pathsWithMaxScore(List<String> board) {
        int MOD = 1000000007;
        int n = board.size();
        int[][][] dp = new int[n][n][2];
        dp[n-1][n-1] = new int[]{0, 1};
        int[][] directions = {{-1, 0}, {0, -1}, {-1, -1}};

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (board.get(i).charAt(j) == 'X' || (i == n - 1 && j == n - 1)) {
                    continue;
                }
                int maxSum = 0, pathCount = 0;
                for (int[] direction : directions) {
                    int ni = i + direction[0], nj = j + direction[1];
                    if (ni >= 0 && nj >= 0) {
                        if (dp[ni][nj][0] > maxSum) {
                            maxSum = dp[ni][nj][0];
                            pathCount = dp[ni][nj][1];
                        } else if (dp[ni][nj][0] == maxSum) {
                            pathCount = (pathCount + dp[ni][nj][1]) % MOD;
                        }
                    }
                }
                if (board.get(i).charAt(j) != 'E') {
                    maxSum = (maxSum + board.get(i).charAt(j) - '0') % MOD;
                }
                dp[i][j][0] = maxSum;
                dp[i][j][1] = pathCount;
            }
        }
        return dp[0][0][1] > 0 ? new int[]{dp[0][0][0], dp[0][0][1]} : new int[]{0, 0};
    }
}

The solution uses a double array `dp` where `dp[i][j]` contains a tuple `(max_sum, path_count)` representing the maximum sum that can be collected to reach the cell `(i, j)` and the number of ways to reach that maximum sum. We start from 'S', marked initially with `(0, 1)`, meaning we start with sum 0 and 1 way. While iterating, we update cells with possible movements from adjacent cells. The time complexity is O(n^2), where n is the size of the board, and the space complexity is also O(n^2) due to the auxiliary array `dp`.

Complexity

Time Complexity: O(n^2) where n is the dimension of the square board.
Space Complexity: O(n^2) for the dp array.

Try this approach in the editor

Approach 2: Dynamic Programming from Bottom-Right to Top-Left

Strategy: In this approach, we'll use dynamic programming to track the maximum path sum and the number of possible such paths from the start square 'S' to the end square 'E'. We'll initialize the bottom-right corner and populate upwards and leftwards.

We use a 2D array for max scores and paths. For each cell not blocked by 'X', the value of max score and path count is determined by considering up, left, and diagonal moves, ensuring to add the numeric value of the current cell to the path sum.

Python

from typing import List

class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        MOD = 10**9 + 7
        n = len(board)
        dp = [[0] * (n+1) for _ in range(n+1)]
        count = [[0] * (n+1) for _ in range(n+1)]
        count[n-1][n-1] = 1

        for i in reversed(range(n)):
            for j in reversed(range(n)):
                if board[i][j] == 'X':
                    continue
                for di, dj in [(0, -1), (-1, 0), (-1, -1)]:
                    ni, nj = i + di, j + dj
                    if ni < 0 or nj < 0:
                        continue
                    if dp[ni][nj] > 0 or (ni, nj) == (n-1, n-1):
                        if dp[i][j] < dp[ni][nj]:
                            dp[i][j] = dp[ni][nj]
                            count[i][j] = count[ni][nj]
                        elif dp[i][j] == dp[ni][nj]:
                            count[i][j] = (count[i][j] + count[ni][nj]) % MOD
                if board[i][j] != 'E':
                    dp[i][j] += int(board[i][j])

        if dp[0][0] == 0 and count[0][0] == 1:
            return [0, 0]
        return [dp[0][0], count[0][0]]

Java

import java.util.*;

public class Solution {
    private static final int MOD = 1000000007;

    public int[] pathsWithMaxScore(List<String> board) {
        int n = board.size();
        int[][] dp = new int[n+1][n+1];
        int[][] count = new int[n+1][n+1];
        count[n-1][n-1] = 1;

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (board.get(i).charAt(j) == 'X') continue;
                for (int[] d : new int[][]{{-1, 0}, {0, -1}, {-1, -1}}) {
                    int ni = i + d[0], nj = j + d[1];
                    if (ni >= 0 && nj >= 0 && dp[ni][nj] >= 0) {
                        int score = (board.get(i).charAt(j) == 'E') ? 0 : board.get(i).charAt(j) - '0';
                        if (dp[i][j] < dp[ni][nj] + score) {
                            dp[i][j] = dp[ni][nj] + score;
                            count[i][j] = count[ni][nj];
                        } else if (dp[i][j] == dp[ni][nj] + score) {
                            count[i][j] = (count[i][j] + count[ni][nj]) % MOD;
                        }
                    }
                }
            }
        }

        if (dp[0][0] == 0 && count[0][0] == 1) return new int[]{0, 0};
        return new int[]{dp[0][0], count[0][0]};
    }
}

C++

#include <vector>
#include <string>
#define MOD 1000000007
using namespace std;

vector<int> pathsWithMaxScore(vector<string>& board) {
    int n = board.size();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
    vector<vector<int>> paths(n + 1, vector<int>(n + 1, 0));
    dp[n-1][n-1] = 0;
    paths[n-1][n-1] = 1;

    for (int i = n - 1; i >= 0; --i) {
        for (int j = n - 1; j >= 0; --j) {
            if (board[i][j] == 'X') continue;
            int maxScore = -1;
            for (int di = -1; di <= 0; ++di) {
                for (int dj = -1; dj <= 0; ++dj) {
                    int ni = i + di, nj = j + dj;
                    if (ni < 0 || nj < 0) continue;
                    if (dp[ni][nj] == -1) continue;
                    if (dp[ni][nj] > maxScore) {
                        maxScore = dp[ni][nj];
                        paths[i][j] = paths[ni][nj];
                    } else if (dp[ni][nj] == maxScore) {
                        paths[i][j] = (paths[i][j] + paths[ni][nj]) % MOD;
                    }
                }
            }
            if (maxScore != -1) {
                dp[i][j] = maxScore + (board[i][j] != 'E' ? board[i][j] - '0' : 0);
            }
        }
    }

    return {max(0, dp[0][0]), paths[0][0]};
}

JavaScript

const MOD = 1e9 + 7;

function pathsWithMaxScore(board) {
    const n = board.length;
    const dp = Array.from({length: n + 1}, () => Array(n + 1).fill(0));
    const count = Array.from({length: n + 1}, () => Array(n + 1).fill(0));
    count[n-1][n-1] = 1;

    for (let i = n - 1; i >= 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            if (board[i][j] === 'X') continue;
            for (const [di, dj] of [[0, -1], [-1, 0], [-1, -1]]) {
                const ni = i + di, nj = j + dj;
                if (ni < 0 || nj < 0) continue;
                if (dp[ni][nj] > 0 || (ni === n - 1 && nj === n - 1)) {
                    const score = board[i][j] === 'E' ? 0 : Number(board[i][j]);
                    if (dp[i][j] < dp[ni][nj] + score) {
                        dp[i][j] = dp[ni][nj] + score;
                        count[i][j] = count[ni][nj];
                    } else if (dp[i][j] === dp[ni][nj] + score) {
                        count[i][j] = (count[i][j] + count[ni][nj]) % MOD;
                    }
                }
            }
        }
    }

    if (dp[0][0] === 0 && count[0][0] === 1) return [0, 0];
    return [dp[0][0], count[0][0]];
}

#include <stdio.h>
#include <string.h>
#define MOD 1000000007

int max(int a, int b) { return a > b ? a : b; }

int* pathsWithMaxScore(char ** board, int boardSize, int* returnSize) {
    int dp[101][101][2] = {0};
    int m = boardSize;

    dp[m-1][m-1][0] = dp[m-1][m-1][1] = 1;

    for (int i = m-1; i >= 0; --i) {
        for (int j = m-1; j >= 0; --j) {
            if (board[i][j] == 'X') continue;
            for (int di = -1; di <= 0; ++di) {
                for (int dj = -1; dj <= 0; ++dj) {
                    if (di == 0 && dj == 0) continue;
                    int ni = i + di, nj = j + dj;
                    if (ni < 0 || nj < 0) continue;
                    if (dp[ni][nj][0] == 0) continue;
                    int val = board[i][j] != 'E' ? board[i][j] - '0' : 0;
                    if (dp[i][j][0] < dp[ni][nj][0] + val) {
                        dp[i][j][0] = dp[ni][nj][0] + val;
                        dp[i][j][1] = dp[ni][nj][1];
                    } else if (dp[i][j][0] == dp[ni][nj][0] + val) {
                        dp[i][j][1] = (dp[i][j][1] + dp[ni][nj][1]) % MOD;
                    }
                }
            }
        }
    }

    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = dp[0][0][0];
    result[1] = dp[0][0][1];
    if (result[0] == 1 && result[1] == 1) result[1] = 0;
    *returnSize = 2;
    return result;
}

public class Solution {
    private const int MOD = 1000000007;

    public int[] PathsWithMaxScore(IList<string> board) {
        int n = board.Count;
        int[,] dp = new int[n + 1, n + 1];
        int[,] count = new int[n + 1, n + 1];
        count[n-1, n-1] = 1;

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (board[i][j] == 'X') continue;
                for (int di = -1; di <= 0; di++) {
                    for (int dj = -1; dj <= 0; dj++) {
                        if (di == 0 && dj == 0) continue;
                        int ni = i + di, nj = j + dj;
                        if (ni < 0 || nj < 0 || dp[ni,nj] == 0) continue;
                        int value = (board[i][j] != 'E') ? board[i][j] - '0' : 0;
                        if (dp[i,j] < dp[ni,nj] + value) {
                            dp[i,j] = dp[ni,nj] + value;
                            count[i,j] = count[ni,nj];
                        } else if (dp[i,j] == dp[ni,nj] + value) {
                            count[i,j] = (count[i,j] + count[ni,nj]) % MOD;
                        }
                    }
                }
            }
        }

        if (dp[0,0] == 0 && count[0,0] == 0) return new int[] {0, 0};
        return new int[] {dp[0,0], count[0,0]};
    }
}

This Python solution implements a conventional DP algorithm, operating in reverse from the 'S' to 'E'. Using two matrices, it efficiently keeps track of the maximal score obtainable and pathways counts for each grid cell, accommodating value addition for non-'X' cells.

Complexity

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

Try this approach in the editor

Approach 3: Breadth-First Search with Priority Queue

Strategy: In this BFS approach, prioritize exploring paths with higher sums by deploying a max-heap structure, ensuring the most beneficial paths are expanded first. We'll backtrack from 'S' to 'E' while updating our path scores dynamically based on BFS execution order.

Python

from heapq import heappop, heappush
from typing import List

class Solution:
    def pathsWithMaxScore(self, board: List[str]) -> List[int]:
        MOD = 10**9 + 7
        n = len(board)
        pq = [(-0, n-1, n-1, 1)]
        visited = [[-1] * n for _ in range(n)]
        directions = [(-1, 0), (0, -1), (-1, -1)]

        while pq:
            curr_neg_sum, r, c, path_count = heappop(pq)
            if r == 0 and c == 0:
                return [-curr_neg_sum, path_count % MOD]
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and board[nr][nc] != 'X':
                    new_sum = -curr_neg_sum + (0 if board[nr][nc] == 'E' else int(board[nr][nc]))
                    if visited[nr][nc] < new_sum:
                        visited[nr][nc] = new_sum
                        heappush(pq, (-new_sum, nr, nc, path_count))
                    elif visited[nr][nc] == new_sum:
                        heappush(pq, (-new_sum, nr, nc, path_count + 1))

        return [0, 0]

Java

import java.util.*;

public class Solution {
    private static final int MOD = 1000000007;

    public int[] pathsWithMaxScore(List<String> board) {
        int n = board.size();
        Queue&lt;int[]&gt; pq = new PriorityQueue&lt;&gt;((a, b) -&gt; b[2] - a[2]);
        int[][] visited = new int[n][n];

        pq.offer(new int[]{n-1, n-1, 0, 1});
        visited[n-1][n-1] = 0;

        int[] directions = {-1, 0, -1, -1, 0, -1};

        int maxSum = 0, pathCount = 0;

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int r = current[0], c = current[1];

            if (r == 0 && c == 0) {
                if (current[2] > maxSum) {
                    maxSum = current[2];
                    pathCount = current[3];
                } else if (current[2] == maxSum) {
                    pathCount = (pathCount + current[3]) % MOD;
                }
                continue;
            }

            for (int d = 0; d < 6; d += 2) {
                int nr = r + directions[d], nc = c + directions[d+1];
                if (nr < 0 || nc < 0 || board.get(nr).charAt(nc) == 'X') continue;
                int newSum = current[2] + (board.get(nr).charAt(nc) != 'E' ? Character.getNumericValue(board.get(nr).charAt(nc)) : 0);
                if (visited[nr][nc] < newSum) {
                    visited[nr][nc] = newSum;
                    pq.offer(new int[]{nr, nc, newSum, current[3]});
                } else if (visited[nr][nc] == newSum) {
                    pq.offer(new int[]{nr, nc, newSum, current[3] + 1});
                }
            }
        }

        return new int[]{maxSum, pathCount};
    }
}

C++

#include &lt;queue&gt;
#include &lt;vector&gt;
#include &lt;string&gt;
#define MOD 1000000007
using namespace std;

class Solution {
public:
    vector<int> pathsWithMaxScore(vector<string>& board) {
        int n = board.size();
        priority_queue&lt;tuple&lt;int, int, int, int&gt;, vector&lt;tuple&lt;int, int, int, int&gt;&gt;, less&lt;&gt;&gt; pq;
        vector&lt;vector&lt;int&gt;&gt; visited(n, vector&lt;int&gt;(n, -1));

        pq.emplace(0, 1, n-1, n-1);
        visited[n-1][n-1] = 0;

        vector&lt;int&gt; dir{-1, 0, -1, -1, 0, -1};

        int maxSum = 0, pathCount = 0;

        while (!pq.empty()) {
            auto [sum, count, r, c] = pq.top(); pq.pop();
            if (r == 0 && c == 0) {
                if (sum &gt; maxSum) {
                    maxSum = sum;
                    pathCount = count;
                } else if (sum == maxSum) {
                    pathCount = (pathCount + count) % MOD;
                }
                continue;
            }
            for (int d = 0; d &lt; 6; d += 2) {
                int nr = r + dir[d], nc = c + dir[d+1];
                if (nr &lt; 0 || nc &lt; 0 || board[nr][nc] == 'X') continue;
                int newSum = sum + (board[nr][nc] != 'E' ? board[nr][nc] - '0' : 0);
                if (visited[nr][nc] &lt; newSum) {
                    visited[nr][nc] = newSum;
                    pq.emplace(newSum, count, nr, nc);
                } else if (visited[nr][nc] == newSum) {
                    pq.emplace(newSum, count + 1, nr, nc);
                }
            }
        }

        return {maxSum, pathCount};
    }
};

JavaScript

function pathsWithMaxScore(board) {
    const MOD = 1e9 + 7;
    const n = board.length;
    const pq = new MaxPriorityQueue({ priority: (a) => a[2] });
    let visited = Array.from({ length: n }, () => Array(n).fill(-1));
    const directions = [[-1, 0], [0, -1], [-1, -1]];

    pq.enqueue([n-1, n-1, 0, 1]);
    visited[n-1][n-1] = 0;

    while (!pq.isEmpty()) {
        let [r, c, sum, pathCount] = pq.dequeue().element;

        if (r == 0 && c == 0) {
            return [sum, pathCount % MOD];
        }

        for (let [dr, dc] of directions) {
            let nr = r + dr, nc = c + dc;
            if (nr < 0 || nc < 0 || board[nr][nc] == 'X') continue;
            let newSum = sum + (board[nr][nc] != 'E' ? Number(board[nr][nc]) : 0);
            if (visited[nr][nc] < newSum) {
                visited[nr][nc] = newSum;
                pq.enqueue([nr, nc, newSum, pathCount]);
            } else if (visited[nr][nc] == newSum) {
                pq.enqueue([nr, nc, newSum, pathCount + 1]);
            }
        }
    }

    return [0, 0];
}

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MOD 1000000007

typedef struct {
    int r, c, sum, count;
} Node;

int compare(const void *a, const void *b) {
    return ((Node *)b)->sum - ((Node *)a)->sum;
}

int* pathsWithMaxScore(char** board, int boardSize, int* returnSize) {
    int n = boardSize;
    Node* queue = (Node*)malloc(n * n * sizeof(Node));
    int** visited = (int**)malloc(n * sizeof(int*));
    int front = 0, rear = 0;

    for (int i = 0; i < n; ++i) {
        visited[i] = (int*)calloc(n, sizeof(int));
    }

    queue[rear++] = (Node){n-1, n-1, 0, 1};
    visited[n-1][n-1] = 1;

    int maxSum = 0, pathCount = 0;

    int directions[3][2] = {{-1, 0}, {0, -1}, {-1, -1}};

    while (front < rear) {
        qsort(queue + front, rear - front, sizeof(Node), compare);
        Node current = queue[front++];

        if (current.r == 0 && current.c == 0) {
            if (current.sum > maxSum) {
                maxSum = current.sum;
                pathCount = current.count;
            } else if (current.sum == maxSum) {
                pathCount = (pathCount + current.count) % MOD;
            }
            continue;
        }

        for (int i = 0; i < 3; ++i) {
            int nr = current.r + directions[i][0];
            int nc = current.c + directions[i][1];
            if (nr < 0 || nc < 0 || board[nr][nc] == 'X' || visited[nr][nc] >= current.sum) continue;
            int newSum = current.sum + (board[nr][nc] != 'E' ? board[nr][nc] - '0' : 0);
            if (visited[nr][nc] < newSum) {
                visited[nr][nc] = newSum;
                queue[rear++] = (Node){nr, nc, newSum, current.count};
            } else if (visited[nr][nc] == newSum) {
                for (int j = front; j < rear; ++j) {
                    if (queue[j].r == nr && queue[j].c == nc && queue[j].sum == newSum) {
                        queue[j].count = (queue[j].count + current.count) % MOD;
                        break;
                    }
                }
            }
        }
    }

    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = maxSum;
    result[1] = pathCount;
    *returnSize = 2;
    return result;
}

using System;
using System.Collections.Generic;

public class Solution {
    private const int MOD = 1000000007;

    public int[] PathsWithMaxScore(IList&lt;string&gt; board) {
        int n = board.Count;
        var pq = new SortedDictionary&lt;int, Queue&lt;int[]&gt;&gt;(Comparer&lt;int&gt;.Create((a, b) =&gt; b.CompareTo(a)));
        pq[0] = new Queue&lt;int[]&gt;();
        pq[0].Enqueue(new[]{n-1, n-1, 1});
        int[][] visited = new int[n][];
        for (int i = 0; i &lt; n; ++i) visited[i] = new int[n];

        int[] directions = {-1, 0, -1, -1, 0, -1};

        while (pq.Count &gt; 0) {
            var maxKey = pq.Keys.GetEnumerator();
            maxKey.MoveNext();
            int currentSum = maxKey.Current;
            var nodes = pq[currentSum];
            while (nodes.Count &gt; 0) {
                var current = nodes.Dequeue();
                if (current[0] == 0 && current[1] == 0) {
                    return new int[]{currentSum, current[2]};
                }

                for (int d = 0; d &lt; 6; d += 2) {
                    int nr = current[0] + directions[d], nc = current[1] + directions[d+1];
                    if (nr &lt; 0 || nc &lt; 0 || board[nr][nc] == 'X') continue;
                    int nextKey = currentSum + (board[nr][nc] != 'E' ? board[nr][nc] - '0' : 0);
                    if (visited[nr][nc] < nextKey) {
                        visited[nr][nc] = nextKey;
                        if (!pq.ContainsKey(nextKey)) pq[nextKey] = new Queue&lt;int[]&gt;();
                        pq[nextKey].Enqueue(new[]{nr, nc, current[2]});
                    } else if (visited[nr][nc] == nextKey) {
                        pq[nextKey].Enqueue(new[]{nr, nc, current[2] + 1});
                    }
                }
            }
            if (nodes.Count == 0) pq.Remove(currentSum);
        }

        return new int[]{0, 0};
    }
}

In this Python implementation, a max-heap using heapq effectively applies BFS, instantiating negative weights to simulate priority queuing. This choice maximizes path extension based on the sum calculations for advantageous path exploration.

Complexity

Time Complexity: O(n^2 log n).
Space Complexity: O(n^2).

Try this approach in the editor

Approach 4: Dynamic Programming

We define f[i][j] to represent the maximum score from the starting point (n - 1, n - 1) to (i, j), and g[i][j] to represent the number of ways to achieve the maximum score from the starting point (n - 1, n - 1) to (i, j). Initially, f[n - 1][n - 1] = 0 and g[n - 1][n - 1] = 1. The other positions of f[i][j] are all -1, and g[i][j] are all 0.

For the current position (i, j), it can be transferred from three positions: (i + 1, j), (i, j + 1), and (i + 1, j + 1). Therefore, we can enumerate these three positions to update the values of f[i][j] and g[i][j]. If the current position (i, j) has an obstacle, or the current position is the starting point, or other positions are out of bounds, no update is performed. Otherwise, if another position (x, y) satisfies f[x][y] \gt f[i][j], then we update f[i][j] = f[x][y] and g[i][j] = g[x][y]. If f[x][y] = f[i][j], then we update g[i][j] = g[i][j] + g[x][y]. Finally, if the current position (i, j) is reachable and is a number, we update f[i][j] = f[i][j] + board[i][j].

Finally, if f[0][0] \lt 0, it means there is no path to reach the endpoint, return [0, 0]. Otherwise, return [f[0][0], g[0][0]]. Note that the result needs to be taken modulo 10^9 + 7.

Time complexity O(n^2), space complexity O(n^2). Where n is the side length of the array.

func pathsWithMaxScore(board []string) []int {
	n := len(board)
	f := make([][]int, n)
	g := make([][]int, n)
	for i := range f {
		f[i] = make([]int, n)
		g[i] = make([]int, n)
		for j := range f[i] {
			f[i][j] = -1
		}
	}
	f[n-1][n-1] = 0
	g[n-1][n-1] = 1
	const mod = 1e9 + 7

	update := func(i, j, x, y int) {
		if x >= n || y >= n || f[x][y] == -1 || board[i][j] == 'X' || board[i][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
		}
	}
	for i := n - 1; i >= 0; i-- {
		for 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 && board[i][j] >= '0' && board[i][j] <= '9' {
				f[i][j] += int(board[i][j] - '0')
			}
		}
	}
	ans := make([]int, 2)
	if f[0][0] != -1 {
		ans[0], ans[1] = f[0][0], g[0][0]
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming Approach	Time Complexity: O(n^2) where n is the dimension of the square board. Space Complexity: O(n^2) for the dp array.
Dynamic Programming from Bottom-Right to Top-Left	Time Complexity: O(n^2). Space Complexity: O(n^2).
Breadth-First Search with Priority Queue	Time Complexity: O(n^2 log n). Space Complexity: O(n^2).
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming (State Tracking)	O(n²)	O(n²)	General solution when computing best score and number of ways simultaneously
DP Bottom‑Right to Top‑Left	O(n²)	O(n²)	Most common interview implementation for grid DP problems
BFS with Priority Queue	O(n² log n)	O(n²)	Useful when modeling the grid as a graph with weighted paths

Frequently asked questions

Is Number of Paths with Max Score easy or hard?

LeetCode classifies Number of Paths with Max Score as a Hard problem. The difficulty comes from combining two objectives—maximizing score and counting optimal paths—while handling obstacles and multiple movement directions in a grid.

Number of Paths with Max Score Python/Java solution

Python and Java implementations typically build a 2D DP array storing score and path counts. Iterate through the grid in reverse order, update states using the three allowed directions, and apply modulo 1e9+7 for path counting. This approach runs in O(n^2) time.

How to solve Number of Paths with Max Score in O(n^2)?

Use a DP table where each entry stores the best score and number of ways to reach that cell. Traverse the board from bottom-right toward the top-left, skipping obstacles and combining results from three reachable neighbors. Update the score and accumulate path counts when multiple neighbors produce the same maximum score.

What is the best approach for Number of Paths with Max Score?

The best approach is dynamic programming on the grid. Track two values for each cell: the maximum score achievable and the number of paths that produce that score. By processing the grid from bottom-right to top-left and checking three neighbors (down, right, diagonal), the solution runs in O(n^2) time and O(n^2) space.

Is Number of Paths with Max Score asked at Google/Amazon/Meta?

Grid dynamic programming problems similar to Number of Paths with Max Score appear frequently in interviews at companies like Amazon, Google, and Meta. The problem tests DP state design, handling multiple optimal paths, and matrix traversal patterns.

What data structure is used in Number of Paths with Max Score?

The primary data structure is a 2D dynamic programming table that stores pairs of values (maximum score and path count). Some alternative solutions treat the board as a graph and use a priority queue for BFS-style traversal, but DP is the standard approach.

What is the time complexity of Number of Paths with Max Score?

The optimal dynamic programming solution runs in O(n^2) time because each cell in the n x n grid is processed once while evaluating up to three transitions. The space complexity is also O(n^2) for storing the DP state containing maximum score and path counts.

Number of Paths with Max Score solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Dynamic Programming from Bottom-Right to Top-Left

Approach 3: Breadth-First Search with Priority Queue

Approach 4: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Number of Paths with Max Score solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming Approach

Approach 2: Dynamic Programming from Bottom-Right to Top-Left

Approach 3: Breadth-First Search with Priority Queue

Approach 4: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems