Longest Increasing Path in a Matrix

This page explains Java solution to problem Longest Increasing Path in a Matrix using Depth First Search algorithm.

Problem Statement

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Input:
nums = [
       [9,9,4],
       [6,6,8],
       [2,1,1]
]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9]

Input:
nums = [
       [3,4,5],
       [3,2,6],
       [2,2,1]
]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]

Solution

package com.vc.hard;

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

        int[][] cache = new int[n][m];
        int max = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                max = Math.max(max, 1 + solve(matrix, cache, i, j));
            }
        }
        return max;
    }

    private int[][] dirs = {{1, 0},{-1, 0},{0, 1},{0, -1}};
    private int solve(int[][] matrix, int[][] cache, int row, int col) {
        if(cache[row][col] > 0) return cache[row][col];
        int max = 0;
        for(int[] dir: dirs) {
            int xNew = row + dir[0];
            int yNew = col + dir[1];
            if(xNew >= 0 && xNew < matrix.length && yNew >= 0 && yNew < matrix[0].length
                    && matrix[row][col] > matrix[xNew][yNew]) {
                max = Math.max(max, 1 + solve(matrix, cache, xNew, yNew));
            }
        }
        cache[row][col] = max;
        return max;
    }
}

Time Complexity

O(M * N * K) Where
M is total number of rows in an input matrix
N is total number of cols in an input matrix
K is length of longest increasing path in an input matrix

Space Complexity

O(M * N)
M is total number of rows in an input matrix
N is total number of cols in an input matrix