[Dynamic Programming] Longest Path in a Matrix (Increasing) - Medium

The Longest Path in a Matrix problem is about finding the longest increasing path in a matrix of numbers. Our goal is to find the longest path where we can move to a neighboring cell that has a bigger number. We can solve this problem well using dynamic programming or depth-first search with memoization. This helps us work with bigger matrices easily.

In this article, we will look at the Longest Increasing Path in a Matrix. We will explain the problem and show different ways to solve it. We will cover dynamic programming in Java, Python, and C++. We will also discuss depth-first search with memoization for each of these languages. Also, we will talk about how to make the solution better and answer some common questions about this topic.

  • [Dynamic Programming] Finding Longest Increasing Path in a Matrix
  • Understanding the Problem Statement for Longest Path in a Matrix
  • Dynamic Programming Approach for Longest Path in a Matrix in Java
  • Dynamic Programming Approach for Longest Path in a Matrix in Python
  • Dynamic Programming Approach for Longest Path in a Matrix in C++
  • Depth First Search with Memoization for Longest Path in a Matrix in Java
  • Depth First Search with Memoization for Longest Path in a Matrix in Python
  • Depth First Search with Memoization for Longest Path in a Matrix in C++
  • Optimizing the Solution for Longest Path in a Matrix
  • Frequently Asked Questions

If you want to learn more about dynamic programming, we suggest checking out other articles. You can read about the Fibonacci number, climbing stairs, and other path problems in grids. These articles will help you understand dynamic programming better. You can find articles like Dynamic Programming: Fibonacci Number and Dynamic Programming: Unique Paths in a Grid for more insights.

Understanding the Problem Statement for Longest Path in a Matrix

We want to find the longest increasing path in a matrix. This means we look for the longest sequence of numbers that go up in value within a 2D grid. We can move in four directions: up, down, left, or right. Each cell in the matrix can only be visited one time while we are finding the path.

Problem Definition

  • Input: A 2D matrix of numbers. Each cell has a value.
  • Output: The length of the longest increasing path in the matrix.

Constraints

  • The matrix can have different sizes (m x n).
  • Each number in the matrix can be from -2^31 to 2^31 - 1.
  • If the matrix is empty, then the output should be 0.

Example

Look at this matrix:

[ [9, 9, 4],
  [6, 6, 8],
  [2, 1, 1] ]

The longest increasing path is 4 -> 6 -> 8. This path has a length of 4.

Approach

To solve this problem, we can use Depth First Search (DFS) with memoization. This helps us not to redo the work for cells we already visited. It makes the process faster. We can also use dynamic programming. In this method, we look at cell values in reverse order. This way, we find longer paths before we find shorter ones.

If you want to learn more about similar problems, you can check out articles on Dynamic Programming and Longest Increasing Subsequence or Dynamic Programming and Unique Paths in a Grid.

Dynamic Programming Approach for Longest Path in a Matrix in Java

We want to find the longest increasing path in a matrix using dynamic programming in Java. First, we create a 2D array dp to save our results. The main idea is to go through each cell in the matrix. For every cell, we will look at its neighbors (up, down, left, right) to find the longest increasing path that starts from that cell.

Here is the Java code:

public class LongestIncreasingPath {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows][cols];
        int longestPath = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                longestPath = Math.max(longestPath, dfs(matrix, dp, r, c));
            }
        }
        
        return longestPath;
    }
    
    private int dfs(int[][] matrix, int[][] dp, int r, int c) {
        if (dp[r][c] != 0) {  // Already computed
            return dp[r][c];
        }
        
        int maxLength = 1; // The length of the path starting from (r, c)

        // Directions: up, down, left, right
        int[] directions = {0, 1, 0, -1, 0};  
        for (int i = 0; i < 4; i++) {
            int newRow = r + directions[i];
            int newCol = c + directions[i + 1];

            if (newRow >= 0 && newRow < matrix.length && newCol >= 0 && newCol < matrix[0].length 
                && matrix[newRow][newCol] > matrix[r][c]) {
                maxLength = Math.max(maxLength, 1 + dfs(matrix, dp, newRow, newCol));
            }
        }
        
        dp[r][c] = maxLength; // Save the result
        return maxLength;
    }
}

