Maximum Path Score in a Grid - Solution & Explanation

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

Q: 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.

MediumArray Dynamic Programming Matrix13 min readAsked at: Microsoft, Google

Practice this problem

Problem Statement

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 <= 200
0 <= k <= 10³
grid[0][0] == 0
0 <= 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 cost k is less than 0, return negative infinity to indicate that the endpoint cannot be reached.
If the current coordinate is the starting point (0, 0), return 0, indicating that the endpoint has been reached (the problem guarantees the starting point has value 0).
Calculate the score contribution res of the current cell. If the current cell's value is not 0, decrement the remaining cost k by 1.
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 exceeding k, denoted as a and b respectively.
Add the current cell's score contribution res to max(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.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed 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

Video Solution

Maximum Path Score in a Grid | Detailed | Simplified | Leetcode 3742 | codestorywithMIK • codestorywithMIK • 5,697 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Path Score in a Grid with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance53.7%

Approaches1

Reading time13 min

Asked at

Microsoft Google