2684. Maximum Number of Moves in a Grid
Difficulty: Medium
Topics: Array
, Dynamic Programming
, Matrix
You are given a 0-indexed m x n
matrix grid
consisting of positive integers.
You can start at any cell in the first column of the matrix, and traverse the grid in the following way:
- From a cell
(row, col)
, you can move to any of the cells:(row - 1, col + 1)
,(row, col + 1)
and(row + 1, col + 1)
such that the value of the cell you move to, should be strictly bigger than the value of the current cell.
Return the maximum number of moves that you can perform.
Example 1:
- Input: grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
- Output: 3
-
Explanation: We can start at the cell (0, 0) and make the following moves:
- (0, 0) -> (0, 1).
- (0, 1) -> (1, 2).
- (1, 2) -> (2, 3). It can be shown that it is the maximum number of moves that can be made.
Example 2:
- Input: grid = [[3,2,4],[2,1,9],[1,1,7]]
- Output: 0
- Explanation: Starting from any cell in the first column we cannot perform any moves.
Constraints:
m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 105
1 <= grid[i][j] <= 106
Hint:
- Consider using dynamic programming to find the maximum number of moves that can be made from each cell.
- The final answer will be the maximum value in cells of the first column.
Solution:
We can use Dynamic Programming (DP) to keep track of the maximum number of moves from each cell, starting from any cell in the first column. Here’s the step-by-step approach:
Approach:
Define DP Array: Let
dp[row][col]
represent the maximum number of moves possible starting fromgrid[row][col]
. Initialize this with0
for all cells.-
Traverse the Grid:
- Start from the last column and move backward to the first column. For each cell in column
col
, calculate possible moves forcol-1
. - Update
dp[row][col]
based on possible moves(row - 1, col + 1)
,(row, col + 1)
, and(row + 1, col + 1)
, only if the value of the destination cell is strictly greater than the current cell.
- Start from the last column and move backward to the first column. For each cell in column
-
Calculate the Maximum Moves:
- After filling out the
dp
table, the result will be the maximum value in the first column ofdp
, as it represents the maximum moves starting from any cell in the first column.
- After filling out the
-
Edge Cases:
- Handle cases where no moves are possible (e.g., when all paths are blocked by lower or equal values in neighboring cells).
Let's implement this solution in PHP: 2684. Maximum Number of Moves in a Grid
<?php
/**
* @param Integer[][] $grid
* @return Integer
*/
function maxMoves($grid) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example usage:
$grid1 = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]];
$grid2 = [[3,2,4],[2,1,9],[1,1,7]];
echo maxMoves($grid1); // Output: 3
echo "\n";
echo maxMoves($grid2); // Output: 0
?>
Explanation:
-
dp
Initialization: We create a 2D arraydp
to store the maximum moves from each cell. -
Loop through Columns: We iterate from the second-last column to the first, updating
dp[row][col]
based on possible moves to neighboring cells in the next column. -
Maximum Moves Calculation: Finally, the maximum value in the first column of
dp
gives the result.
Complexity Analysis:
- Time Complexity: O(m x n) since we process each cell once.
-
Space Complexity: O(m x n) for the
dp
array.
This solution is efficient given the constraints and will work within the provided limits.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)