Explanation:

  • Matrix Check: First, the function checks if the matrix is valid. It checks if it is not null and not empty.
  • DP Array: We make a dp array to keep the lengths of the longest paths from each cell.
  • DFS Traversal: For each cell, we start a depth-first search (DFS). The DFS checks all four directions and updates the longest path found.
  • Memoization: We store the results in the dp array. This stops us from recalculating paths for cells we have already checked.

This dynamic programming approach finds the longest increasing path in a matrix. It does this with a time complexity of O(m * n). Here, m is the number of rows and n is the number of columns in the matrix.

Dynamic Programming Approach for Longest Path in a Matrix in Python

We want to find the longest increasing path in a matrix using dynamic programming in Python. We can use a 2D list (matrix) to keep track of the lengths of the longest paths from each cell. The algorithm has these main steps:

  1. Initialization: We create a cache to store the longest path lengths for each cell. We start with -1 to show that the path length is not calculated yet.

  2. DFS with Memoization: We write a depth-first search (DFS) function. This function will look in all four directions (up, down, left, right) from each cell. If a nearby cell has a bigger value, we go to that cell and find the longest path again. We use the cache to store results. This helps us not to do the same work again.

  3. Iterate through the Matrix: We go through each cell in the matrix. We call the DFS function if we have not calculated the path length for that cell yet. We keep track of the biggest path length we find.

Here is the Python code:

def longestIncreasingPath(matrix):
    if not matrix or not matrix[0]:
        return 0
    
    rows, cols = len(matrix), len(matrix[0])
    cache = [[-1] * cols for _ in range(rows)]

    def dfs(x, y):
        if cache[x][y] != -1:
            return cache[x][y]
        
        longest = 1  # The path length counts the current cell
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and matrix[nx][ny] > matrix[x][y]:
                longest = max(longest, 1 + dfs(nx, ny))
        
        cache[x][y] = longest
        return longest

    max_length = 0
    for i in range(rows):
        for j in range(cols):
            if cache[i][j] == -1:
                max_length = max(max_length, dfs(i, j))
    
    return max_length

# Example usage
matrix = [
    [9, 9, 4],
    [6, 6, 8],
    [2, 1, 1]
]
print(longestIncreasingPath(matrix))  # Output: 4

Explanation of the Code:

  • The longestIncreasingPath function starts by getting the size of the matrix and the cache.
  • The dfs function finds the longest path from a specific cell (x, y). It looks at nearby cells and uses memoization to save results.
  • A loop goes through each cell in the matrix. We call the dfs function to find the longest increasing path starting from that cell.
  • Finally, we return the maximum path length.

This dynamic programming method helps us find the longest increasing path in a matrix. It uses memoization to avoid calculating paths that we already know.

Dynamic Programming Approach for Longest Path in a Matrix in C++

To find the longest increasing path in a matrix using dynamic programming in C++, we can use a 2D array. We will store the lengths of the longest paths from each cell. We will go through the matrix. For each cell, we will check its neighbors to find the longest path.

Code Implementation

Here is a simple C++ code for the dynamic programming approach:

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty()) return 0;

        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<int>> dp(rows, vector<int>(cols, -1));

        int longestPath = 0;

        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                longestPath = max(longestPath, dfs(matrix, dp, i, j));
            }
        }

        return longestPath;
    }

private:
    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& dp, int x, int y) {
        if (dp[x][y] != -1) return dp[x][y];

        int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int maxLength = 1;

        for (auto& dir : directions) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            if (newX >= 0 && newX < matrix.size() && newY >= 0 && newY < matrix[0].size() && 
                matrix[newX][newY] > matrix[x][y]) {
                maxLength = max(maxLength, 1 + dfs(matrix, dp, newX, newY));
            }
        }

        return dp[x][y] = maxLength;
    }
};

