2684. Maximum Number of Moves in a Grid


Problem Description

In the given problem, we have a 0-indexed matrix with dimensions m x n, which means it has m rows and n columns. Each cell of this matrix contains a positive integer. The challenge is to navigate through the matrix starting from any cell in the first column and make a sequence of moves to traverse the grid. The rules for moving from one cell to the next are as follows:

  • You can move diagonally up to the right, straight to the right, or diagonally down to the right. In other words, from a cell (row, col), you can move to (row - 1, col + 1), (row, col + 1), or (row + 1, col + 1).
  • The value of the cell you move to must be strictly greater than the value of the current cell.

The goal is to find out the maximum number of moves you can perform while respecting these constraints.

Intuition

To solve this problem, we can think of it as a graph traversal issue, where each cell of the matrix represents a node, and a directed edge connects two nodes if it's possible to move from one to the other following the rules stated above.

Since we are looking for the maximum number of moves, a breadth-first search (BFS) approach is suitable because it explores neighbors first before moving to the next level. This will ensure that we visit each cell at least once while keeping track of the number of moves made.

Here’s the step-by-step intuition behind the algorithm:

  1. Initialize a queue: We begin by adding all cells in the first column to the queue as possible starting points.
  2. Track distances: We also keep a distance matrix, which holds the maximum number of moves made to reach a given cell.
  3. Explore neighbors: For each cell, explore the three potential moves that can be made (straight to the right, diagonally up to the right, or diagonally down to the right). We check that the move is within the bounds of the matrix, and that the value of the target cell is greater than that of the current cell.
  4. Update distance and queue: If we find a valid move that also allows us to increase the distance (number of moves), we update the distance for the target cell and add it to the queue to explore its neighbors next.
  5. Maximize the moves: Whenever we update the distances, we also keep track of the maximum distance encountered.
  6. Repeat until done: We repeat the process until the queue is empty, indicating we've explored every possible move from each starting cell.

By using BFS and a distance matrix, we ensure that we count the maximum possible moves from any starting cell in the first column to any other reachable cell.

Solution Approach

The implementation of the solution involves the use of a Breadth-First Search (BFS), a deque data structure for efficient pop and append operations, and a 2D list to maintain the distance travelled to each cell. Below is a step-by-step walk through the algorithm illustrated by the given Python code:

  1. Import deque: Before starting, a deque from the collections module is imported, providing a double-ended queue which allows for fast appends and pops from both ends.
1from collections import deque
  1. Define move directions: A tuple of tuples dirs is created defining the three possible directions in which we can move from any cell — up-right, right, and down-right.
1dirs = ((-1, 1), (0, 1), (1, 1))
  1. Initialize data structures:
  • The dimensions of the grid are assigned to m and n.
  • A deque called q is created and initialized with all the row indices and column zero. This represents the valid starting positions.
  • A 2D list called dist is created to keep track of the maximum distance (number of moves) for each cell. It is initialized with zeros, implying that initially, no moves have been made.
  • A variable ans is set to zero to keep track of the maximum number of moves encountered.
1m, n = len(grid), len(grid[0])
2q = deque((i, 0) for i in range(m))
3dist = [[0] * n for _ in range(m)]
4ans = 0
  1. BFS algorithm: A while loop is initiated to process all cells in the q.
  • From the current cell (i, j), all three possible moves are considered.
  • For each move, validate the new cell indices (x, y) are within the grid's bounds and that the move leads to a larger value.
  • Next, check if the distance dist[x][y] can be increased, indicating that a longer path to the cell (x, y) has been found.
  • If the conditions are met, update dist[x][y] with the incremented count and insert the new cell (x, y) into the queue to process its neighbors as well.
  • While updating the distance, also update the ans variable to maintain the maximum number of moves encountered across all paths in the grid.
