Maximum Number of Moves in a Grid

Maximum Number of Moves in a Grid

What is this problem about?

The Maximum Number of Moves in a Grid coding problem gives you an m×n grid. Starting from any cell in the first column, you can move to the cell to the right, upper-right, or lower-right, but only if the destination cell has a strictly greater value than the current cell. Find the maximum number of moves you can make.

Why is this asked in interviews?

Amazon, Accenture, and Google use this problem to test column-by-column dynamic programming. It is a path-finding problem with a strict increase constraint and diagonal moves allowed — a non-standard variant that requires careful DP state design. Candidates who recognize this as a column-wise DP with three predecessors per cell demonstrate clean algorithmic thinking.

Algorithmic pattern used

Column-by-column DP: Define dp[i][j] = maximum moves to reach cell (i, j). Initialize dp[i][0] = 0 for all i (start at column 0). For each column j from 1 to n-1, for each cell (i, j): check its three predecessors (i-1, j-1), (i, j-1), (i+1, j-1). If the predecessor is reachable and grid[i][j] > grid[pred], update dp[i][j] = dp[pred][j-1] + 1. The answer is the maximum dp value across all columns. Track reachability separately (a cell is reachable if dp > 0 or it's column 0).

Example explanation

Grid:

2  4  3  5
5  1  9  3
3  8  6  1

• Column 0: all reachable (moves=0).
• Column 1: (0,1)=4 from (0,0)=2 ✓ (1 move), (1,1)=1 from anything: 1<2,1<5,1<3 → not reachable. (2,1)=8 from (1,0)=5 ✓ (1 move) or (2,0)=3 ✓ (1 move).
• Column 2: (0,2)=3 from (0,1)=4? 3<4 ✗. From (1,1)=1? 1 unreachable. Not reachable. (1,2)=9 from (0,1)=4 ✓ → 2 moves, or (2,1)=8 ✓ → 2 moves. (2,2)=6 from (2,1)=8? 6<8 ✗.
• Column 3: (0,3)=5 from (1,2)=9? 5<9 ✗. (1,3)=3 from (1,2)=9? ✗.
• Max moves = 2.

Common mistakes candidates make

• Not tracking reachability: Cells in column 0 are all reachable but subsequent cells may be entirely unreachable. Don't count dp[i][j]=0 as a reachable cell.
• Boundary checks for diagonal moves: Row i-1 and i+1 may be out of bounds. Always validate row indices.
• Starting from only one row: Any cell in column 0 is a valid start.

Interview preparation tip

For the Array Matrix Dynamic Programming interview pattern, this is a "grid DP with multi-directional predecessors" problem. The key is initializing all column-0 cells as reachable with 0 moves, then sweeping column by column. This pattern (column-sweep DP) applies to many grid path problems with movement constraints.