Longest Increasing path in a matrix

XXX. Longest Increasing Path in a Matrix

Dynamic Programming

Depth-First Search

Problem Statement:

Given an integer matrix, find the length of the longest increasing path in the matrix. From each cell, you can move in four directions (left, right, up, or down) to a cell with a greater value.

Algorithm:

This problem uses dynamic programming with memoization and depth-first search (DFS):

1. Define a cache matrix to store the longest path starting from each cell. Initialize all values to 0, meaning they are not yet computed.
2. Perform DFS from each cell in the matrix. For each cell:
   • Check all four possible directions (up, down, left, right).
   • If the neighboring cell value is greater, recursively compute the path length starting from that cell.
3. Use the cache matrix to store previously computed results to avoid redundant calculations.
4. Track the maximum path length across all cells in the matrix.

Complexity:

Time Complexity: O(m * n), where m and n are the dimensions of the matrix. Each cell is visited once and its result is cached.
Space Complexity: O(m * n), for the cache matrix and the recursion stack.

Java Implementation:

public class Solution {

    public static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] cache = new int[m][n]; // Cache to store the longest path from each cell
        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); // Compute longest path from (i, j)
                max = Math.max(max, len); // Update the global maximum
            }
        }

        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]; // Return cached result if available

        int max = 1; // Minimum path length is 1 (the cell itself)
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];

            // Check boundaries and ensure the move increases the value
            if (x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue;

            int len = 1 + dfs(matrix, x, y, m, n, cache); // Recursive DFS for the next cell
            max = Math.max(max, len); // Update the maximum path length
        }

        cache[i][j] = max; // Cache the result for this cell
        return max;
    }
}