1while q:
2    i, j = q.popleft()
3    for a, b in dirs:
4        x, y = i + a, j + b
5        if (
6            0 <= x < m
7            and 0 <= y < n
8            and grid[x][y] > grid[i][j]
9            and dist[x][y] < dist[i][j] + 1
10        ):
11            dist[x][y] = dist[i][j] + 1
12            ans = max(ans, dist[x][y])
13            q.append((x, y))
  1. Return solution: After the BFS loop exits, ans represents the maximum number of moves that can be performed in the grid. Therefore, ans is returned as the solution to the problem.
1return ans

This approach efficiently traverses the matrix ensuring that it records the maximum moves to reach each cell. The breadth-first nature of the algorithm ensures it finds the longest path from the first column to any column by visiting vertices in increasing order of their distances from the start, hence capturing the maximum number of moves possible.

Example Walkthrough

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

Assume we have the following 3x3 matrix:

1grid = [
2    [1, 2, 3],
3    [6, 5, 4],
4    [7, 3, 8]
5]

Here's how the algorithm would process this grid:

  1. Import deque: We import the deque to use a double-ended queue for our BFS.

  2. Define move directions: The directions we can move to from any cell are ((-1, 1), (0, 1), (1, 1)) corresponding to up-right, right, and down-right.

  3. Initialize data structures:

  • Get the grid dimensions m=3, n=3.
  • Initialize q with all cells in the first column: deque([(0, 0), (1, 0), (2, 0)]).
  • Initialize dist with zeros [[0, 0, 0], [0, 0, 0], [0, 0, 0]].
  • Initialize ans = 0.
  1. BFS algorithm: Process all cells in q:
  • Start with the first element in q: (0, 0).
  • Check the three possible moves from (0, 0): (0, 1), (-1, 1) (invalid as it's outside the grid), (1, 1).
  • Move from (0, 0) to (0, 1) since grid[0][1] > grid[0][0] and update dist[0][1] = 1 and ans = 1. Add (0, 1) to q.
  • Move from (0, 0) to (1, 1) is disallowed since grid[1][1] < grid[0][0].
  • Process the next element in q: (1, 0).
  • Check the three possible moves from (1, 0): (0, 1), (1, 1), (2, 1).
  • All moves are disallowed since dist[x][y] cannot be increased.
  • Now, process (2, 0).
  • Check three possible moves: (1, 1), (2, 1), (3, 1) (invalid as it's outside the grid).
  • (1, 1) is allowed, dist[1][1] = 1 and ans remains 1. Add (1, 1) to q.
  • (2, 1) is allowed, dist[2][1] = 1 and ans remains 1. Add (2, 1) to q.
  • Continue the process until q is empty, updating ans and dist as we find larger paths.
  1. Return solution: After the while loop exits, ans will be 1 in this case since there is no path in the grid that allows more than one move. Thus, we would return 1 as the solution to the problem.

This example demonstrates the algorithm finding the maximum number of moves to navigate through a provided grid of numbers, following the rules of strictly increasing values and the allowed directions of movement.

Python Solution

1from collections import deque
2
3class Solution:
4    def max_moves(self, grid):
5        # Define the directions in which to move (up-right, right, down-right)
6        directions = ((-1, 1), (0, 1), (1, 1))
7      
8        # Get the dimensions of the grid
9        num_rows, num_cols = len(grid), len(grid[0])
10      
11        # Initialize a queue with all possible starting positions in the first column
12        queue = deque((row, 0) for row in range(num_rows))
13      
14        # Initialize a 2D list to keep track of the distance for each cell
15        distance = [[0] * num_cols for _ in range(num_rows)]
16      
17        # Initialize the maximum number of moves to 0
18        max_moves = 0
19      
20        # Iterate through the queue until it is empty
21        while queue:
22            # Pop the current cell from the queue
23            i, j = queue.popleft()
24          
25            # Iterate through the possible directions
26            for delta_row, delta_col in directions:
27                # Calculate the new coordinates
28                new_row, new_col = i + delta_row, j + delta_col
29              
30                # Check if the new position is within bounds
31                # and if moving there increases the distance
32                if (0 <= new_row < num_rows and
33                    0 <= new_col < num_cols and
34                    grid[new_row][new_col] > grid[i][j] and
35                    distance[new_row][new_col] < distance[i][j] + 1):
36                  
37                    # Update the distance for the new cell
38                    distance[new_row][new_col] = distance[i][j] + 1
39                  
40                    # Update the maximum number of moves
41                    max_moves = max(max_moves, distance[new_row][new_col])
42                  
43                    # Add the new cell to the queue
44                    queue.append((new_row, new_col))
45      
46        # Return the maximum number of moves
47        return max_moves
48

Java Solution

1class Solution {
2    public int maxMoves(int[][] grid) {
3        // Define the possible directions of movement
4        int[][] directions = {{-1, 1}, {0, 1}, {1, 1}};
5        // Dimensions of the grid
6        int rows = grid.length, columns = grid[0].length;
7        // Queue to keep track of positions to process
8        Deque<int[]> queue = new ArrayDeque<>();
9        // Start by adding all positions in the first column to the queue
10        for (int row = 0; row < rows; ++row) {
11            queue.offer(new int[] {row, 0});
12        }
13        // Distance array to keep track of the maximum moves to reach each cell
14        int[][] distance = new int[rows][columns];
15        // Variable to hold the final answer - maximum number of moves
16        int maxMoves = 0;
17        // Process each position in the queue
18        while (!queue.isEmpty()) {
19            // Get the next position from the queue
20            var current = queue.poll();
21            int currentRow = current[0], currentCol = current[1];
22            // Explore all possible directions from the current position
23            for (var direction : directions) {
24                int nextRow = currentRow + direction[0], nextCol = currentCol + direction[1];
25                // Check if the next position is within bounds and has a larger value in the grid
26                // and whether we can reach it in a greater number of moves
27                if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < columns &&
28                    grid[nextRow][nextCol] > grid[currentRow][currentCol] &&
29                    distance[nextRow][nextCol] < distance[currentRow][currentCol] + 1) {
30                    // Update the distance for the next position
31                    distance[nextRow][nextCol] = distance[currentRow][currentCol] + 1;
32                    // Update the maxMoves if this move is greater
33                    maxMoves = Math.max(maxMoves, distance[nextRow][nextCol]);
34                    // Add the next position to the queue for further processing
35                    queue.offer(new int[] {nextRow, nextCol});
36                }
37            }
38        }
39        // Return the maximum number of moves
40        return maxMoves;
41    }
42}
43

C++ Solution

1#include <vector>
2#include <queue>
3#include <cstring>
4#include <algorithm>
5
6class Solution {
7public:
8    int maxMoves(std::vector<std::vector<int>>& grid) {
9        // Get the dimensions of the grid.
10        int rows = grid.size();
11        int cols = grid[0].size();
12
13        // Initialize a matrix to keep track of maximum distances travelled.
14        int dist[rows][cols];
15        std::memset(dist, 0, sizeof(dist));
16
17        // Var to hold the answer (maximum number of moves).
18        int maxMoves = 0;
19      
20        // Queue to perform Breadth-First Search (BFS).
21        std::queue<std::pair<int, int>> queue;
22      
23        // Start from all positions in the first column.
24        for (int i = 0; i < rows; ++i) {
25            queue.emplace(i, 0);
26        }
27
28        // Define movement directions to right-up, right, and right-down.
29        int directions[3][2] = {{-1, 1}, {0, 1}, {1, 1}};
30
31        // Perform BFS on the grid.
32        while (!queue.empty()) {
33            auto [row, col] = queue.front();
34            queue.pop();
35
36            // Check all possible directions from the current position.
37            for (int k = 0; k < 3; ++k) {
38                int nextRow = row + directions[k][0];
39                int nextCol = col + directions[k][1];
40
41                // Ensure the move is within the grid boundaries.
42                if (nextRow >= 0 && nextRow < rows && 
43                    nextCol >= 0 && nextCol < cols && 
44                    grid[nextRow][nextCol] > grid[row][col] && // Ensure increasing path
45                    dist[nextRow][nextCol] < dist[row][col] + 1) { // Ensure we can improve the distance.
46
47                    // Update the maximum distance of moves for the cell.
48                    dist[nextRow][nextCol] = dist[row][col] + 1;
49                  
50                    // Update the overall maximum number of moves.
51                    maxMoves = std::max(maxMoves, dist[nextRow][nextCol]);
52
53                    // Add the new cell to the queue for further exploration.
54                    queue.emplace(nextRow, nextCol);
55                }
56            }
57        }
58
59        // Return the maximum number of moves found.
60        return maxMoves;
61    }
62};
63

Typescript Solution

1type Grid = number[][];
2type Coordinates = [number, number];
3
4// Initialize a matrix to keep track of maximum distances travelled.
5let dist: number[][];
6let maxMoves: number;
7
8// Movement directions: right-up, right, and right-down.
9const directions: Coordinates[] = [[-1, 1], [0, 1], [1, 1]];
10
11// Queue to perform Breadth-First Search (BFS).
12let queue: Coordinates[] = [];
13
14function initializeGrid(rows: number, cols: number): void {
15  dist = Array.from({ length: rows }, () => Array(cols).fill(0));
16  maxMoves = 0;
17}
18
19function isWithinBounds(row: number, col: number, rows: number, cols: number): boolean {
20  return row >= 0 && row < rows && col >= 0 && col < cols;
21}
22
23function updateMaxMoves(row: number, col: number): void {
24  maxMoves = Math.max(maxMoves, dist[row][col]);
25}
26
27function addToQueue(row: number, col: number): void {
28  queue.push([row, col]);
29}
30
31function bfs(grid: Grid): void {
32  while (queue.length > 0) {
33    const [row, col] = queue.shift()!;
34
35    for (const [dr, dc] of directions) {
36      const nextRow = row + dr;
37      const nextCol = col + dc;
38
39      if (isWithinBounds(nextRow, nextCol, grid.length, grid[0].length) &&
40          grid[nextRow][nextCol] > grid[row][col] &&
41          dist[nextRow][nextCol] < dist[row][col] + 1) {
42
43        dist[nextRow][nextCol] = dist[row][col] + 1;
44        updateMaxMoves(nextRow, nextCol);
45        addToQueue(nextRow, nextCol);
46      }
47    }
48  }
49}
50
51// Function to calculate the maximum number of moves.
52function maxMoves(grid: Grid): number {
53  const rows = grid.length;
54  const cols = grid[0].length;
55
56  // Initialize the grid and BFS queue.
57  initializeGrid(rows, cols);
58
59  // Start from all positions in the first column.
60  for (let i = 0; i < rows; i++) {
61    addToQueue(i, 0);
62  }
63
64  // Perform BFS on the grid.
65  bfs(grid);
66
67  // Return the maximum number of moves found.
68  return maxMoves;
69}
70
71// Example usage:
72// const grid: Grid = [[...] ...];
73// console.log(maxMoves(grid));
74

Time and Space Complexity

Time Complexity

The time complexity of this code is primarily determined by the while loop which processes elements in the queue. We start by adding every row's first column position to the queue. Each element from the grid may be added to the queue up to m * n times, where m is the number of rows and n is the number of columns. In the worst case, we visit each cell and potentially enqueue each neighbor. Since there are at most 3 neighbors for each cell, the worst case time complexity is O(3 * m * n), which simplifies to O(m * n) since constant factors are dropped in Big O notation.

Space Complexity

The space complexity includes the space required for the queue and the dist array. The queue can potentially store all grid cells if all get enqueued simultaneously, which would require O(m * n) space. The dist array also requires O(m * n) space since it holds a value for every cell in the grid. Therefore, the total space complexity is O(m * n) + O(m * n), which simplifies to O(m * n).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