Problem Description

You have a 2D matrix grid with m rows and n columns, where all values are positive integers. Your task is to find the maximum number of moves you can make while traversing through the matrix.

Starting Position: You can start from any cell in the first column (column 0).

Movement Rules: From any cell at position (row, col), you can move to one of three cells in the next column:

• Move diagonally up-right to (row - 1, col + 1)
• Move right to (row, col + 1)
• Move diagonally down-right to (row + 1, col + 1)

Movement Constraint: You can only move to a cell if its value is strictly greater than your current cell's value. In other words, if you're at cell (row, col) with value grid[row][col], you can only move to cell (row', col + 1) if grid[row'][col + 1] > grid[row][col].

Goal: Find the maximum number of moves (steps to the right) you can make following these rules. Each move takes you exactly one column to the right.

For example, if you can traverse from column 0 to column 3, you've made 3 moves. The problem asks for the maximum possible moves achievable by choosing the optimal starting cell and path.

Intuition

The key insight is that we want to find the maximum distance (in terms of columns) we can travel from the first column. Since we can start from any row in the first column, we need to explore all possible starting positions.

Think of this problem as a level-by-level exploration. At each column (level), we want to know: "Which rows are still reachable?" We start with all rows in column 0 being reachable since we can start from any of them.

For each subsequent column, we check: from all currently reachable rows, which rows in the next column can we reach? A row in the next column is reachable if:

1. It's a valid neighbor (diagonal up, straight, or diagonal down)
2. Its value is strictly greater than the current cell's value

The process continues column by column. If at any point we can't reach any row in the next column, we've found our maximum moves - it's the current column index. If we successfully reach the last column, then the maximum moves is n - 1 (where n is the number of columns).

Why does this work? Because we're essentially performing a breadth-first search (BFS) where each "level" represents a column. We maintain all possible positions we could be at in the current column, then expand to find all possible positions for the next column. The use of a set ensures we don't track duplicate positions, making the solution efficient.

The beauty of this approach is that we don't need to track individual paths or use dynamic programming to remember the best path to each cell. We only care about whether a cell is reachable at each column level, which significantly simplifies the problem.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution uses a BFS approach to traverse the grid column by column. Here's how the implementation works:

Initialization:

• Create a set q containing all row indices from 0 to m-1, representing that we can start from any row in the first column
• Get the dimensions m (rows) and n (columns) of the grid

Column-by-Column Traversal:

for j in range(n - 1):

