aboutsummaryrefslogtreecommitdiff
path: root/max_num_moves_grid.py
diff options
context:
space:
mode:
Diffstat (limited to 'max_num_moves_grid.py')
-rw-r--r--max_num_moves_grid.py43
1 files changed, 43 insertions, 0 deletions
diff --git a/max_num_moves_grid.py b/max_num_moves_grid.py
new file mode 100644
index 0000000..cfce8b7
--- /dev/null
+++ b/max_num_moves_grid.py
@@ -0,0 +1,43 @@
+# 2684. Maximum Number of Moves in a Grid
+
+"""
+given a 0-indexed array 'm * n' 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 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 thhe
+value of the cell you are moving to should be strictly bigger than the value
+of the current cell. return the maximum number of moves that you can perform.
+"""
+
+
+class Solution(object):
+ def maxMoves(self, grid):
+ """
+ :type grid: List[List[int]]
+ :rtype: int
+ """
+ m, n, ans = len(grid), len(grid[0]), 0
+ dp = [0] * m
+ for j in range(1, n):
+ left_top, found = 0, False
+ for i in range(m):
+ next_left_top, curr = dp[i], -1
+ if i - 1 >= 0 and left_top != -1 and grid[i][j] > grid[i - 1][j - 1]:
+ curr = max(curr, left_top + 1)
+ if dp[i] != -1 and grid[i][j] > grid[i][j - 1]:
+ curr = max(curr, dp[i] + 1)
+ dp[i] = curr
+ found = found or (dp[i] != -1)
+ left_top = next_left_top
+ if not found:
+ break
+ ans = j
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.maxMoves(grid=[[2, 4, 3, 5], [5, 4, 9, 3], [3, 4, 2, 11], [10, 9, 13, 15]])
+ )
+ print(obj.maxMoves(grid=[[3, 2, 4], [2, 1, 9], [1, 1, 7]]))