int main() {
    Solution solution;
    vector<vector<int>> matrix = {
        {9, 9, 4},
        {6, 6, 8},
        {2, 1, 1}
    };
    cout << "Longest Increasing Path: " << solution.longestIncreasingPath(matrix) << endl;
    return 0;
}

Explanation of the Code

  • We create a class called Solution. It has a public method longestIncreasingPath that takes a 2D vector (matrix) as input.
  • A 2D vector dp is made to store the longest path lengths for each cell. It starts with -1.
  • We look at each cell in the matrix. For each cell, we call the dfs helper function to find the longest path starting from that cell.
  • The dfs function looks in all four directions (up, down, left, right) to find increasing paths. It updates the dp array so we do not do the same work again.
  • At the end, it returns the longest path length found.

This dynamic programming way finds the longest increasing path in a matrix. It works well for medium-level problems in competitive programming.

For more content on dynamic programming techniques, you can check this article on Longest Increasing Subsequence.

Depth First Search with Memoization for Longest Path in a Matrix in Java

To find the longest increasing path in a matrix, we can use Depth First Search (DFS) with memoization. We will explore each cell in the matrix. Then we will find the longest path starting from that cell. We will also store the results of paths we already computed. This helps us avoid doing the same work again.

Implementation Steps:

  1. We create a table to store results of the longest paths we have found.
  2. For each cell in the matrix, if we have not calculated its path yet, we will do a DFS to find the longest path from there.
  3. We update our table with the length of the path we just calculated.
  4. We return the maximum length we found from all paths.

Java Code Example:

class Solution {
    private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int rows, cols;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) return 0;
        rows = matrix.length;
        cols = matrix[0].length;
        int[][] memo = new int[rows][cols];
        int maxPath = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                maxPath = Math.max(maxPath, dfs(matrix, r, c, memo));
            }
        }
        return maxPath;
    }

    private int dfs(int[][] matrix, int r, int c, int[][] memo) {
        if (memo[r][c] != 0) return memo[r][c];

        int maxLength = 1;
        for (int[] dir : directions) {
            int newRow = r + dir[0];
            int newCol = c + dir[1];
            if (isValid(newRow, newCol) && matrix[newRow][newCol] > matrix[r][c]) {
                maxLength = Math.max(maxLength, 1 + dfs(matrix, newRow, newCol, memo));
            }
        }
        memo[r][c] = maxLength;
        return maxLength;
    }

    private boolean isValid(int row, int col) {
        return row >= 0 && row < rows && col >= 0 && col < cols;
    }
}

Explanation of the Code:

  • The longestIncreasingPath function sets up the table and goes through each cell in the matrix.
  • The dfs function checks if we have already calculated the path length for the current cell. If not, it looks in all four directions (up, down, left, right) for neighbors that are higher than the current cell’s value.
  • The isValid function makes sure we do not go outside the matrix limits.
  • We store the result in the memo array. This helps us speed up future calls.

This method helps us find the longest increasing path in a matrix using DFS with memoization in Java. It avoids recomputing paths for cells that we have already checked.

Depth First Search with Memoization for Longest Path in a Matrix in Python

To find the longest increasing path in a matrix using Depth First Search (DFS) with memoization in Python, we can follow these steps:

  1. Initialize Variables:
    • We create a memoization table to save results of paths we already calculated.
    • We define directions for moving in the matrix. This includes up, down, left, and right.
  2. DFS Function:
    • We write a DFS function that explores all paths from a specific cell.
    • We check if we already computed the result for the current cell. If yes, we return that result.
    • For each valid move to an adjacent cell with a higher value, we call the DFS function again.
  3. Iterate Over All Cells:
    • We call the DFS function for each cell in the matrix. We also keep track of the longest path we find.

Here’s the Python code for this method:

def longestIncreasingPath(matrix):
    if not matrix or not matrix[0]:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    memo = [[-1] * cols for _ in range(rows)]
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    def dfs(x, y):
        if memo[x][y] != -1:
            return memo[x][y]

        max_length = 1  # at least the cell itself
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and matrix[nx][ny] > matrix[x][y]:
                max_length = max(max_length, 1 + dfs(nx, ny))

        memo[x][y] = max_length
        return max_length

    longest_path = 0
    for i in range(rows):
        for j in range(cols):
            longest_path = max(longest_path, dfs(i, j))

    return longest_path

