Leetcode Daily Question 29/10/2024 - 2684. Maximum Number of Moves in a Grid
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 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.
Solution:
from typing import List
class Solution:
def maxMoves(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
prev = [True] * m
for j in range(1, n):
curr = [False] * m
for i in range(m):
if grid[i][j] > grid[i][j-1]:
curr[i] |= prev[i]
if i and grid[i][j] > grid[i-1][j-1]:
curr[i] |= prev[i-1]
if i + 1 < m and grid[i][j] > grid[i+1][j-1]:
curr[i] |= prev[i+1]
if sum(curr) == 0:
return j - 1
return n - 1Explanation:
We can solve this by checking if it is possible to reach the next column from the current column. When we can no longer proceed, we have found the maximum number of moves possible.
We can do this with a 1d dp array representing the first column. We initiate this dp array with True since we always start from any cell in column 0.
We then iterate column by column to see if it is possible to reach the current column from the previous.
We check each possible previous position (i, j - 1), (i - 1, j - 1), (i + 1, j - 1) to see if any of them are larger than the current cell. If so, we can use the OR operator to turn the current cell in the current column to be true.
We exit the loop early if we can not reach from any cell to the current column since the current column will all have False states. The result in this case is the current column minus 1.
Otherwise, we can reach the other side of the matrix, giving the maximum possible number moves of n - 1.
def maxMoves(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
prev = [True] * m
for j in range(1, n):
curr = [False] * m
for i in range(m):
if grid[i][j] > grid[i][j-1]:
curr[i] |= prev[i]
if i and grid[i][j] > grid[i-1][j-1]:
curr[i] |= prev[i-1]
if i + 1 < m and grid[i][j] > grid[i+1][j-1]:
curr[i] |= prev[i+1]
if sum(curr) == 0:
return j - 1
return n - 1The time complexity is O(m * n) since we potentially need to traverse each and every cell of the grid to propagate the dp table.
The space complexity is O(m) since we store a dp tables representing the starting column and current column.
The full solution can be found near the top of the page.