Graph theory, Java solution, O(v^2), no DFS


  • 25
    A

    Treat matrix as a graph. Then we find the longest path in graph. In this way, it can be solved in polynomial time. I drew a picture in my blog, check my blog

    public static class Point{
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0)
            return 0;
        int n = matrix.length, m = matrix[0].length, count = m * n, ans = 0;
        while (count > 0) {
            HashSet<Point> remove = new HashSet<Point>();
            // each round, remove the peak number.
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (matrix[i][j] == Integer.MIN_VALUE)
                        continue;
                    boolean up = (i == 0 || matrix[i][j] >= matrix[i - 1][j]);
                    boolean bottom = (i == n - 1 || matrix[i][j] >= matrix[i + 1][j]);
                    boolean left = (j == 0 || matrix[i][j] >= matrix[i][j - 1]);
                    boolean right = (j == m - 1 || matrix[i][j] >= matrix[i][j + 1]);
                    if (up && bottom && left && right)
                        remove.add(new Point(i, j));
                }
            }
            for (Point point : remove) {
                matrix[point.x][point.y] = Integer.MIN_VALUE;
                count--;
            }
            ans++;
        }
        return ans;
    }
    

  • 0
    K

    I think HashSet is not necessary. ArrayList is enough.


  • 0

    Very clever solution, but I wonder how do you estimate the complexity?


  • 3

    I think DFS still works in O(V) with memorization because every node will be visited only once. Correct me if I am wrong.


  • 0
    A

    I think you are right. Once the graph is built, it can be solved in O(V) time.


  • 0
    L

    I think HashSet is used to avoid duplicated points, but without override the hashCode and equal function, every Point is unique due to java will use reference/memory address to calculate hash code.


  • 2

    So brilliant!

    I think the core idea is treat the graph as topology sorted, and each time we delete from the end (which means we will delete all nodes within the same level), and increment count. The reason behind is: we can choose one (and only one) node from current level for next step.

    So in this way we get the longest path from end to start.

    Shou Xia Wo De Xi Gai.


  • 0
    A

    @left.peter Where do duplicated points come from? I think list is enough, hashset is overkill.


  • 5
    A

    @YuTingLiu But in the worst case, (i.e. the matrix is a single linked chain), you have to scan the whole matrix for m*n times (because each time you only remove 1 point), and each time you scan the whole matrix (at least one read operation from every cell matrix[i][j]). So it might not be really faster than DFS. In total, you would read (m*n)^(m*n) cells, which basically means O((m*n)^(m*n)). Am I right?


  • 1
    R

    I don't think there's any difference between this and Dfs in terms of time complexity.
    Dfs + Memoization already yields the best possible time complexity which is O(N)


  • 0
    R

    Great solution!
    I think it also works backward. i.e. every time delete node without any in-degree rather than out-degree. Please correct me if I'm wrong.


  • 1
    J

    Actually, this solution is topological sort


  • 0
    S

    brilliant idea!


  • 0
    C

    Nice Idea. But this top down solution could be O(nm^2) if all nodes forms a line.
    DFS is a bottom up solution which guarantee O(nm)


  • 7

    This is essentially BFS and you are trimming leafs level by level. Instead of searching the whole matrix every time you can use queue to speed it up. This is my BFS implementation:

        private final int[][] dirs = {{1, 0}, {-1, 0},{0, 1}, {0, -1}};
        private boolean ispeak(int[][] matrix, boolean[][] marked, int i, int j) {
            if (i > 0 && !marked[i-1][j] && matrix[i-1][j] > matrix[i][j]) return false;
            if (i < matrix.length-1 && !marked[i+1][j] && matrix[i+1][j] > matrix[i][j]) return false;
            if (j > 0 && !marked[i][j-1] && matrix[i][j-1] > matrix[i][j]) return false;
            if (j < matrix[0].length-1 && !marked[i][j+1] && matrix[i][j+1] > matrix[i][j]) return false;
            return true;
        }
        public int longestIncreasingPath(int[][] matrix) {
            if (matrix.length == 0 || matrix[0].length == 0) return 0;
            int len = 0;
            LinkedList<int[]> queue = new LinkedList<>();
            boolean[][] marked = new boolean[matrix.length][matrix[0].length];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (ispeak(matrix, marked, i, j)) queue.add(new int[]{i, j});
                }
            }
            while (!queue.isEmpty()) {
                len++;
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int[] p = queue.poll();
                    marked[p[0]][p[1]] = true;
                    for (int j = 0; j < 4; j++) {
                        int r = p[0]+dirs[j][0], c = p[1]+dirs[j][1];
                        if (r >= 0 && r < matrix.length && c >= 0 && c < matrix[0].length && !marked[r][c] && ispeak(matrix, marked, r, c)) {
                            if (matrix[r][c] != matrix[p[0]][p[1]]) queue.add(new int[]{r, c});
                        }
                    }
                }
            }
            return len;
        }
    

  • 0
    Y

    @dreamchase another simpler optimization would be through priority queue, it will give us a natural topological order, the time complexity gets lowered to O(mnlog(mn))

    public class Solution {
        public final int[] dir = {0,1,0,-1,0};
        public class Point{
            public int i, j, val;
            Point(int i, int j, int val){
                this.i = i;
                this.j = j;
                this.val = val;
            }
        }
        public int longestIncreasingPath(int[][] matrix){
            if(matrix==null || matrix.length<1) return 0;
            int row = matrix.length, col = matrix[0].length, max = 1;
            int[][] mem = new int[row][col];
            PriorityQueue<Point> pq = new PriorityQueue<>(new Comparator<Point>() {
                public int compare(Point o1, Point o2) {
                    return o2.val-o1.val;
                }
            });
            for(int i=0;i<row;i++)
                for(int j=0;j<col;j++)
                    pq.offer(new Point(i,j,matrix[i][j]));//O(m*n)
            while(!pq.isEmpty()){//O(m*n*log(m*n))
                Point cur = pq.poll();
                mem[cur.i][cur.j] = 1;
                for(int k=0;k<dir.length-1;k++){
                    int r = cur.i + dir[k], c = cur.j + dir[k+1];
                    if(r<0 || c<0 || r>=row || c>=col || cur.val>=matrix[r][c]) continue;
                    mem[cur.i][cur.j] = Math.max(mem[cur.i][cur.j], mem[r][c] + 1);
                }
                max = Math.max(mem[cur.i][cur.j], max);
            }
            return max;
        }
    }
    

  • 0

    @yixuanwang.start the running time of BFS is only O(mn)


  • 0
    Y

    @dreamchase you are right, I just thought pq is more intuitive, it's not as efficient as yours, but it beats OP's topological sort


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.