Longest Increasing Path in a Matrix

Problem Statement

The task is to determine the length of the longest increasing path in a 2D matrix consisting of integers. The matrix dimensions are specified as m x n. You can move vertically or horizontally to neighboring cells to form a path, but not diagonally and not beyond the matrix boundaries. The challenge is to identify the path where each step increases in value, and to report the maximum length of such a path found within the matrix.

Examples

Example 1

Input:

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

Output:

4

Explanation:

The longest increasing path is `[1, 2, 6, 9]`.

Example 2

Input:

matrix = [[3,4,5],[3,2,6],[2,2,1]]

Output:

4

Explanation:

The longest increasing path is `[3, 4, 5, 6]`. Moving diagonally is not allowed.

Example 3

Input:

matrix = [[1]]

Output:

1

Constraints

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 200
• 0 <= matrix[i][j] <= 231 - 1

Approach and Intuition

To tackle this problem and find the longest increasing path, consider the following approach based on dynamic programming and depth-first search (DFS):

1. Initialization: Start by creating a memoization table (a 2D list) of the same size as the matrix, initialized to None or zero, to store the length of the longest increasing path starting from each cell.

2. Depth-First Search (DFS): Implement a recursive DFS function. This function will:

   • Check the boundary conditions and whether the movement is to a higher value.
   • Utilize the memoization table to avoid recalculating paths from cells already visited.
   • Explore all four possible directions (left, right, up, down) from the current cell, ensuring you only move to cells with higher values.

3. Recursive Exploration: For every cell, use the DFS function to explore the possible paths. Compare values with adjacent cells and move to the cell if it has a higher value, recursively calculating the path length.

4. Memoization: Store the results of each DFS call in the memoization table, which represents the longest path beginning from that cell. This avoids redundant calculations and dramatically improves efficiency.

5. Calculate the Maximum Path: After applying the DFS to each cell and storing the longest paths in the memoization table, the final step is to find the maximum value in this table, which represents the length of the longest increasing path in the matrix.

Example Analyses from Provided Cases:

• Example 1: The path [1, 2, 6, 9] demonstrates increasing values with each step to adjacent cells, yielding a path length of 4.
• Example 2: Similarly, the path [3, 4, 5, 6] is formed by moving through cells with strictly increasing values.
• Example 3: With a single-cell matrix, the longest path is trivially the cell itself with a path length of 1.

This approach ensures that all possibilities are explored, and the use of memoization ensures efficiency, making the algorithm feasible even for large matrices within the provided constraints.

Solutions

public class Solution {
    private static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int rows, cols;
    public int findLongestPath(int[][] matrixGrid) {
        int rows = matrixGrid.length;
        if (rows == 0) return 0;
        int cols = matrixGrid[0].length;
        int[][] paddedMatrix = new int[rows + 2][cols + 2];
        for (int i = 0; i < rows; ++i)
            System.arraycopy(matrixGrid[i], 0, paddedMatrix[i + 1], 1, cols);

        int[][] outdegrees = new int[rows + 2][cols + 2];
        for (int i = 1; i <= rows; ++i)
            for (int j = 1; j <= cols; ++j)
                for (int[] d : directions)
                    if (paddedMatrix[i][j] < paddedMatrix[i + d[0]][j + d[1]])
                        outdegrees[i][j]++;

        cols += 2;
        rows += 2;
        ArrayList<int[]> initialLeaves = new ArrayList<>();
        for (int i = 1; i < rows - 1; ++i)
            for (int j = 1; j < cols - 1; ++j)
                if (outdegrees[i][j] == 0) initialLeaves.add(new int[]{i, j});

        int longestPath = 0;
        while (!initialLeaves.isEmpty()) {
            longestPath++;
            ArrayList<int[]> newLeaves = new ArrayList<>();
            for (int[] leaf : initialLeaves) {
                for (int[] d : directions) {
                    int x = leaf[0] + d[0], y = leaf[1] + d[1];
                    if (paddedMatrix[leaf[0]][leaf[1]] > paddedMatrix[x][y])
                        if (--outdegrees[x][y] == 0)
                            newLeaves.add(new int[]{x, y});
                }
            }
            initialLeaves = newLeaves;
        }
        return longestPath;
    }
}