Longest Increasing Path in a Matrix

Share

Given an m x n integers matrix, return the length of the longest increasing path. From each cell, you can move in 4 directions to adjacent cells with strictly greater values.

Example 1
Input: [[9,9,4],[6,6,8],[2,1,1]] → Output: 4 (1→6→8→9)
Example 2
Input: [[3,4,5],[3,2,6],[2,2,1]] → Output: 4

Solution Approach

DFS with memoization. memo[i][j] = longest increasing path starting at (i,j). For each cell, try 4 directions to cells with greater value.

  • memo[i][j] stores the answer for each cell.
  • dfs(i,j): if memo[i][j]>0 return it.
  • Try 4 directions: if neighbor has greater value, recurse and take max.
  • memo[i][j] = 1 + max over valid neighbors.
Java
class Solution {
    int[][] memo;
    int m, n;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

    public int longestIncreasingPath(int[][] matrix) {
        m=matrix.length; n=matrix[0].length; memo=new int[m][n]; int max=0;
        for (int i=0;i<m;i++) for (int j=0;j<n;j++) max=Math.max(max,dfs(matrix,i,j));
        return max;
    }
    private int dfs(int[][] mat, int r, int c) {
        if (memo[r][c]>0) return memo[r][c];
        memo[r][c]=1;
        for (int[] d:dirs) {
            int nr=r+d[0], nc=c+d[1];
            if (nr>=0&&nr<m&&nc>=0&&nc<n&&mat[nr][nc]>mat[r][c])
                memo[r][c]=Math.max(memo[r][c],1+dfs(mat,nr,nc));
        }
        return memo[r][c];
    }
}
  • Time Complexity: O(M*N)
  • Space Complexity: O(M*N)