Fork me on GitHub

Longest Increasing Path in a Matrix

Posted on

Description

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public int height;
    public int width;
    public int longestIncreasingPath(int[][] matrix) {
        height = matrix.length;
        if (height == 0) return 0;
        width = matrix[0].length;
        
        
        //Using restore[i][j], means the length of increasing count of coordinate (i, j)
        int[][] restore = new int[height][width];
        
        //Mark each item as clean(-1)
        for(int i = 0; i < height; i++)
            for(int j = 0; j < width; j++)
                restore[i][j] = -1;
        
        int retLength = -1;
        
        for (int i = 0; i < height; i++)
            for(int j = 0; j < width; j++)
                retLength = Math.max(retLength, startFromIJ(matrix, i, j, restore));  
        
        return retLength;
    }
    
    public int startFromIJ(int[][] matrix, int i, int j, int[][] restore) {
        if (restore[i][j] != -1) return restore[i][j];
        // if (i < 0 || i >= height || j < 0 || j >= width) return 0;
        int[][] directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        int ret = 1;
        for (int index = 0; index <= 3; index += 1) {
            int newRow = i + directions[index][0];
            int newCol = j + directions[index][1];
            if (newRow >= 0 && newRow < height && newCol >= 0 && newCol < width && matrix[newRow][newCol] > matrix[i][j]){
                ret = Math.max(ret, startFromIJ(matrix, newRow, newCol, restore) + 1);
            }
        }
        restore[i][j] = ret;
        return ret;
    }
}