LeetCode Problem 2684

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

LeetCode 2684 - Maximum Number of Moves in a Grid

Problem Understanding

The problem gives us an m x n matrix called grid, where every cell contains a positive integer. We may begin from any row in the first column, meaning any cell (row, 0) is a valid starting point.

From a current position (row, col), we are only allowed to move to the next column, specifically to one of these three cells:

• (row - 1, col + 1), the upper-right diagonal
• (row, col + 1), directly right
• (row + 1, col + 1), the lower-right diagonal

However, a move is only valid if the destination cell contains a strictly larger value than the current cell.

The goal is to compute the maximum number of moves possible. A move means transitioning from one cell to another. If we cannot move anywhere from the starting cell, the answer is 0.

The constraints are important:

• m and n can each be as large as 1000
• The total number of cells is at most 10^5

This immediately tells us that exponential search is impossible. Even a solution with quadratic work per cell would likely be too slow. We need an algorithm close to linear in the number of cells.

An important observation is that every move always goes from column c to column c + 1. This means the graph of possible moves is a Directed Acyclic Graph, because we never move backward. That property makes dynamic programming a natural fit.

There are several edge cases that can cause issues in naive implementations:

• A grid where no moves are possible from any starting position
• A grid where many paths overlap, causing repeated recomputation in brute-force DFS
• Boundary rows where upward or downward diagonal moves would go outside the grid
• Large grids where recursive DFS without memoization would time out

The problem guarantees all values are positive integers and that the grid dimensions are valid.

Approaches

Brute Force Approach

A straightforward solution is to try every possible path starting from every row in the first column.

We can perform a Depth First Search from each starting cell. At every position, we recursively try all three valid directions if the destination value is strictly larger.

This approach is correct because it explores every legal path and therefore eventually finds the maximum number of moves.

The problem is efficiency. A cell can branch into as many as three new paths, and many subproblems repeat. For example, multiple paths may eventually arrive at the same cell, causing the same subtree of computations to be recalculated repeatedly.

In the worst case, the number of paths grows exponentially with the number of columns.

Optimal Approach

The key insight is that the answer for a cell depends only on cells in the next column.

If we define:

dp[row][col] = maximum moves starting from (row, col)

then:

• We look at the three reachable neighbors in column col + 1
• For every valid move, we can take 1 + dp[next_row][col + 1]
• The best among those becomes dp[row][col]

Because moves always go left to right, we can process columns from right to left. When computing a cell, all required future states are already known.

This transforms the exponential search into dynamic programming with one computation per cell.

Approach	Time Complexity	Space Complexity	Notes
Brute Force DFS	O(3^n)	O(n)	Explores all possible paths recursively
Dynamic Programming	O(m × n)	O(m × n)	Computes each state once

Algorithm Walkthrough

1. Let m be the number of rows and n be the number of columns.
2. Create a DP table dp of size m x n, initialized with 0.

The value dp[r][c] will represent the maximum number of moves possible starting from cell (r, c). 3. Process columns from right to left.

We move backward because every transition depends on cells in the next column. 4. For each cell (r, c), check the three possible destinations:

• (r - 1, c + 1)
• (r, c + 1)
• (r + 1, c + 1)

5. For each destination:

• Verify the row is inside bounds
• Verify the destination value is strictly larger

If both conditions hold, update:

dp[r][c] = max(dp[r][c], 1 + dp[next_row][c + 1])

6. After processing all columns, examine every cell in the first column.

Since we may start from any row, the final answer is:

max(dp[row][0] for all rows)

Why it works

The algorithm works because every valid move always advances exactly one column to the right. This creates a Directed Acyclic Graph structure where future states never depend on earlier columns.

By processing columns from right to left, every state already has its future answers computed before it is evaluated. The recurrence correctly considers every valid next move and chooses the maximum possible continuation, guaranteeing the optimal result.

Python Solution

from typing import List

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        dp = [[0] * cols for _ in range(rows)]

        for col in range(cols - 2, -1, -1):
            for row in range(rows):
                for next_row in (row - 1, row, row + 1):
                    if 0 <= next_row < rows:
                        if grid[next_row][col + 1] > grid[row][col]:
                            dp[row][col] = max(
                                dp[row][col],
                                1 + dp[next_row][col + 1]
                            )

        return max(dp[row][0] for row in range(rows))

The implementation begins by determining the grid dimensions. A DP table of the same size is created, where every cell initially contains 0, meaning no moves are currently known.

The algorithm iterates through columns in reverse order, beginning from the second-last column because the last column cannot move anywhere.

For every cell, the code checks the three allowed directions. Boundary checks prevent invalid row access. The strict inequality condition ensures we only move to larger values.

Whenever a valid transition exists, the DP state is updated using the recurrence relation:

1 + dp[next_row][next_col]

The final step scans the first column because any row may be used as the starting point.

Go Solution

func maxMoves(grid [][]int) int {
    rows := len(grid)
    cols := len(grid[0])

    dp := make([][]int, rows)
    for i := 0; i < rows; i++ {
        dp[i] = make([]int, cols)
    }

    directions := []int{-1, 0, 1}

    for col := cols - 2; col >= 0; col-- {
        for row := 0; row < rows; row++ {
            for _, d := range directions {
                nextRow := row + d

                if nextRow >= 0 && nextRow < rows {
                    if grid[nextRow][col+1] > grid[row][col] {
                        candidate := 1 + dp[nextRow][col+1]

                        if candidate > dp[row][col] {
                            dp[row][col] = candidate
                        }
                    }
                }
            }
        }
    }

    answer := 0

    for row := 0; row < rows; row++ {
        if dp[row][0] > answer {
            answer = dp[row][0]
        }
    }

    return answer
}

