Watch 10 video solutions for Maximum Number of Moves in a Grid, a medium level problem involving Array, Dynamic Programming, Matrix. This walkthrough by codestorywithMIK has 6,260 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
(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.lengthn == grid[i].length2 <= m, n <= 10004 <= m * n <= 1051 <= grid[i][j] <= 106Problem Overview: You are given an m x n grid of integers. Starting from any cell in the first column, you can move to (row-1, col+1), (row, col+1), or (row+1, col+1) if the destination value is strictly greater than the current cell. The task is to compute the maximum number of moves possible following these rules.
Approach 1: Divide and Conquer with DFS + Memoization (O(m * n) time, O(m * n) space)
Treat each cell as the start of a subproblem: the maximum moves you can make beginning from that position. From cell (r, c), recursively explore the three valid next positions in column c + 1 that contain larger values. Without caching, this would recompute the same paths many times. Memoization stores the result for each cell so every state is solved once. The recursion effectively performs a depth‑first search across the grid while caching results in a DP table. This approach maps naturally to dynamic programming over a matrix, and the state transition simply picks the best of the three possible moves.
Approach 2: Iterative Subproblem Solving (Bottom‑Up DP) (O(m * n) time, O(m * n) space)
The recursive solution can be converted into a bottom‑up DP. Process columns from right to left since moves always go to col + 1. Maintain a DP table where dp[r][c] represents the maximum moves starting from cell (r, c). For each cell, check the three possible neighbors in the next column. If the neighbor’s value is larger, update dp[r][c] = 1 + dp[next]. The answer is the maximum value among all cells in the first column. This avoids recursion overhead and keeps the transition logic explicit. Iterating column by column also makes boundary handling easier when working with arrays and grids.
Recommended for interviews: The DFS + memoization approach clearly shows the state transition and demonstrates strong understanding of dynamic programming on grids. Interviewers often expect you to first describe the recursive exploration and then optimize it with memoization. The bottom‑up DP version shows additional maturity by eliminating recursion and computing the same states iteratively.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer (DFS + Memoization) | O(m * n) | O(m * n) | When modeling the problem recursively or explaining the DP state transition during interviews |
| Iterative Subproblem Solving (Bottom-Up DP) | O(m * n) | O(m * n) | When you want an iterative solution without recursion overhead and clearer DP table updates |