Explanation:

  • The longestIncreasingPath function first checks if the matrix is empty. If it is not, we set up the memoization table and movement directions.
  • The inner dfs function checks if we already have the result for the current cell. Then, it looks at all four possible directions.
  • We loop through each cell, calling the DFS function and updating the longest path we find.
  • Finally, we return the length of the longest increasing path in the matrix.

This method helps us find the longest increasing path in a matrix using memoization. It makes sure we process each cell only once, which leads to a good solution. For more on dynamic programming, you can read the article on Dynamic Programming - Longest Increasing Subsequence.

Depth First Search with Memoization for Longest Path in a Matrix in C++

To find the longest increasing path in a matrix, we can use Depth First Search (DFS) with memoization in C++. We will take a recursive way to do this. We look at each cell and check its neighbors (up, down, left, right) to see if we can move to a cell with a bigger value. Memoization helps us save results for cells we already checked. This way, we can cut down on repeated calculations.

Implementation Steps:

  1. Define a Memoization Table: We will create a 2D vector to keep the length of the longest path starting from each cell.
  2. DFS Function: We need a helper function that looks at the neighboring cells and updates the memoization table.
  3. Iterate Over All Cells: For each cell in the matrix, we will call the DFS function if we did not compute it yet.

C++ Code Example:

#include <vector>
#include <algorithm>

class Solution {
public:
    int longestIncreasingPath(std::vector<std::vector<int>>& matrix) {
        if (matrix.empty()) return 0;
        
        int rows = matrix.size();
        int cols = matrix[0].size();
        std::vector<std::vector<int>> memo(rows, std::vector<int>(cols, -1));
        int longestPath = 0;
        
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                longestPath = std::max(longestPath, dfs(matrix, memo, i, j));
            }
        }
        
        return longestPath;
    }

private:
    int dfs(std::vector<std::vector<int>>& matrix, std::vector<std::vector<int>>& memo, int x, int y) {
        if (memo[x][y] != -1) return memo[x][y];

        int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int maxLength = 1;

        for (auto& dir : directions) {
            int newX = x + dir[0];
            int newY = y + dir[1];
            if (newX >= 0 && newX < matrix.size() && newY >= 0 && newY < matrix[0].size() && 
                matrix[newX][newY] > matrix[x][y]) {
                maxLength = std::max(maxLength, 1 + dfs(matrix, memo, newX, newY));
            }
        }

        memo[x][y] = maxLength;
        return maxLength;
    }
};

Explanation of the Code:

  • Input Handling: First, we check if the matrix is empty. If yes, we return 0.
  • Memoization Table: We start a memoization table called memo with -1 to show uncomputed states.
  • DFS Traversal: The dfs function looks in all the valid directions (right, down, left, up) to find longer increasing paths.
  • Memoization: Before we return the length of the path from the current cell, we save the result in the memo table to avoid unnecessary calculations.

This method works well to find the longest increasing path in the matrix while reducing the number of calculations. This makes it good for bigger matrices. For more related content, you can check out the Dynamic Programming: Longest Increasing Subsequence.

Optimizing the Solution for Longest Path in a Matrix

We can make the solution for finding the longest increasing path in a matrix better by using dynamic programming with depth-first search (DFS) and memoization. This helps us find the longest path quickly and avoids doing the same work again.

Key Steps in Optimization:

  1. Memoization: We save the results of cells we have already checked. This way, we do not have to find the longest path for those cells again.
  2. DFS Traversal: We start from each cell and check all four directions (up, down, left, right) one by one. We make sure to look only for increasing values.
  3. Boundary Conditions: We check the edges of the matrix. We only go to neighboring cells that have larger values than the current one.

Implementation in Python