The Go implementation follows the same logic as the Python version. A two-dimensional slice is allocated for the DP table.

Go does not provide a built-in max function for integers in older versions, so comparisons are handled manually with conditional statements.

Since all values fit comfortably within standard integer ranges, there are no overflow concerns.

Worked Examples

Example 1

grid =
[
  [2, 4, 3, 5],
  [5, 4, 9, 3],
  [3, 4, 2,11],
  [10,9,13,15]
]

We process from right to left.

Initial DP Table

Row	Col0	Col1	Col2	Col3
0	0	0	0	0
1	0	0	0	0
2	0	0	0	0
3	0	0	0	0

Processing Column 2

Cell (0,2)=3

• Can move to (0,3)=5
• dp[0][2] = 1

Cell (1,2)=9

• Cannot move anywhere

Cell (2,2)=2

• Can move to (2,3)=11
• Can move to (3,3)=15
• dp[2][2] = 1

Cell (3,2)=13

• Can move to (3,3)=15
• dp[3][2] = 1

DP Table

Row	Col0	Col1	Col2	Col3
0	0	0	1	0
1	0	0	0	0
2	0	0	1	0
3	0	0	1	0

Processing Column 1

Cell (0,1)=4

• Can move to (1,2)=9
• dp[0][1] = 1

Cell (1,1)=4

• Can move to (1,2)=9
• dp[1][1] = 1

Cell (2,1)=4

• Can move to (1,2)=9
• dp[2][1] = 1

Cell (3,1)=9

• Can move to (3,2)=13
• dp[3][1] = 2

Processing Column 0

Cell (0,0)=2

• Can move to (0,1)=4
• Best continuation gives:

1 + dp[0][1] = 2

Cell (2,0)=3

• Can move to (2,1)=4
• Gives 2

Final answer becomes 3.

Example 2

grid =
[
  [3,2,4],
  [2,1,9],
  [1,1,7]
]

From every starting position, no valid increasing move exists from column 0 to column 1.

Therefore all DP values remain 0.

Answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Every cell checks at most three neighbors
Space	O(m × n)	DP table stores one value per cell

The algorithm visits each cell exactly once and performs only constant work per cell. Since each state checks at most three neighbors, the runtime is linear in the number of grid cells.

The DP table requires storage proportional to the grid size.

Test Cases

from typing import List

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        dp = [[0] * cols for _ in range(rows)]

        for col in range(cols - 2, -1, -1):
            for row in range(rows):
                for next_row in (row - 1, row, row + 1):
                    if 0 <= next_row < rows:
                        if grid[next_row][col + 1] > grid[row][col]:
                            dp[row][col] = max(
                                dp[row][col],
                                1 + dp[next_row][col + 1]
                            )

        return max(dp[row][0] for row in range(rows))

solution = Solution()

assert solution.maxMoves(
    [[2,4,3,5],
     [5,4,9,3],
     [3,4,2,11],
     [10,9,13,15]]
) == 3  # provided example 1

assert solution.maxMoves(
    [[3,2,4],
     [2,1,9],
     [1,1,7]]
) == 0  # provided example 2

assert solution.maxMoves(
    [[1,2,3,4]]
) == 3  # single row increasing

assert solution.maxMoves(
    [[4,3,2,1]]
) == 0  # single row decreasing

assert solution.maxMoves(
    [[1],
     [2],
     [3]]
) == 0  # single column, no moves possible

assert solution.maxMoves(
    [[1,10,20],
     [2,3,30],
     [1,4,5]]
) == 2  # multiple possible paths

assert solution.maxMoves(
    [[1,2],
     [3,4]]
) == 1  # smallest valid movement case

assert solution.maxMoves(
    [[1,1,1],
     [1,1,1]]
) == 0  # equal values are invalid moves

assert solution.maxMoves(
    [[1,5,9,10],
     [2,3,8,11],
     [4,6,7,12]]
) == 3  # optimal zig-zag path

Test	Why
Example 1 grid	Validates standard multi-step traversal
Example 2 grid	Validates no valid moves
Single increasing row	Tests straight-line progression
Single decreasing row	Tests immediate dead end
Single column grid	Ensures zero moves when no next column exists
Multiple path choices	Verifies optimal path selection
Small 2x2 grid	Tests minimal valid dimensions
Equal values grid	Confirms strict inequality handling
Zig-zag increasing path	Verifies diagonal transitions

Edge Cases

No Valid Moves Anywhere

A grid may contain values such that no cell can move to a larger value in the next column. This is easy to mishandle if the algorithm assumes every position contributes at least one move.

The implementation handles this naturally because every DP state starts at 0. If no valid neighbor exists, the value remains 0.

Boundary Rows

Cells in the top row cannot move upward, and cells in the bottom row cannot move downward. Without careful bounds checking, this can cause index-out-of-range errors.

The implementation explicitly checks:

0 <= next_row < rows

before accessing neighboring cells.

Equal Neighbor Values

Moves are only allowed when the next value is strictly greater. Using >= by mistake would produce incorrect paths.

The implementation correctly uses:

grid[next_row][col + 1] > grid[row][col]

which enforces the strict inequality exactly as required.

Single Column Grid

If the grid has only one column, movement is impossible because every move requires advancing to the next column.

The algorithm handles this correctly because the reverse column loop never executes, leaving all DP values at 0. The final answer therefore becomes 0.