Solution For Longest Increasing Path In A Matrix

The Longest Increasing Path In A Matrix problem on LeetCode is a dynamic programming problem that asks you to find the length of the longest increasing path in a given matrix. An increasing path is a path in which each cell is greater than the cell before it. The path can start from any cell in the matrix and can move in any of the four directions (up, down, left, or right).

Here is a detailed solution for this problem with step-by-step explanation.

Step 1: Understand the problem statement
The problem statement is asking us to find the length of the longest increasing path in a given matrix. We can move in any of the four directions from a cell and the path can start from any cell in the matrix.

Step 2: Approach
We can solve this problem using dynamic programming. We will start by creating a DP matrix of the same size as the input matrix to store the longest path length from each cell. We will then iterate through each cell in the matrix and use a recursive DFS approach to find the longest increasing path from that cell.

Step 3: Pseudo code
The pseudo code for the solution is as follows:

Initialize a DP matrix of the same size as the input matrix to store the longest path length from each cell
Define a recursive DFS function that takes the matrix, the current cell coordinates, and the DP matrix as input
If the DP matrix contains a calculated value for the current cell, return that value
Set the longest path length from the current cell to 1
For each of the four neighboring cells, if the neighbor is greater than the current cell, recursively call the DFS function on that neighbor and add 1 to the returned value
Set the longest path length from the current cell to the maximum path length from its neighbors
Update the DP matrix with the calculated longest path length for the current cell
Return the longest path length from the current cell

Loop through each cell in the matrix and call the recursive DFS function to find the longest increasing path from that cell
Return the maximum path length found

Step 4: Code implementation

In the code below, we have created a class Solution with a single function longestIncreasingPath which takes a matrix as input and returns the length of the longest increasing path in the matrix.

class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
if not matrix:
return 0

    # Initialize a DP matrix of the same size as the input matrix to store the longest path length from each cell
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]

    # Define a recursive DFS function that takes the matrix, the current cell coordinates, and the DP matrix as input
    def dfs(x, y):
        # If the DP matrix contains a calculated value for the current cell, return that value
        if dp[x][y]:
            return dp[x][y]

        # Set the longest path length from the current cell to 1
        path = 1

        # For each of the four neighboring cells, if the neighbor is greater than the current cell,
        # recursively call the DFS function on that neighbor and add 1 to the returned value
        for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny] > matrix[x][y]:
                path = max(path, dfs(nx, ny) + 1)

        # Set the longest path length from the current cell to the maximum path length from its neighbors
        dp[x][y] = path

        # Return the longest path length from the current cell
        return path

    # Loop through each cell in the matrix and call the recursive DFS function to find the longest increasing path from that cell
    ans = 0
    for i in range(m):
        for j in range(n):
            ans = max(ans, dfs(i, j))

    # Return the maximum path length found
    return ans

Step 5: Test the solution
We can test our solution with some sample test cases:

assert(Solution().longestIncreasingPath([
[9,9,4],
[6,6,8],
[2,1,1] ]) == 4)

assert(Solution().longestIncreasingPath([
[3,4,5],
[3,2,6],
[2,2,1] ]) == 4)

The above test cases pass successfully.

Step 6: Time complexity analysis
We are iterating through each cell in the matrix once and for each cell, we perform a recursive DFS operation on its neighbors. The max length of the path is limited by the number of cells in the matrix. So, the worst-case time complexity of the algorithm will be O(n^2 * 4^n), where n is the number of cells in the matrix. However, in practice, the time complexity of this algorithm is much lower due to the memoization technique used to avoid duplicate computations.

Step 7: Space complexity analysis
We are using a DP matrix of the same size as the input matrix to store the longest path length from each cell. So, the space complexity of the algorithm is O(n^2), where n is the number of cells in the matrix.

Step by Step Implementation For Longest Increasing Path In A Matrix

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        //cache[i][j] means the longest increasing path 
        //that starts from matrix[i][j]
        int[][] cache = new int[m][n];
        int max = 1;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int len = dfs(matrix, i, j, m, n, cache);
                max = Math.max(max, len);
            }
        }
        return max;
    }
    
    private int dfs(int[][] matrix, int i, int j, int m, int n, int[][] cache) {
        if(cache[i][j] != 0) return cache[i][j];
        int max = 1;
        //check up
        if(i > 0 && matrix[i][j] < matrix[i - 1][j]) {
            max = Math.max(max, 1 + dfs(matrix, i - 1, j, m, n, cache));
        }
        //check down
        if(i < m - 1 && matrix[i][j] < matrix[i + 1][j]) {
            max = Math.max(max, 1 + dfs(matrix, i + 1, j, m, n, cache));
        }
        //check left
        if(j > 0 && matrix[i][j] < matrix[i][j - 1]) {
            max = Math.max(max, 1 + dfs(matrix, i, j - 1, m, n, cache));
        }
        //check right
        if(j < n - 1 && matrix[i][j] < matrix[i][j + 1]) {
            max = Math.max(max, 1 + dfs(matrix, i, j + 1, m, n, cache));
        }
        cache[i][j] = max;
        return max;
    }
}

