Maximum number of moves in a grid

Array Dynamic Programming Matrix

58.8% acceptance

Feb 25, 2026

953

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.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_moves(grid: Vec<Vec<i32>>) -> i32 {
    let m = grid.len();
    let n = grid[0].len();
    // dp[r] = max moves to reach (r, current_col), -1 if unreachable
    // Column 0: all rows reachable with 0 moves
    let mut dp = vec![0i32; m];
    let mut ans = 0;
    for c in 1..n {
      let mut new_dp = vec![-1i32; m];
      for r in 0..m {
        for dr in [-1i32, 0, 1] {
          let pr = r as i32 + dr;
          if pr < 0 || pr >= m as i32 { continue; }
          let pr = pr as usize;
          if dp[pr] < 0 { continue; }
          if grid[r][c] > grid[pr][c - 1] {
            new_dp[r] = new_dp[r].max(dp[pr] + 1);
          }
        }
        if new_dp[r] >= 0 { ans = ans.max(new_dp[r]); }
      }
      dp = new_dp;
    }
    ans
  }
}