Maximum Number of Moves in a Grid
MedPrompt
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.lengthn == grid[i].length2 <= m, n <= 10004 <= m * n <= 1051 <= grid[i][j] <= 106
Approaches
4 approaches with complexity analysis and trade-offs.
This approach optimizes the space complexity of the bottom-up DP solution. By observing the DP state transition, we can see that to compute the values for any column c, we only need the values from the immediately adjacent column c+1. This means we don't need to store the entire 2D DP table. We can use just two 1D arrays (one for the current column, one for the next) to store the necessary information, reducing the space complexity.
Algorithm
- Initialize a 1D array
dpof sizemwith zeros. This array will store the DP values for the column to the right of the one being currently processed. - Iterate through columns from
c = n-2down to0. - Inside the loop, create a new temporary 1D array
current_dpof sizemto store results for the current columnc. - For each row
rfrom0tom-1:- Calculate
current_dp[r]by checking the three possible moves to columnc+1and using the values from thedparray (which holds values for columnc+1). current_dp[r] = max(1 + dp[nr])over valid moves.
- Calculate
- After iterating through all rows for column
c, updatedp = current_dp. - After the main loop finishes,
dpwill hold the results for the first column. The answer is the maximum value in thisdparray.
Walkthrough
In the bottom-up DP approach, the calculation of dp[r][c] only depends on dp[...][c+1]. This dependency on only the adjacent column allows for a significant space optimization. Instead of a m x n table, we only need to maintain the DP values for one column at a time.
We can use a 1D array, let's call it dp, of size m, to store the maximum moves from each cell in a given column. We iterate from c = n-2 down to 0. In each iteration, dp holds the values for column c+1. We use another temporary array, current_dp, to compute the values for the current column c. For each row r, current_dp[r] is calculated using the values in dp. After we've computed all values for column c and stored them in current_dp, we update dp = current_dp to prepare for the next iteration (column c-1).
After the loop over all columns is complete, the dp array will contain the maximum moves starting from each cell in the first column. The final answer is the maximum value in this array.
class Solution { public int maxMoves(int[][] grid) { int m = grid.length; int n = grid[0].length; int[] dp = new int[m]; // Represents dp values for the next column (c+1) for (int c = n - 2; c >= 0; c--) { int[] current_dp = new int[m]; // Represents dp values for the current column c for (int r = 0; r < m; r++) { // Check move to (r-1, c+1) if (r > 0 && grid[r - 1][c + 1] > grid[r][c]) { current_dp[r] = Math.max(current_dp[r], 1 + dp[r - 1]); } // Check move to (r, c+1) if (grid[r][c + 1] > grid[r][c]) { current_dp[r] = Math.max(current_dp[r], 1 + dp[r]); } // Check move to (r+1, c+1) if (r < m - 1 && grid[r + 1][c + 1] > grid[r][c]) { current_dp[r] = Math.max(current_dp[r], 1 + dp[r + 1]); } } dp = current_dp; } int maxMoves = 0; for (int moves : dp) { maxMoves = Math.max(maxMoves, moves); } return maxMoves; }}Complexity
Time
O(m * n) - The time complexity remains the same as we still iterate through each cell once.
Space
O(m) - We only need two arrays of size `m` to store the DP states for the current and next columns.
Trade-offs
Pros
Most space-efficient solution while maintaining optimal time complexity.
Highly practical for problems with tight memory constraints.
Cons
The logic can be slightly more complex to implement compared to the standard 2D DP approach.
This approach involves exploring every possible path starting from each cell in the first column using a recursive Depth First Search (DFS). It's a straightforward translation of the problem description into code but suffers from severe performance issues because it repeatedly solves the same subproblems.
Algorithm
- Initialize a global variable
maxMovesto 0. - Iterate through each cell
(i, 0)in the first column. - For each starting cell, call a recursive DFS function
dfs(i, 0). - Update
maxMoves = max(maxMoves, dfs(i, 0)). - The
dfs(row, col)function works as follows:- Initialize
currentMaxMoves = 0. - Explore the three possible next positions:
(row - 1, col + 1),(row, col + 1), and(row + 1, col + 1). - For each valid next position
(nextRow, nextCol)(i.e., within grid bounds andgrid[nextRow][nextCol] > grid[row][col]):- Recursively call
dfs(nextRow, nextCol)and updatecurrentMaxMoves = max(currentMaxMoves, 1 + dfs(nextRow, nextCol)).
- Recursively call
- Return
currentMaxMoves.
- Initialize
- Finally, return
maxMoves.
Walkthrough
The core idea is to simulate all possible move sequences. We can define a recursive function, dfs(row, col), that calculates the maximum number of moves possible starting from the cell (row, col). The main part of the program will then call this function for every cell in the first column and take the maximum of the results.
Inside dfs(row, col), we check the three potential next cells. For each valid move (one that stays within the grid and moves to a cell with a strictly greater value), we make a recursive call. The number of moves from the current cell will be 1 (for the current move) plus the number of moves from the next cell. We take the maximum over all three possible moves. If no moves are possible from (row, col), the function returns 0.
This method is a classic brute-force approach. Its downfall is the overlapping subproblems; the dfs function for a particular cell might be called many times through different paths, leading to an exponential number of computations.
class Solution { public int maxMoves(int[][] grid) { int m = grid.length; int n = grid[0].length; int maxMoves = 0; // Start DFS from each cell in the first column for (int i = 0; i < m; i++) { maxMoves = Math.max(maxMoves, dfs(grid, i, 0)); } return maxMoves; } private int dfs(int[][] grid, int r, int c) { int m = grid.length; int n = grid[0].length; int currentMax = 0; // Possible moves: (r-1, c+1), (r, c+1), (r+1, c+1) int[] dr = {-1, 0, 1}; for (int i = 0; i < 3; i++) { int nr = r + dr[i]; int nc = c + 1; if (nr >= 0 && nr < m && nc < n && grid[nr][nc] > grid[r][c]) { currentMax = Math.max(currentMax, 1 + dfs(grid, nr, nc)); } } return currentMax; }}Complexity
Time
O(m * 3^n) - In the worst case, from each of the `m` starting cells, the search can branch out in 3 directions for `n-1` steps, leading to an exponential time complexity.
Space
O(n) - The space complexity is determined by the maximum depth of the recursion stack, which can be at most `n` (the number of columns).
Trade-offs
Pros
Simple to conceptualize and implement.
Cons
Extremely inefficient due to a large number of redundant computations for the same subproblems.
Will likely result in a 'Time Limit Exceeded' error for larger grids.
This approach, also known as top-down dynamic programming, enhances the brute-force DFS by using memoization. A memoization table (a 2D array) is used to store the results of subproblems (the maximum moves from a cell). When the DFS function is called for a cell, it first checks if the result is already in the table. If so, it returns the stored value, avoiding re-computation. This drastically reduces the time complexity.
Algorithm
- Create a 2D memoization table,
memo, of the same dimensions as the grid, initialized with a sentinel value (e.g.,nullor -1). - The main logic is the same as the brute-force DFS: iterate through the first column and call a recursive function
dfs(i, 0)for each cell. - The
dfs(row, col)function is modified:- First, check if
memo[row][col]has a computed value. If so, return it immediately. - If not, compute the result as in the brute-force approach by exploring the three possible next moves.
- Before returning the computed maximum moves, store it in
memo[row][col].
- First, check if
- The final answer is the maximum value returned from the initial DFS calls.
Walkthrough
To overcome the inefficiency of the brute-force approach, we can store the result for each state (row, col) once it's computed. We use a 2D array, memo, of the same size as the grid for this purpose. memo[r][c] will store the maximum number of moves starting from cell (r, c).
The dfs function is modified to accept this memo table. At the beginning of the function, it checks if memo[r][c] has been computed. If it has, the stored value is returned. Otherwise, the computation proceeds as before. Once the result is calculated, it's stored in memo[r][c] before being returned. This ensures that for any given cell, the calculation is performed only once.
class Solution { public int maxMoves(int[][] grid) { int m = grid.length; int n = grid[0].length; Integer[][] memo = new Integer[m][n]; int maxMoves = 0; for (int i = 0; i < m; i++) { maxMoves = Math.max(maxMoves, dfs(grid, i, 0, memo)); } return maxMoves; } private int dfs(int[][] grid, int r, int c, Integer[][] memo) { if (memo[r][c] != null) { return memo[r][c]; } int m = grid.length; int n = grid[0].length; int currentMax = 0; int[] dr = {-1, 0, 1}; for (int i = 0; i < 3; i++) { int nr = r + dr[i]; int nc = c + 1; if (nr >= 0 && nr < m && nc < n && grid[nr][nc] > grid[r][c]) { currentMax = Math.max(currentMax, 1 + dfs(grid, nr, nc, memo)); } } return memo[r][c] = currentMax; }}Complexity
Time
O(m * n) - Each state `(row, col)` is computed exactly once. The computation for each state takes constant time (checking 3 neighbors).
Space
O(m * n) - For the memoization table. The recursion stack also contributes up to O(n) space.
Trade-offs
Pros
Guarantees that each subproblem is solved only once, making it much more efficient.
Correctly solves the problem within the time limits.
Cons
Requires extra space for the memoization table, which can be large for big grids.
Deep recursion could potentially lead to a stack overflow, although unlikely with the given constraints.
This approach uses bottom-up dynamic programming, also known as tabulation. Instead of recursion, we use an iterative approach to fill a DP table. Let dp[r][c] be the maximum number of moves starting from cell (r, c). Since moves are always to the next column, we can compute the values for column c if we know the values for column c+1. This suggests filling the DP table from right to left.
Algorithm
- Create a 2D DP table,
dp[m][n], initialized to all zeros.dp[r][c]will store the max moves from cell(r, c). - The base cases are the cells in the last column (
c = n-1), wheredp[r][n-1] = 0. - Iterate through the grid columns from right to left, from
c = n-2down to0. - For each column, iterate through the rows from
r = 0tom-1. - For each cell
(r, c), calculatedp[r][c]based on the already computed values in the next columnc+1:- Check the three potential next cells
(r-1, c+1),(r, c+1),(r+1, c+1). - If a move to
(nr, c+1)is valid, consider1 + dp[nr][c+1]moves. dp[r][c]is the maximum of these values.
- Check the three potential next cells
- After filling the table, the answer is the maximum value in the first column:
max(dp[i][0])for alli.
Walkthrough
We create a 2D array dp of size m x n. dp[r][c] will store the maximum number of moves that can be performed starting from cell (r, c). The cells in the last column (c = n-1) can't make any more moves, so dp[r][n-1] is 0 for all r. We can initialize the entire dp table with zeros to handle this base case.
We then iterate from the second-to-last column (c = n-2) down to the first column (c = 0). For each cell (r, c), we calculate dp[r][c] by looking at the three possible destination cells in column c+1. For each valid move to a cell (nr, c+1), the number of moves would be 1 + dp[nr][c+1]. We take the maximum over all valid moves. If no moves are possible, dp[r][c] remains 0.
After the loops complete, the first column of the dp table, dp[i][0], contains the maximum moves starting from each cell in the first column. The final answer is the maximum value in this first column.
class Solution { public int maxMoves(int[][] grid) { int m = grid.length; int n = grid[0].length; int[][] dp = new int[m][n]; int maxMoves = 0; for (int c = n - 2; c >= 0; c--) { for (int r = 0; r < m; r++) { // Check move to (r-1, c+1) if (r > 0 && grid[r - 1][c + 1] > grid[r][c]) { dp[r][c] = Math.max(dp[r][c], 1 + dp[r - 1][c + 1]); } // Check move to (r, c+1) if (grid[r][c + 1] > grid[r][c]) { dp[r][c] = Math.max(dp[r][c], 1 + dp[r][c + 1]); } // Check move to (r+1, c+1) if (r < m - 1 && grid[r + 1][c + 1] > grid[r][c]) { dp[r][c] = Math.max(dp[r][c], 1 + dp[r + 1][c + 1]); } } } for (int i = 0; i < m; i++) { maxMoves = Math.max(maxMoves, dp[i][0]); } return maxMoves; }}Complexity
Time
O(m * n) - We iterate through each cell of the grid (from right to left) once, performing constant work at each cell.
Space
O(m * n) - We use a 2D DP table of the same size as the grid.
Trade-offs
Pros
Avoids recursion, eliminating the risk of stack overflow and potentially offering a slight performance improvement due to lower overhead.
The logic is often easier to reason about for tabulation fans.
Cons
Requires O(m * n) space, which is the same as the memoization approach.
Solutions
Solution
class Solution {public int maxMoves(int[][] grid) { int[][] dirs = {{-1, 1}, {0, 1}, {1, 1}}; int m = grid.length, n = grid[0].length; Deque<int[]> q = new ArrayDeque<>(); for (int i = 0; i < m; ++i) { q.offer(new int[]{i, 0}); } int[][] dist = new int[m][n]; int ans = 0; while (!q.isEmpty()) { var p = q.poll(); int i = p[0], j = p[1]; for (var dir : dirs) { int x = i + dir[0], y = j + dir[1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > grid[i][j] && dist[x][y] < dist[i][j] + 1) { dist[x][y] = dist[i][j] + 1; ans = Math.max(ans, dist[x][y]); q.offer(new int[]{x, y}); } } } return ans; }}class Solution {public: int maxMoves(vector<vector<int>> &grid) { int m = grid.size(), n = grid[0].size(); int dist[m][n]; memset(dist, 0, sizeof(dist)); int ans = 0; queue<pair<int, int>> q; for (int i = 0; i < m; ++i) { q.emplace(i, 0); } int dirs[3][2] = {{-1, 1}, {0, 1}, {1, 1}}; while (!q.empty()) { auto [i, j] = q.front(); q.pop(); for (int k = 0; k < 3; ++k) { int x = i + dirs[k][0], y = j + dirs[k][1]; if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] > grid[i][j] && dist[x][y] < dist[i][j] + 1) { dist[x][y] = dist[i][j] + 1; ans = max(ans, dist[x][y]); q.emplace(x, y); } } } return ans; }};class Solution: def maxMoves(self, grid: List[List[int]]) -> int: dirs = ((- 1, 1), (0, 1), (1, 1)) m, n = len(grid), len(grid[0]) q = deque((i, 0) for i in range(m)) dist = [[0] * n for _ in range(m)] ans = 0 while q: i, j = q . popleft() for a, b in dirs: x, y = i + a, j + b if (0 <= x < m and 0 <= y < n and grid[x][y] > grid[i][j] and dist[x][y] < dist[i][j] + 1): dist[x][y] = dist[i][j] + 1 ans = max(ans, dist[x][y]) q . append((x, y)) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.