HARD
DATA STRUCTURES AND ALGORITHMS

How to Solve Longest Increasing Path in a Matrix

Written By

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

• Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. This is because we traverse each cell in the matrix exactly once during the DFS process.
• Space Complexity: O(m * n), this is because we use a memoization table of the same size to store the previously calculated results. Additionally, the recursion stack during the DFS process can go up to the maximum depth of the matrix, which is O(m * n) in the worst case scenario. Therefore, the overall space complexity is dominated by the memoization table and the recursion stack.