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).

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]
Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]
Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Solution

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

        int now = 0;
        int cont[] = new int[m * n * 4];
        int next[] = new int[m * n * 4];
        int head[] = new int[m * n];
        Arrays.fill(head, -1);
        int indegree[] = new int[m * n];

        int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int from = j * m + i;
                for(int[] dir: dirs) {
                    if(i + dir[0] >= 0 && i + dir[0] < m && j + dir[1] >= 0 && j + dir[1] < n
                       && matrix[i+dir[0]][j+dir[1]] > matrix[i][j]) {
                        int to = (j+dir[1]) * m + i + dir[0];

                        cont[now] = to;
                        next[now] = head[from];
                        head[from] = now++;
                        indegree[to]++;
                    }
                }
            }
        }

        int ans = 0;
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i = 0; i < m * n; i++) {
            if(indegree[i] == 0) { // once contained, that would be >= 1
                queue.offer(i);
            }
        }

        while(!queue.isEmpty()) {
            ans++;
            Queue<Integer> newQ = new LinkedList<Integer>();
            while(!queue.isEmpty()) {
                int from = queue.poll();
                int tar = head[from];
                while(tar != -1) {
                    if(--indegree[cont[tar]] == 0) {
                        newQ.offer(cont[tar]);
                    }
                    tar = next[tar];
                }
            }
            queue = newQ;
        }

        return ans;
    }
}