How to Solve Longest Increasing Path in a Matrix
Longest Increasing Path in a Matrix Introduction
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
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
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: 41def longestIncreasingPath(matrix):
2 # Check if input matrix is empty
3 if not matrix:
4 return 0
5
6 rows, cols = len(matrix), len(matrix[0]) # calculate number of rows and columns
7 memo = [[0] * cols for _ in range(rows)] # create memo table
8 maxPath = 0
9
10 def dfs(row, col):
11 # If the result for this cell has already been calculated, return it
12 if memo[row][col] != 0:
13 return memo[row][col]
14
15 directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] # Possible directions: right, left, down, up
16 maxLen = 1
17
18 for dx, dy in directions:
19 newRow, newCol = row + dx, col + dy
20 # Check if the new cell is within the matrix boundaries and has a higher value
21 if 0 <= newRow < rows and 0 <= newCol < cols and matrix[newRow][newCol] > matrix[row][col]:
22 maxLen = max(maxLen, 1 + dfs(newRow, newCol)) # Recursively explore the new cell
23
24 memo[row][col] = maxLen # Cache the result for this cell
25 return maxLen
26
27 for row in range(rows):
28 for col in range(cols):
29 maxPath = max(maxPath, dfs(row, col)) # Explore each cell and update the maximum path length
30
31 return maxPath
32
33# Driver code
34matrix1 = [
35 [9, 9, 4],
36 [6, 6, 8],
37 [2, 1, 1]
38]
39print(longestIncreasingPath(matrix1)) # Output: 4
40
41matrix2 = [
42 [3, 4, 5],
43 [3, 2, 6],
44 [2, 2, 1]
45]
46print(longestIncreasingPath(matrix2)) # Output: 4Time/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.
Watch These Related Mock Interviews
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
