FastPrepCount Matrix Paths Through Ordered Checkpoints
Problems/Count Matrix Paths Through Ordered Checkpoints

Count Matrix Paths Through Ordered Checkpoints

Google logoGoogle● HardFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report gives the task and interview context. The callable signature, deterministic tie-breaking, examples, and bounds are source-faithful reconstruction details; estimated fidelity is 90%.

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[][]) → int

Examples

Example 1

rows = 3columns = 4checkpoints = [[1,1],[2,3]]return = 2

Two choices reach the first checkpoint and two more steps finish at the required endpoint.

Example 2

rows = 1columns = 5checkpoints = []return = 1

With one row, there is exactly one path.

Example 3

rows = 2columns = 2checkpoints = [[0,1]]return = 0

The 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.

More Google problems

  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int countCheckpointPaths(int rows, int columns, int[][] checkpoints) {
        // write your code here
    }
}
Checking account…