Maximum Path Score in a Grid - Video Solutions
Maximum Path Score in a Grid | Detailed | Simplified | Leetcode 3742 | codestorywithMIK
Maximum Path Score in a Grid - Video Solution
Watch 10 video solutions for Maximum Path Score in a Grid, a medium level problem involving Array, Dynamic Programming, Matrix. This walkthrough by codestorywithMIK has 5,697 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 2000 <= k <= 103āāāāāāāāāāāāāāgrid[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.
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 |