We iterate through columns from 0 to n-2 (since we're checking moves to the next column j+1).

Finding Reachable Cells in Next Column: For each column j, we:

1. Create an empty set t to store reachable rows in column j+1
2. For each currently reachable row i in set q:
   • Check three possible moves: k ranges from i-1 to i+1 (representing diagonal up, straight, and diagonal down)
   • For each potential row k:
     • Verify it's within bounds: 0 <= k < m
     • Check if the move is valid: grid[i][j] < grid[k][j + 1]
     • If both conditions are met, add k to set t

Early Termination:

if not t:
    return j

If set t is empty after checking all possible moves, it means we cannot move to column j+1 from any reachable cell in column j. Therefore, we've made j moves (from column 0 to column j).

Update for Next Iteration:

q = t

If we can continue, update q with the newly reachable rows for the next iteration.

Final Result:

return n - 1

If we successfully traverse all columns without getting stuck, we've made n-1 moves (from column 0 to column n-1).

The use of sets instead of lists is crucial here - it automatically handles duplicates when multiple cells in column j can reach the same cell in column j+1, preventing redundant checks and improving efficiency.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3×4 grid:

grid = [[2, 4, 3, 5],
        [5, 4, 9, 3],
        [3, 4, 2, 11]]

Initial Setup:

• m = 3 (rows), n = 4 (columns)
• q = {0, 1, 2} - we can start from any row in column 0

Iteration 1: From column 0 to column 1 (j = 0)

• Create empty set t for reachable rows in column 1
• Check from row 0 (value = 2):
  • Can move to row 0, col 1? 2 < 4 ✓ → add 0 to t
  • Can move to row 1, col 1? 2 < 4 ✓ → add 1 to t
• Check from row 1 (value = 5):
  • Can move to row 0, col 1? 5 < 4 ✗
  • Can move to row 1, col 1? 5 < 4 ✗
  • Can move to row 2, col 1? 5 < 4 ✗
• Check from row 2 (value = 3):
  • Can move to row 1, col 1? 3 < 4 ✓ → add 1 to t (already there)
  • Can move to row 2, col 1? 3 < 4 ✓ → add 2 to t
• Result: t = {0, 1, 2}, update q = {0, 1, 2}

Iteration 2: From column 1 to column 2 (j = 1)

• Create empty set t for reachable rows in column 2
• Check from row 0 (value = 4):
  • Can move to row 0, col 2? 4 < 3 ✗
  • Can move to row 1, col 2? 4 < 9 ✓ → add 1 to t
• Check from row 1 (value = 4):
  • Can move to row 0, col 2? 4 < 3 ✗
  • Can move to row 1, col 2? 4 < 9 ✓ → add 1 to t (already there)
  • Can move to row 2, col 2? 4 < 2 ✗
• Check from row 2 (value = 4):
  • Can move to row 1, col 2? 4 < 9 ✓ → add 1 to t (already there)
  • Can move to row 2, col 2? 4 < 2 ✗
• Result: t = {1}, update q = {1}

Iteration 3: From column 2 to column 3 (j = 2)

• Create empty set t for reachable rows in column 3
• Check from row 1 (value = 9):
  • Can move to row 0, col 3? 9 < 5 ✗
  • Can move to row 1, col 3? 9 < 3 ✗
  • Can move to row 2, col 3? 9 < 11 ✓ → add 2 to t
• Result: t = {2}, update q = {2}

End of Loop: We've successfully traversed all columns (reached column 3), so we return n - 1 = 3.

The maximum number of moves is 3, achieved by following the path:

• Start at (0, 0) with value 2
• Move to (1, 1) with value 4
• Move to (1, 2) with value 9
• Move to (2, 3) with value 11

Note how the algorithm doesn't track specific paths but instead maintains all reachable positions at each column level, efficiently finding the maximum possible moves.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm uses a BFS-like approach that processes the grid column by column from left to right. For each column j (from 0 to n-2), it examines all valid row positions in set q. For each row position i in q, it checks at most 3 adjacent positions (i-1, i, i+1) in the next column. In the worst case, all m rows could be valid positions at each column, leading to examining up to 3m positions per column. Since we process n-1 columns, the total time complexity is O(3m × (n-1)), which simplifies to O(m × n).

Space Complexity: O(m)

The algorithm maintains two sets: q and t. Set q stores the valid row indices that can be reached in the current column, while set t temporarily stores the valid row indices for the next column. In the worst case, both sets could contain all m row indices, but they never exceed this size. Since we only keep track of positions for the current and next columns (not the entire path), the space complexity is O(m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Using Visited Tracking Unnecessarily

A common mistake is treating this problem like a typical graph traversal and maintaining a visited set across all iterations:

Incorrect Approach:

visited = set()  # Global visited set - WRONG!
for col in range(cols - 1):
    next_reachable_rows = set()
    for current_row in reachable_rows:
        if (current_row, col) in visited:
            continue
        visited.add((current_row, col))
        # ... rest of logic

Why it's wrong: Since we're moving strictly from left to right (column by column), we can never revisit a cell. Each column is processed exactly once, and we only move forward. Adding visited tracking not only adds unnecessary complexity but can also prevent valid paths from being explored if multiple paths converge at the same cell.

Correct Approach: Simply track reachable rows for each column without any visited set, as shown in the original solution.

2. Confusing Move Count with Column Index

Another pitfall is incorrectly calculating the number of moves:

Incorrect:

if not next_reachable_rows:
    return col + 1  # WRONG - this would count columns, not moves

Why it's wrong: If we can't move from column j to column j+1, we've made exactly j moves (from column 0 to column j). The move count represents transitions between columns, not the column indices themselves.

Correct: Return col when no further moves are possible, and cols - 1 if we reach the last column.

3. Using Lists Instead of Sets for Reachable Rows

Inefficient Approach:

reachable_rows = list(range(rows))  # Using list instead of set
for col in range(cols - 1):
    next_reachable_rows = []
    for current_row in reachable_rows:
        for next_row in range(current_row - 1, current_row + 2):
            if 0 <= next_row < rows:
                if grid[current_row][col] < grid[next_row][col + 1]:
                    next_reachable_rows.append(next_row)  # Duplicates!

Why it's problematic: Multiple cells in column j might be able to reach the same cell in column j+1. Using a list would store duplicates, leading to:

• Redundant processing in subsequent iterations
• Time complexity degradation from O(mn) to potentially O(m²n)
• Unnecessary memory usage

Correct: Use sets to automatically handle duplicates and maintain optimal performance.