Maximum Path Score in a Grid solution and explanation
Google
9 more videos on this problem
Maximum Path Score in a Grid | Detailed | Simplified | Leetcode 3742 | codestorywithMIKcodestorywithMIK · 24:21 · 5K views
Maximum Path Score in a Grid | LeetCode 3742 | Weekly Contest 475Sanyam IIT Guwahati · 17:57 · 1K views
3742. Maximum Path Score in a Grid (Leetcode Medium)Programming Live with Larry · 22:22 · 437 views
leetcode 3742 | Maximum Path Score in a Grid | Leetcode POTD | Dynamic Programming | DSACode With Vick · 16:19 · 433 views
Daily Leetcode #2221: Apr 30, 2026 - 3742. Maximum Path Score in a GridProgramming Live with Larry · 12:47 · 414 views
Maximum Path Score in a Grid | Leetcode 3742 | Java | HindiKernel Queen 👑 · 9:18 · 405 views
Maximum Path Score in a Grid | LeetCode 3742 - Pythonimpoldev · 14:00 · 353 views
3742. Maximum Path Score in a Grid | Leetcode Daily - PythonLeetcode Daily · 4:52 · 267 views
Maximum Path Score in a Grid | LeetCode 3742 | DP | Java Code | Developer CoderDeveloper Coder · 18:10 · 145 views
3742. Maximum Path Score in a Grid | Weekly contest 475 | Q3 | dynamic programmingcodingX krishna · 23:47 · 126 views
The problem
You are given an m x n grid where each cell contains one of the values 0, 1, or 2. You are also given an integer k.
You start from the top-left corner (0, 0) and want to reach the bottom-right corner (m - 1, n - 1) by moving only right or down.
Each cell contributes a specific score and incurs an associated cost, according to their cell values:
- 0: adds 0 to your score and costs 0.
- 1: adds 1 to your score and costs 1.
- 2: adds 2 to your score and costs 1.
Return the maximum score achievable without exceeding a total cost of k, or -1 if no valid path exists.
Note: If you reach the last cell but the total cost exceeds k, the path is invalid.
Example 1:
Input: grid = [[0, 1],[2, 0]], k = 1
Output: 2
Explanation:
The optimal path is:
| Cell | grid[i][j] | Score | Total Score |
Cost | Total Cost |
|---|---|---|---|---|---|
| (0, 0) | 0 | 0 | 0 | 0 | 0 |
| (1, 0) | 2 | 2 | 2 | 1 | 1 |
| (1, 1) | 0 | 0 | 2 | 0 | 1 |
Thus, the maximum possible score is 2.
Example 2:
Input: grid = [[0, 1],[1, 2]], k = 1
Output: -1
Explanation:
There is no path that reaches cell (1, 1) without exceeding cost k. Thus, the answer is -1.
Constraints:
1 <= m, n <= 2000 <= k <= 103grid[0][0] == 00 <= grid[i][j] <= 2
Approach overview
Problem Overview: You are given a matrix where each cell contributes to a score. Starting from the top-left cell, move through the grid to reach the destination while maximizing the total score collected along the path.
Approach 1: Brute Force DFS (Exponential Time)
The most direct way is to explore every possible path from the starting cell to the destination using depth-first search. From each position, recursively move to the allowed neighboring cells (commonly right or down in grid path problems) and track the cumulative score. At the destination, return the final score and propagate the maximum back up the recursion stack. This approach checks every possible path combination, which leads to O(2^(m+n)) time in the worst case and O(m+n) recursion stack space. It demonstrates the core idea but quickly becomes infeasible for larger grids.
Approach 2: Memoization Search (Top-Down Dynamic Programming) (O(m*n))
A better approach stores intermediate results so each grid cell is solved only once. Use a DFS function dfs(r, c) that returns the maximum score obtainable starting from cell (r, c). When the function computes the result for a cell, store it in a memo table. If the same cell is reached again, return the cached value instead of recomputing all paths below it. The recurrence adds the current cell value to the maximum of the next reachable cells.
This converts the exponential search into a dynamic programming solution over the grid. Each cell becomes a state, and transitions correspond to valid moves. Because there are at most m * n cells and each state is computed once, the time complexity becomes O(m*n). The memo table requires O(m*n) space, and recursion depth is bounded by the grid dimensions.
This pattern is a classic application of dynamic programming on a matrix, where overlapping subproblems appear while exploring paths. The grid itself is simply stored as an array structure.
Recommended for interviews: Start by describing the brute-force DFS to show you understand the path enumeration. Then transition to memoization and explain how caching results for each cell eliminates repeated work. Interviewers typically expect the memoized or DP solution with O(m*n) time.
Solution
We define a function dfs(i, j, k) that represents the maximum score achievable when starting from position (i, j) and reaching the endpoint (0, 0) with remaining cost not exceeding k. We use memoization search to avoid redundant calculations.
Specifically, the implementation steps of function dfs(i, j, k) are as follows:
- If the current coordinate
(i, j)is out of bounds or the remaining costkis less than0, return negative infinity to indicate that the endpoint cannot be reached. - If the current coordinate is the starting point
(0, 0), return0, indicating that the endpoint has been reached (the problem guarantees the starting point has value0). - Calculate the score contribution
resof the current cell. If the current cell's value is not0, decrement the remaining costkby1. - Recursively calculate the maximum scores achievable from the upper cell
(i-1, j)and the left cell(i, j-1)when reaching the endpoint with remaining cost not exceedingk, denoted asaandbrespectively. - Add the current cell's score contribution
restomax(a, b)to get the maximum score achievable from the current cell, and return this value.
Finally, we call dfs(m-1, n-1, k) to calculate the maximum score achievable when starting from the bottom-right corner and reaching the top-left corner with remaining cost not exceeding k. If the result is less than 0, return -1 to indicate no valid path exists; otherwise, return the result.
The time complexity is O(m times n times k), and the space complexity is O(m times n times k), where m and n are the number of rows and columns in the grid, and k is the maximum allowed cost.
class Solution:
def maxPathScore(self, grid: List[List[int]], k: int) -> int:
@cache
def dfs(i: int, j: int, k: int) -> int:
if i < 0 or j < 0 or k < 0:
return -inf
if i == 0 and j == 0:
return 0
res = grid[i][j]
if grid[i][j]:
k -= 1
a = dfs(i - 1, j, k)
b = dfs(i, j - 1, k)
res += max(a, b)
return res
ans = dfs(len(grid) - 1, len(grid[0]) - 1, k)
dfs.cache_clear()
return -1 if ans < 0 else ansclass Solution {
private int[][] grid;
private Integer[][][] f;
private final int inf = 1 << 30;
public int maxPathScore(int[][] grid, int k) {
this.grid = grid;
int m = grid.length;
int n = grid[0].length;
f = new Integer[m][n][k + 1];
int ans = dfs(m - 1, n - 1, k);
return ans < 0 ? -1 : ans;
}
private int dfs(int i, int j, int k) {
if (i < 0 || j < 0 || k < 0) {
return -inf;
}
if (i == 0 && j == 0) {
return 0;
}
if (f[i][j][k] != null) {
return f[i][j][k];
}
int res = grid[i][j];
int nk = k;
if (grid[i][j] > 0) {
--nk;
}
int a = dfs(i - 1, j, nk);
int b = dfs(i, j - 1, nk);
res += Math.max(a, b);
f[i][j][k] = res;
return res;
}
}class Solution {
public:
int maxPathScore(vector<vector<int>>& grid, int k) {
int m = grid.size();
int n = grid[0].size();
int inf = 1 << 30;
vector f(m, vector(n, vector<int>(k + 1, -1)));
auto dfs = [&](this auto&& dfs, int i, int j, int k) -> int {
if (i < 0 || j < 0 || k < 0) {
return -inf;
}
if (i == 0 && j == 0) {
return 0;
}
if (f[i][j][k] != -1) {
return f[i][j][k];
}
int res = grid[i][j];
int nk = k;
if (grid[i][j] > 0) {
--nk;
}
int a = dfs(i - 1, j, nk);
int b = dfs(i, j - 1, nk);
res += max(a, b);
return f[i][j][k] = res;
};
int ans = dfs(m - 1, n - 1, k);
return ans < 0 ? -1 : ans;
}
};function maxPathScore(grid: number[][], k: number): number {
const m = grid.length;
const n = grid[0].length;
const inf = 1 << 30;
const f: number[][][] = Array.from({ length: m }, () =>
Array.from({ length: n }, () => Array(k + 1).fill(-1)),
);
const dfs = (i: number, j: number, k: number): number => {
if (i < 0 || j < 0 || k < 0) {
return -inf;
}
if (i === 0 && j === 0) {
return 0;
}
if (f[i][j][k] !== -1) {
return f[i][j][k];
}
let res = grid[i][j];
let nk = k;
if (grid[i][j] !== 0) {
--nk;
}
const a = dfs(i - 1, j, nk);
const b = dfs(i, j - 1, nk);
res += Math.max(a, b);
f[i][j][k] = res;
return res;
};
const ans = dfs(m - 1, n - 1, k);
return ans < 0 ? -1 : ans;
}func maxPathScore(grid [][]int, k int) int {
m := len(grid)
n := len(grid[0])
inf := 1 << 30
f := make([][][]int, m)
for i := 0; i < m; i++ {
f[i] = make([][]int, n)
for j := 0; j < n; j++ {
f[i][j] = make([]int, k+1)
for t := 0; t <= k; t++ {
f[i][j][t] = -1
}
}
}
var dfs func(i, j, k int) int
dfs = func(i, j, k int) int {
if i < 0 || j < 0 || k < 0 {
return -inf
}
if i == 0 && j == 0 {
return 0
}
if f[i][j][k] != -1 {
return f[i][j][k]
}
res := grid[i][j]
nk := k
if grid[i][j] != 0 {
nk--
}
a := dfs(i-1, j, nk)
b := dfs(i, j-1, nk)
res += max(a, b)
f[i][j][k] = res
return res
}
ans := dfs(m-1, n-1, k)
if ans < 0 {
return -1
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS | O(2^(m+n)) | O(m+n) | Conceptual baseline or very small grids where exploring all paths is feasible |
| Memoized DFS (Top-Down DP) | O(m*n) | O(m*n) | General case. Eliminates repeated subproblems and is the expected interview solution |
Frequently asked questions
Is Maximum Path Score in a Grid easy or hard?
Maximum Path Score in a Grid is generally considered a medium difficulty problem. The main challenge is recognizing overlapping subproblems and applying dynamic programming or memoization to avoid exponential path exploration.
Maximum Path Score in a Grid Python/Java solution
Most implementations use memoized DFS or dynamic programming. Python typically uses recursion with an LRU cache or a 2D memo list, while Java uses a 2D DP array with recursive or iterative logic. Both achieve O(m*n) time complexity.
How to solve Maximum Path Score in a Grid in O(m*n)?
Define a DFS function that returns the best score starting from a given cell. Store results in a memoization table so repeated visits to the same cell reuse the cached value. Because each of the m*n cells is processed once, the algorithm runs in O(m*n) time.
What is the best approach for Maximum Path Score in a Grid?
The best approach is memoized depth-first search (top-down dynamic programming). Each cell represents a state, and the algorithm caches the maximum score obtainable from that cell to avoid recomputing overlapping subproblems. This reduces the complexity to O(m*n) time with O(m*n) space.
Is Maximum Path Score in a Grid asked at Google/Amazon/Meta?
Grid dynamic programming and path optimization problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of maximum path sum, minimum path sum, and grid traversal with memoization are common interview patterns.
What data structure is used in Maximum Path Score in a Grid?
The solution uses a 2D array (matrix) to represent the grid and another 2D array or hash map for memoization. Recursion or a stack drives the DFS traversal while caching intermediate results.
What is the time complexity of Maximum Path Score in a Grid?
The optimal memoization or dynamic programming solution runs in O(m*n) time, where m and n are the grid dimensions. Each cell is evaluated once and stored in a memo table. Space complexity is also O(m*n) for the cache.