Longest Increasing Path in Matrix

107.Longest Increasing Path in a Matrix

Matrix

Depth-First Search

Dynamic Programming

Problem Statement:

Given an m x n integer matrix, return the length of the longest increasing path in the matrix. You can move in four directions: up, down, left, and right. You may not move diagonally or revisit the same cell in a single path.

Algorithm:

1. Initialize a dp table to store the longest increasing path starting from each cell.
2. Use a depth-first search (DFS) function with memoization to calculate the path length for each cell:
   • If the current cell has been computed before, return its value from dp.
   • Otherwise, calculate the maximum path length by moving to all valid adjacent cells with greater values.
3. Iterate through all cells in the matrix, calling the DFS function, and track the maximum path length.
4. Return the maximum value found in dp.

Complexity:

Time: O(m * n), where m is the number of rows and n is the number of columns | Space: O(m * n).

Java Implementation:

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

        int n = matrix.length;
        int m = matrix[0].length;
        int max = -1;

        int[][] dp = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                longest(matrix, dp, i, j, n, m, Integer.MIN_VALUE);
                max = Math.max(dp[i][j], max);
            }
        }

        return max;
    }

    int longest(int[][] matrix, int[][] dp, int x, int y, int n, int m, int prev) {
        if (x < 0 || y < 0 || x >= n || y >= m || matrix[x][y] <= prev) return 0;

        if (dp[x][y] > 0) return dp[x][y];

        int max = 1;

        int[] dx = {0, -1, 0, 1};
        int[] dy = {1, 0, -1, 0};

        for (int i = 0; i < dx.length; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];
            max = Math.max(max, 1 + longest(matrix, dp, newX, newY, n, m, matrix[x][y]));
        }

        dp[x][y] = max;

        return max;
    }
}
                

Python Implementation:

def longestIncreasingPath(matrix):
    if not matrix:
        return 0

    n, m = len(matrix), len(matrix[0])
    dp = [[0] * m for _ in range(n)]

    def dfs(x, y, prev):
        if x < 0 or y < 0 or x >= n or y >= m or matrix[x][y] <= prev:
            return 0
        if dp[x][y] > 0:
            return dp[x][y]

        max_len = 1
        directions = [(0, 1), (-1, 0), (0, -1), (1, 0)]
        for dx, dy in directions:
            max_len = max(max_len, 1 + dfs(x + dx, y + dy, matrix[x][y]))

        dp[x][y] = max_len
        return max_len

    return max(dfs(i, j, float('-inf')) for i in range(n) for j in range(m))
                

C++ Implementation:

#include 
#include 
using namespace std;

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

        int n = matrix.size(), m = matrix[0].size(), maxLen = 0;
        vector> dp(n, vector(m, 0));

        auto dfs = [&](auto&& self, int x, int y, int prev) -> int {
            if (x < 0 || y < 0 || x >= n || y >= m || matrix[x][y] <= prev)
                return 0;
            if (dp[x][y] > 0)
                return dp[x][y];

            int max_len = 1;
            vector> directions = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
            for (auto [dx, dy] : directions) {
                max_len = max(max_len, 1 + self(self, x + dx, y + dy, matrix[x][y]));
            }

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

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                maxLen = max(maxLen, dfs(dfs, i, j, INT_MIN));
            }
        }

        return maxLen;
    }
};