We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Moves in a Grid

Difficulty: Medium

Problem Description

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 by moving to adjacent cells to the right: (row - 1, col + 1), (row, col + 1), and (row + 1, col + 1), provided the value of the cell you move to is strictly bigger than the value of the current cell. Return the maximum number of moves that you can perform.

Key Insights

  • The traversal is restricted to rightward movements only, which simplifies the problem structure.
  • Each move must strictly increase the value of the current cell, creating a dependency on the cell values.
  • Dynamic programming can be utilized to store the maximum number of moves possible from each cell in order to avoid redundant calculations.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Solution

To solve this problem, we will use a dynamic programming approach. We will create a 2D array dp where dp[i][j] represents the maximum number of moves possible starting from cell (i, j). We will initialize the values of dp to 0, and then fill it by checking possible moves from each cell in the first column to all cells in the columns to the right. For each cell, we will check the three possible move directions (diagonal up-right, straight right, diagonal down-right) and update the dp value based on the conditions. Finally, we will find the maximum value in the first column of the dp array, which will give us the result.

Code Solutions

def maxMoves(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    
    for j in range(n - 1):
        for i in range(m):
            if dp[i][j] > 0 or j == 0:  # Starting from first column
                for ni in [i - 1, i, i + 1]:  # Check three possible moves
                    if 0 <= ni < m and grid[ni][j + 1] > grid[i][j]:
                        dp[ni][j + 1] = max(dp[ni][j + 1], dp[i][j] + 1)

    return max(dp[i][-1] for i in range(m))
← Back to All Questions