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.

Examples

Example 1:

$$ \begin{array}{|c|c|c|c|} \hline \colorbox{orange} 2 & \colorbox{orange} 4 & 3 & 5 \ \hline 5 & 4 & \colorbox{orange} 9 & 3 \ \hline 3 & 4 & 2 & \colorbox{orange} {11} \ \hline 10 & 9 & 13 & 15 \ \hline \end{array} $$

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:

$$ \begin{array}{|c|c|c|} \hline 3 & 2 & 4 \ \hline 2 & 1 & 9 \ \hline 1 & 1 & 7 \ \hline \end{array} $$

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.

Solution

Method 1 - Recursion

In this approach, we simply recurse through each possible move without storing intermediate results. This means that the same subproblem might be solved multiple times, resulting in an exponential time complexity.

Here is the approach:

  1. For each cell (row, col), recursively check the possible moves (row-1, col+1), (row, col+1), and (row+1, col+1).
  2. Directly compute the number of moves from each cell.

Code

Java
class Solution {
    private int dfs(int[][] grid, int row, int col) {
        int m = grid.length, n = grid[0].length;
        if (col == n - 1) {  // If it's the last column, no further moves possible.
            return 0;
        }
        int max_moves = 0;
        if (row > 0 && grid[row - 1][col + 1] > grid[row][col]) {
            max_moves = Math.max(max_moves, 1 + dfs(grid, row - 1, col + 1));
        }
        if (grid[row][col + 1] > grid[row][col]) {
            max_moves = Math.max(max_moves, 1 + dfs(grid, row, col + 1));
        }
        if (row < m - 1 && grid[row + 1][col + 1] > grid[row][col]) {
            max_moves = Math.max(max_moves, 1 + dfs(grid, row + 1, col + 1));
        }
        return max_moves;
    }

    public int maxMoves(int[][] grid) {
        int m = grid.length;
        int ans = 0;
        for (int row = 0; row < m; row++) {
            ans = Math.max(ans, dfs(grid, row, 0));
        }
        return ans;
    }
}
Python
class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def dfs(row: int, col: int) -> int:
            if col == n - 1:  # If it's the last column, no further moves possible.
                return 0
            max_moves = 0
            directions = [(1, 1), (0, 1), (-1, 1)]
            for dr, dc in directions:
                new_row, new_col = row + dr, col + dc
                if 0 <= new_row < m and new_col < n and grid[new_row][new_col] > grid[row][col]:
                    max_moves = max(max_moves, 1 + dfs(new_row, new_col))
            return max_moves

        return max(dfs(row, 0) for row in range(m))

Complexity

  • ⏰ Time complexity: O(3 ^ (m * n))
  • 🧺 Space complexity: O(m + n)

Method 2 - Top Down DP with memoization

In the top-down DP approach, we’ll use memoization to store the maximum moves from each cell as we recursively calculate them.

Here is the approach:

  1. Start from any cell in the first column.
  2. Use memoization to store results of subproblems.

Code

Java
class Solution {
    private int dfs(int[][] grid, int row, int col, int[][] memo) {
        if (col == grid[0].length - 1) return 0;
        if (memo[row][col] != -1) return memo[row][col];
        int max_moves = 0;
        if (row > 0 && grid[row - 1][col + 1] > grid[row][col]) {
            max_moves = Math.max(max_moves, 1 + dfs(grid, row - 1, col + 1, memo));
        }
        if (grid[row][col + 1] > grid[row][col]) {
            max_moves = Math.max(max_moves, 1 + dfs(grid, row, col + 1, memo));
        }
        if (row < grid.length - 1 && grid[row + 1][col + 1] > grid[row][col]) {
            max_moves = Math.max(max_moves, 1 + dfs(grid, row + 1, col + 1, memo));
        }
        return memo[row][col] = max_moves;
    }

    public int maxMoves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] memo = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                memo[i][j] = -1;
            }
        }
        int ans = 0;
        for (int row = 0; row < m; row++) {
            ans = Math.max(ans, dfs(grid, row, 0, memo));
        }
        return ans;
    }
}
Python
class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        memo = [[-1] * n for _ in range(m)]
        
        def dfs(row: int, col: int) -> int:
            if memo[row][col] != -1:
                return memo[row][col]
            max_moves = 0
            directions = [(1, 1), (0, 1), (-1, 1)]
            for dr, dc in directions:
                new_row, new_col = row + dr, col + dc
                if 0 <= new_row < m and new_col < n and grid[new_row][new_col] > grid[row][col]:
                    max_moves = max(max_moves, 1 + dfs(new_row, new_col))
            memo[row][col] = max_moves
            return max_moves
        
        return max(dfs(row, 0) for row in range(m))

Complexity

  • ⏰ Time complexity: O(m * n) due to memoization.
  • 🧺 Space complexity: O(m * n) due to the recursive call stack and memoization array.

Method 3 - Bottom up DP

The bottom-up DP approach involves initializing a DP array and iteratively calculating the maximum moves for each cell starting from the last column to the first.

  1. Use an auxiliary DP array to store the maximum number of moves possible ending at each cell.
  2. Iterate through the matrix from the last column to the first column.

Here is the approach:

  1. Initialization: Start by initializing a DP array dp with same dimension as grid and all elements set to zero.
  2. Transition: For each cell (row, col), calculate the dp[row][col] based on the possible moves:
    • (row-1, col+1), (row, col+1), and (row+1, col+1).
    • Update dp[row][col] if moving to a neighbouring cell yields a higher number of moves.
  3. Result: The answer will be the maximum value in the first column of the DP array, which signifies the starting points with the highest number of moves.

Code

Java
class Solution {
    public int maxMoves(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] dp = new int[m][n];
        int ans = 0;

        for (int col = n - 2; col >= 0; col--) {
            for (int row = 0; row < m; row++) {
                if (col == 0) dp[row][col] = 0;
                if (row > 0 && grid[row - 1][col + 1] > grid[row][col]) {
                    dp[row][col] = Math.max(dp[row][col], dp[row - 1][col + 1] + 1);
                }
                if (grid[row][col + 1] > grid[row][col]) {
                    dp[row][col] = Math.max(dp[row][col], dp[row][col + 1] + 1);
                }
                if (row < m - 1 && grid[row + 1][col + 1] > grid[row][col]) {
                    dp[row][col] = Math.max(dp[row][col], dp[row + 1][col + 1] + 1);
                }
                if (col == 0) {
                    ans = Math.max(ans, dp[row][col]);
                }
            }
        }
        return ans;
    }
}
Python
class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        ans = 0

        for col in range(n - 2, -1, -1):
            for row in range(m):
                if row > 0 and grid[row - 1][col + 1] > grid[row][col]:
                    dp[row][col] = max(dp[row][col], dp[row - 1][col + 1] + 1)
                if grid[row][col + 1] > grid[row][col]:
                    dp[row][col] = max(dp[row][col], dp[row][col + 1] + 1)
                if row < m - 1 and grid[row + 1][col + 1] > grid[row][col]:
                    dp[row][col] = max(dp[row][col], dp[row + 1][col + 1] + 1)
                if col == 0:
                    ans = max(ans, dp[row][col])
                    
        return ans

Complexity

  • ⏰ Time complexity: O(m * n) - We visit each cell once and update its state based on its neighbours.
  • 🧺 Space complexity: O(m * n) - For the DP array.