Thomas Ngo

Software Engineer

4 minute read

Problem Statement

problem

Brute Force [MLE]

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        res = 0
        ROWS = len(grid)
        COLS = len(grid[0])
        queue = deque()
        for row in range(ROWS):
            queue.append([row, 0, 0])

        while queue:
            row, col, moves = queue.popleft()
            for r, c in [(row - 1, col + 1), (row, col + 1), (row + 1, col + 1)]:
                if 0 <= r < ROWS and 0 <= c < COLS and grid[r][c] > grid[row][col]:
                    res = max(res, moves + 1)
                    queue.append([r, c, moves + 1])

        return res

Intuition

The core idea behind this algorithm is to traverse through a 2D grid in search of the maximum possible moves. Each move is valid if it moves to a cell with a greater value than the current cell, and only certain directions are allowed to progress in the traversal. This intuition stems from observing that each cell can only advance to the right (including diagonals) and only if the destination cell has a higher value.

Approach

  1. Initialize Variables: We set up variables to track the result (res), the dimensions of the grid (ROWS and COLS), and a 2D dp array to store the maximum moves possible from each cell.

  2. Breadth-First Search (BFS): We utilize a queue to perform BFS on each cell in the first column. Each entry in the queue represents a cell’s row, column, and move count.
    • From each cell, we attempt to move to three possible adjacent cells on the right: diagonally up-right, right, and diagonally down-right.
    • If the next cell exists within the grid bounds, has a value greater than the current cell’s value, and has not been visited, it is added to the queue with an incremented move count.

  3. Tracking Maximum Moves: Each time a valid move is made, we update res with the maximum move count observed so far, and the destination cell is marked as visited.

  4. Return Result: Once all cells have been processed, the algorithm returns res, which holds the maximum number of moves achievable.

Complexity

  • Time complexity: The algorithm processes each cell once and performs constant work per cell, resulting in a time complexity of \(O(m \cdot n)\), where \(m\) and \(n\) are the grid’s rows and columns.

  • Space complexity: Additional space is used for the queue and visited array, yielding a space complexity of \(O(m \cdot n)\).

Code

from collections import deque
from typing import List

class Solution:
    def maxMoves(self, grid: List[List[int]]) -> int:
        res = 0
        ROWS = len(grid)
        COLS = len(grid[0])
        dp = [[0]*COLS for _ in range(ROWS)]
        queue = deque()
        for row in range(ROWS):
            queue.append([row, 0, 0])

        visited = [[False] * COLS for _ in range(ROWS)]

        while queue:
            row, col, moves = queue.popleft()
            for r, c in [(row - 1, col + 1), (row, col + 1), (row + 1, col + 1)]:
                if 0 <= r < ROWS and 0 <= c < COLS and grid[r][c] > grid[row][col] and not visited[r][c]:
                    res = max(res, moves + 1)
                    queue.append([r, c, moves + 1])
                    visited[r][c] = True

        return res

Approach 2: Top-Down Dynamic Programming

class Solution:
    # The three possible directions for the next column.
    dirs = [-1, 0, 1]

    def DFS(self, row, col, grid, dp):
        M, N = len(grid), len(grid[0])

        # If we have already calculated the moves required for this cell, return the answer.
        if dp[row][col] != -1:
            return dp[row][col]

        max_moves = 0
        for dir in self.dirs:
            # Next cell after the move.
            new_row, new_col = row + dir, col + 1

            # If the next cell is valid and greater than the current cell value,
            # perform recursion to that cell with updated value of moves.
            if (
                0 <= new_row < M
                and 0 <= new_col < N
                and grid[row][col] < grid[new_row][new_col]
            ):
                max_moves = max(
                    max_moves, 1 + self.DFS(new_row, new_col, grid, dp)
                )

        dp[row][col] = max_moves
        return max_moves

    def maxMoves(self, grid):
        M, N = len(grid), len(grid[0])

        # Initialize the dp array with -1 indicating uncomputed cells.
        dp = [[-1] * N for _ in range(M)]

        max_moves = 0
        # Start DFS from each cell in the first column.
        for i in range(M):
            moves_required = self.DFS(i, 0, grid, dp)
            max_moves = max(max_moves, moves_required)

        return max_moves

Approach 3: Bottom-up Dynamic Programming

class Solution:
    def maxMoves(self, grid):
        M, N = len(grid), len(grid[0])

        # Create a 2D list for dp, initialized to 0.
        dp = [[0] * N for _ in range(M)]

        # Initialize the first column with moves as 1.
        for i in range(M):
            dp[i][0] = 1

        max_moves = 0
        for j in range(1, N):
            for i in range(M):
                # Check all three possible previous cells:
                # (i, j-1), (i-1, j-1), (i+1, j-1)
                if grid[i][j] > grid[i][j - 1] and dp[i][j - 1] > 0:
                    dp[i][j] = max(dp[i][j], dp[i][j - 1] + 1)
                if (
                    i - 1 >= 0
                    and grid[i][j] > grid[i - 1][j - 1]
                    and dp[i - 1][j - 1] > 0
                ):
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)
                if (
                    i + 1 < M
                    and grid[i][j] > grid[i + 1][j - 1]
                    and dp[i + 1][j - 1] > 0
                ):
                    dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 1)

                max_moves = max(max_moves, dp[i][j] - 1)

        return max_moves

You may also enjoy