# Maximum Number of Moves in a Grid
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-moves-in-a-grid)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-moves-in-a-grid
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
---
## Problem
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:**

![](https://assets.glich.co/dsa/maximum-number-of-moves-in-a-grid/image0.png) 

**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:**

![](https://assets.glich.co/dsa/maximum-number-of-moves-in-a-grid/image1.png)
**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`

# Approaches
## Brute-force Depth First Search
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.
**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).
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a global variable `maxMoves` to 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 and `grid[nextRow][nextCol] > grid[row][col]`):
    - Recursively call `dfs(nextRow, nextCol)` and update `currentMaxMoves = max(currentMaxMoves, 1 + dfs(nextRow, nextCol))`.
  - Return `currentMaxMoves`.
- Finally, return `maxMoves`.

## DFS with Memoization
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Create a 2D memoization table, `memo`, of the same dimensions as the grid, initialized with a sentinel value (e.g., `null` or -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]`.
- The final answer is the maximum value returned from the initial DFS calls.

## Bottom-Up Dynamic Programming
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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`), where `dp[r][n-1] = 0`.
- Iterate through the grid columns from right to left, from `c = n-2` down to `0`.
- For each column, iterate through the rows from `r = 0` to `m-1`.
- For each cell `(r, c)`, calculate `dp[r][c]` based on the already computed values in the next column `c+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, consider `1 + dp[nr][c+1]` moves.
  - `dp[r][c]` is the maximum of these values.
- After filling the table, the answer is the maximum value in the first column: `max(dp[i][0])` for all `i`.

## Space-Optimized Bottom-Up Dynamic Programming
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a 1D array `dp` of size `m` with 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-2` down to `0`.
- Inside the loop, create a new temporary 1D array `current_dp` of size `m` to store results for the current column `c`.
- For each row `r` from `0` to `m-1`:
  - Calculate `current_dp[r]` by checking the three possible moves to column `c+1` and using the values from the `dp` array (which holds values for column `c+1`).
  - `current_dp[r] = max(1 + dp[nr])` over valid moves.
- After iterating through all rows for column `c`, update `dp = current_dp`.
- After the main loop finishes, `dp` will hold the results for the first column. The answer is the maximum value in this `dp` array.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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 ans

```