Count Matrix Paths Through Ordered Checkpoints
Problem statement
Start at (rows-1,0) and finish at (rows-1,columns-1). Every move advances one column and changes the row by -1, 0, or +1 while remaining in bounds.
Count paths that visit every listed checkpoint in the given order. Checkpoints have strictly increasing columns and may include either endpoint. Return the count modulo 1,000,000,007.
Function
countCheckpointPaths(rows: int, columns: int, checkpoints: int[][]) → intExamples
Example 1
rows = 3columns = 4checkpoints = [[1,1],[2,3]]return = 2Two choices reach the first checkpoint and two more steps finish at the required endpoint.
Example 2
rows = 1columns = 5checkpoints = []return = 1With one row, there is exactly one path.
Example 3
rows = 2columns = 2checkpoints = [[0,1]]return = 0The checkpoint conflicts with the required bottom-right destination, so no path qualifies.
Constraints
1 <= rows, columns <= 1000.- Checkpoint coordinates are valid and columns are strictly increasing.