Longest Increasing Path in a Matrix (Interview Solution)

How to Solve Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix Introduction

The Longest Increasing Path in a Matrix problem asks us to as the name would suggest, return the length of the longest increasing path given an m x n matrix. The limitations are that we can only move up, down, left, or right not diagonally, and going outside of bounds (wrap-around) is also not permitted. The challenge in this problem is using memoization to store the results of the subproblems (the lengths) to avoid redundant calculations.

Longest Increasing Path in a Matrix Problem

Given an m x n integers matrix, return the length of the longest increasing path in the matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Example Inputs and Outputs

Example 1

Input: Matrix = [ [9, 9, 4], [6, 6, 8], [2, 1, 1] ]

Output: 4

Example 2

Input: Matrix = [ [3, 4, 5], [3, 2, 6], [2, 2, 1] ]

Output: 4

Longest Increasing Path in a Matrix Solutions

To tackle this problem, we can use a dynamic programming approach with memoization. To find the longest increasing path, we start by initializing a table called "memo" to keep track of the lengths of the longest increasing paths starting from each cell in the matrix. We then iterate over each cell in the matrix and perform a depth-first search (DFS).

During the DFS, we explore the neighboring cells and recursively calculate the length of the increasing path if the neighboring cell has a greater value. We store the lengths of these paths in the memo table to avoid redundant calculations. This way, when we encounter a cell that we have visited before, we can simply retrieve the precalculated length from the memo table instead of recomputing it.

After performing the DFS for all cells, we find the maximum length of the increasing path in the memo table. This maximum length represents the longest increasing path in the matrix. By using memoization and avoiding redundant calculations, this DP approach solves the problem more efficiently with a better runtime than a naive approach that explores all possible paths.

def longestIncreasingPath(matrix):
    # Check if input matrix is empty
    if not matrix:
        return 0

rows, cols = len(matrix), len(matrix[0]) # calculate number of rows and columns
    memo = [[0] * cols for _ in range(rows)] # create memo table
    maxPath = 0

def dfs(row, col):
        # If the result for this cell has already been calculated, return it
        if memo[row][col] != 0:
            return memo[row][col]

directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # Possible directions: right, left, down, up
        maxLen = 1

for dx, dy in directions:
            newRow, newCol = row + dx, col + dy
            # Check if the new cell is within the matrix boundaries and has a higher value
            if 0 <= newRow < rows and 0 <= newCol < cols and matrix[newRow][newCol] > matrix[row][col]:
                maxLen = max(maxLen, 1 + dfs(newRow, newCol))  # Recursively explore the new cell

memo[row][col] = maxLen  # Cache the result for this cell
        return maxLen

for row in range(rows):
        for col in range(cols):
            maxPath = max(maxPath, dfs(row, col))  # Explore each cell and update the maximum path length

return maxPath

# Driver code
matrix1 = [\
    [9, 9, 4],\
    [6, 6, 8],\
    [2, 1, 1]\\
]
print(longestIncreasingPath(matrix1))  # Output: 4

matrix2 = [\
    [3, 4, 5],\
    [3, 2, 6],\
    [2, 2, 1]\\
]
print(longestIncreasingPath(matrix2))  # Output: 4

Time/Space Complexity Analysis