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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Moves in a Grid

Number: 2794

Difficulty: Medium

Paid? No

Companies: Accenture, Amazon

Problem Description

Given an m x n grid of positive integers, you can start at any cell in the first column and move to the next column using one of three possible moves: top-right, right, or bottom-right. However, you may only move if the value in the destination cell is strictly greater than the value in the current cell. The goal is to determine the maximum number of moves you can perform.

Key Insights

  • Use dynamic programming to track the maximum moves possible from each cell.
  • Process the grid from rightmost column to leftmost column.
  • For each cell, the move is valid only if the target cell's value is greater than the current cell’s value.
  • The answer is the maximum value computed for cells in the first column.

Space and Time Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. Space Complexity: O(m * n) for the dp table.

Solution

We use dynamic programming by creating a 2D dp array where dp[i][j] represents the maximum number of moves possible starting from the cell at (i, j). We initialize the last column with 0 because no moves can be made from there. Then, for each cell from the second last column to the first column, we check its three potential next moves (top-right, right, and bottom-right) provided the value in the next cell is strictly greater. We update dp[i][j] as 1 plus the maximum dp value of the chosen move. Finally, we return the maximum value among all dp[i][0] (cells at the first column).

Code Solutions

# Python solution for Maximum Number of Moves in a Grid

def max_moves(grid):
    # Get grid dimensions
    m, n = len(grid), len(grid[0])
    # Initialize dp table with 0's
    dp = [[0] * n for _ in range(m)]
    
    # Process from second last column to first column
    for col in range(n - 2, -1, -1):
        for row in range(m):
            # Check three possible directions: top-right, right, bottom-right
            best_move = 0
            for new_row in [row - 1, row, row + 1]:
                new_col = col + 1
                # Ensure new position is within bounds and value is strictly increased
                if 0 <= new_row < m and grid[new_row][new_col] > grid[row][col]:
                    best_move = max(best_move, 1 + dp[new_row][new_col])
            dp[row][col] = best_move

    # The answer is the maximum moves from any starting cell in the first column
    return max(dp[row][0] for row in range(m))


# Example usage:
grid1 = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
print(max_moves(grid1))  # Expected output: 3
← Back to All Questions