DP Grid Advanced¶
Table of Contents¶
- 1594. Maximum Non Negative Product in a Matrix (Medium)
- 1301. Number of Paths with Max Score (Hard)
- 2435. Paths in Matrix Whose Sum Is Divisible by K (Hard)
- 174. Dungeon Game (Hard)
- 329. Longest Increasing Path in a Matrix (Hard)
- 2328. Number of Increasing Paths in a Grid (Hard)
- 2267. Check if There Is a Valid Parentheses String Path (Hard)
- 1937. Maximum Number of Points with Cost (Medium)
- 3363. Find the Maximum Number of Fruits Collected (Hard)
- 1463. Cherry Pickup II (Hard)
- 741. Cherry Pickup (Hard)
- 3459. Length of Longest V-Shaped Diagonal Segment (Hard)
- 2510. Check if There is a Path With Equal Number of 0's And 1's (Medium) 👑
1594. Maximum Non Negative Product in a Matrix¶
1301. Number of Paths with Max Score¶
2435. Paths in Matrix Whose Sum Is Divisible by K¶
174. Dungeon Game¶
329. Longest Increasing Path in a Matrix¶
-
Tags: Array, Dynamic Programming, Depth First Search, Breadth First Search, Graph, Topological Sort, Memoization, Matrix
from collections import deque
from functools import cache
from typing import List
# BFS - Topological Sort
def longestIncreasingPathBFS(matrix: List[List[int]]) -> int:
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# Calculate indegrees and initialize queue in one pass
indegree = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
for dr, dc in dirs:
nr, nc = i + dr, j + dc
if (
0 <= nr < m
and 0 <= nc < n
and matrix[nr][nc] > matrix[i][j]
):
indegree[nr][nc] += 1
# Start with cells that have no smaller neighbors
queue = deque(
(i, j) for i in range(m) for j in range(n) if indegree[i][j] == 0
)
res = 0
while queue:
res += 1
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if (
0 <= nr < m
and 0 <= nc < n
and matrix[nr][nc] > matrix[r][c]
):
indegree[nr][nc] -= 1
if indegree[nr][nc] == 0:
queue.append((nr, nc))
return res
# DP - 2D
def longestIncreasingPath(matrix: List[List[int]]) -> int:
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
@cache
def dfs(r, c):
path = 1
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
path = max(path, dfs(nr, nc) + 1)
return path
res = 0
for i in range(m):
for j in range(n):
res = max(res, dfs(i, j))
return res
if __name__ == "__main__":
matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
assert longestIncreasingPath(matrix) == 4
assert longestIncreasingPathBFS(matrix) == 4
2328. Number of Increasing Paths in a Grid¶
-
Tags: Array, Dynamic Programming, Depth First Search, Breadth First Search, Graph, Topological Sort, Memoization, Matrix