This problem can be solved using a dynamic programming approach. We can create a 2D array, dp, where dp[i][j] represents the longest increasing path from the cell (i, j). We can then fill in this array using a bottom-up approach.

First, we initialize all values in dp to 1. This is because the longest increasing path from a cell can always be at least 1 (the cell itself).

Then, we iterate through the matrix, starting from the bottom right corner. For each cell, we check all of its neighbors (up, down, left, right). If the neighbor has a value greater than the cell's value, then we know there is an increasing path from the cell to the neighbor.

We can then update the cell's value in dp to be the longest increasing path from the cell to the neighbor, plus 1.

After we have iterated through the entire matrix, the cell with the largest value in dp will be the cell with the longest increasing path.

var longestIncreasingPath = function(matrix) {
    
    //if the matrix is empty, return 0
    if (matrix.length === 0) {
        return 0;
    }
    
    //store the maximum length of an increasing path
    let max = 0;
    
    //create a 2D array to store the length of the longest increasing path
    //starting from each cell in the matrix
    let dp = new Array(matrix.length);
    for (let i = 0; i < dp.length; i++) {
        dp[i] = new Array(matrix[0].length).fill(0);
    }
    
    //traverse through the matrix
    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            
            //find the longest increasing path starting from matrix[i][j]
            let len = findPath(matrix, i, j, dp);
            
            //update the maximum length
            max = Math.max(max, len);
        }
    }
    
    return max;
};

//find the longest increasing path starting from matrix[i][j]
//and return the length of the path
var findPath = function(matrix, i, j, dp) {
    
    //if the cell has been visited, return the stored value
    if (dp[i][j] !== 0) {
        return dp[i][j];
    }
    
    //store the length of the longest increasing path
    let max = 1;
    
    //check if the cell to the left is valid and smaller
    if (i > 0 && matrix[i-1][j] < matrix[i][j]) {
        max = Math.max(max, 1 + findPath(matrix, i-1, j, dp));
    }
    
    //check if the cell to the right is valid and smaller
    if (i < matrix.length-1 && matrix[i+1][j] < matrix[i][j]) {
        max = Math.max(max, 1 + findPath(matrix, i+1, j, dp));
    }
    
    //check if the cell to the top is valid and smaller
    if (j > 0 && matrix[i][j-1] < matrix[i][j]) {
        max = Math.max(max, 1 + findPath(matrix, i, j-1, dp));
    }
    
    //check if the cell to the bottom is valid and smaller
    if (j < matrix[0].length-1 && matrix[i][j+1] < matrix[i][j]) {
        max = Math.max(max, 1 + findPath(matrix, i, j+1, dp));
    }
    
    //store the length of the longest path starting from matrix[i][j]
    dp[i][j] = max;
    
    return max;
};

int longestIncreasingPath(vector>& matrix) {
        if (matrix.empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector> dp(m, vector(n, 0));
        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                res = max(res, dfs(matrix, dp, i, j));
            }
        }
        return res;
    }
    
    int dfs(vector>& matrix, vector>& dp, int i, int j) {
        if (dp[i][j]) return dp[i][j];
        vector> dirs{{0,-1}, {0,1}, {-1,0}, {1,0}};
        int m = matrix.size(), n = matrix[0].size();
        int res = 1;
        for (auto& dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue;
            res = max(res, 1 + dfs(matrix, dp, x, y));
        }
        dp[i][j] = res;
        return res;
    }

public class Solution {
    public int LongestIncreasingPath(int[][] matrix) {
        if(matrix.Length == 0) return 0;
        int[][] dirs = new int[][] {{0,1},{0,-1},{1,0},{-1,0}};
        int m = matrix.Length, n = matrix[0].Length;
        int[][] memo = new int[m][];
        for(int i = 0; i < m; i++)
            memo[i] = new int[n];
        
        int ans = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                ans = Math.Max(ans, DFS(matrix, i, j, dirs, memo));
            }
        }
        return ans;
    }
    
    private int DFS(int[][] matrix, int i, int j, int[][] dirs, int[][] memo){
        if(memo[i][j] != 0) return memo[i][j];
        memo[i][j] = 1;
        foreach(int[] dir in dirs){
            int x = i + dir[0], y = j + dir[1];
            if(x < 0 || y < 0 || x >= matrix.Length || y >= matrix[0].Length || matrix[x][y] <= matrix[i][j])
                continue;
            memo[i][j] = Math.Max(memo[i][j], 1 + DFS(matrix, x, y, dirs, memo));
        }
        return memo[i][j];
    }
}