def longestIncreasingPath(matrix):
    if not matrix or not matrix[0]:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    memo = [[-1] * cols for _ in range(rows)]

    def dfs(r, c):
        if memo[r][c] != -1:
            return memo[r][c]

        max_length = 1
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                max_length = max(max_length, 1 + dfs(nr, nc))

        memo[r][c] = max_length
        return max_length

    longest_path = 0
    for r in range(rows):
        for c in range(cols):
            longest_path = max(longest_path, dfs(r, c))

    return longest_path

Implementation in Java

public class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length, cols = matrix[0].length;
        int[][] memo = new int[rows][cols];
        int longestPath = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                longestPath = Math.max(longestPath, dfs(matrix, r, c, memo));
            }
        }
        return longestPath;
    }

    private int dfs(int[][] matrix, int r, int c, int[][] memo) {
        if (memo[r][c] != 0) return memo[r][c];

        int maxLength = 1;
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int[] dir : directions) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < matrix.length && nc >= 0 && nc < matrix[0].length && matrix[nr][nc] > matrix[r][c]) {
                maxLength = Math.max(maxLength, 1 + dfs(matrix, nr, nc, memo));
            }
        }
        memo[r][c] = maxLength;
        return maxLength;
    }
}

Implementation in C++

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;

        int rows = matrix.size(), cols = matrix[0].size();
        vector<vector<int>> memo(rows, vector<int>(cols, -1));
        int longestPath = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                longestPath = max(longestPath, dfs(matrix, r, c, memo));
            }
        }
        return longestPath;
    }

    int dfs(vector<vector<int>>& matrix, int r, int c, vector<vector<int>>& memo) {
        if (memo[r][c] != -1) return memo[r][c];

        int maxLength = 1;
        vector<vector<int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (auto& dir : directions) {
            int nr = r + dir[0], nc = c + dir[1];
            if (nr >= 0 && nr < matrix.size() && nc >= 0 && nc < matrix[0].size() && matrix[nr][nc] > matrix[r][c]) {
                maxLength = max(maxLength, 1 + dfs(matrix, nr, nc, memo));
            }
        }
        memo[r][c] = maxLength;
        return maxLength;
    }
};

Conclusion

This better way makes the time needed much less than a simple DFS. It helps us work with bigger matrices easily. For more tips on dynamic programming, we can look at articles like Dynamic Programming: Longest Increasing Subsequence and Dynamic Programming: Unique Paths in a Grid.

Frequently Asked Questions

What is the Longest Increasing Path in a Matrix problem?

The Longest Increasing Path in a Matrix problem is to find the longest path in a matrix. Each step must go to a nearby cell that has a higher value. We can solve this problem using dynamic programming or depth-first search. Sometimes, we use memoization to make it faster. Knowing this problem helps us understand dynamic programming better.

How do I implement the Longest Increasing Path algorithm in Java?

To implement the Longest Increasing Path algorithm in Java, we can use both dynamic programming and depth-first search (DFS) with memoization. The dynamic programming way needs a 2D array. This array stores the lengths of increasing paths. The DFS method checks each cell one by one. It saves results so we do not calculate the same thing again. This makes it much faster.

What is the time complexity of the Longest Increasing Path in a Matrix solution?

The time complexity for finding the Longest Increasing Path in a Matrix is O(M * N). Here M is the number of rows and N is the number of columns in the matrix. This complexity happens because we look at each cell one time while doing dynamic programming or DFS. This speed makes it good for bigger matrices.

Can the Longest Increasing Path algorithm be optimized further?

Yes, we can make the Longest Increasing Path algorithm even better. The basic ways are already quick, but we can use techniques like topological sorting for Directed Acyclic Graphs (DAG) if we see the matrix as a graph. Also, using data structures like priority queues can help us improve speed in some cases. This way, we can find paths faster.

What other dynamic programming problems are similar to the Longest Increasing Path?

There are many dynamic programming problems that are like the Longest Increasing Path in a Matrix. One example is the Longest Increasing Subsequence problem. This problem finds the longest subsequence in a list of numbers. Another example is the Unique Paths in a Grid. This one counts the different paths in a grid. Looking at these problems helps us learn more about dynamic programming techniques.