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.
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; }}Video 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.