0329. Longest Increasing Path in a Matrix

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

Description

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

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

Example 1:

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

Example 2:

**Input:** matrix = [[3,4,5],[3,2,6],[2,2,1]]
**Output:** 4
**Explanation:** The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Example 3:

**Input:** matrix = [[1]]
**Output:** 1

Constraints:

• m == matrix.length

• n == matrix[i].length

• 1 <= m, n <= 200

• 0 <= matrix[i][j] <= 231 - 1

ac: DFS + Memorization

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        // edge case
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int row = matrix.length, col = matrix[0].length, lgst = 0;
        int[][] visited = new int[row][col];

        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                int tmp = dfs(matrix, r, c, visited, matrix[r][c]-1);
                lgst = Math.max(lgst, tmp);
            }
        }

        return lgst;
    }

    private int dfs(int[][] matrix, int r, int c, int[][] visited, int last) {
        // exit
        if (r < 0 || r >= matrix.length || c < 0 || c >= matrix[0].length) return 0;  // out of boundary
        if (matrix[r][c] <= last) return 0;  // not increasing
        if (visited[r][c] > 0) return visited[r][c];  // processed before, has result

        // process
        visited[r][c] = Math.max(visited[r][c], dfs(matrix, r+1, c, visited, matrix[r][c]) + 1);
        visited[r][c] = Math.max(visited[r][c], dfs(matrix, r-1, c, visited, matrix[r][c]) + 1);
        visited[r][c] = Math.max(visited[r][c], dfs(matrix, r, c+1, visited, matrix[r][c]) + 1);
        visited[r][c] = Math.max(visited[r][c], dfs(matrix, r, c-1, visited, matrix[r][c]) + 1);

        return visited[r][c];
    }
}

use dirs technique in a matrix, but I think my original solution above is more intuitive.

class Solution {
    private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public int longestIncreasingPath(int[][] matrix) {
        // edge case
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int row = matrix.length, col = matrix[0].length, lgst = 0;
        int[][] visited = new int[row][col];

        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                int tmp = dfs(matrix, r, c, visited);
                lgst = Math.max(lgst, tmp);
            }
        }

        return lgst;
    }

    private int dfs(int[][] matrix, int r, int c, int[][] visited) {
        // exit
        if (visited[r][c] > 0) return visited[r][c];  // processed before, has result

        // process
        for (int[] d : dirs) {
            int r2 = d[0] + r;
            int c2 = d[1] + c;
            if (r2 >=0 && r2 < matrix.length && c2 >= 0 && c2 < matrix[0].length) {  // boundary check
                if (matrix[r][c] >= matrix[r2][c2]) continue; // not increasing
                visited[r][c] = Math.max(visited[r][c], dfs(matrix, r2, c2, visited));
            }
        }

        return ++visited[r][c];  // plus itself count as 1
    }
}

AC2: Topological sort

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/discuss/288520/Longest-Path-in-DAG

I think this is a littble bit irrelevant and overkill. But interesting thoughts: use topological sort to iterate a graph, where order matters.

public int longestIncreasingPath(int[][] matrix) {
        // Corner cases
        if (matrix.length == 0) {
            return 0;
        }

        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int rows = matrix.length, cols = matrix[0].length;

        // indegree[i][j] indicates thee number of adjacent cells bigger than matrix[i][j]
        int[][] indegree = new int[rows][cols];
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                for (int[] dir: dirs) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];
                    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
                        if (matrix[nx][ny] > matrix[x][y]) {
                            indegree[x][y]++;
                        }
                    }
                }

            }
        }

        // Add each cell with indegree zero to the queue
        Queue<int[]> queue = new LinkedList<>();
        for (int x = 0; x < rows; x++) {
            for (int y = 0; y < cols; y++) {
                if (indegree[x][y] == 0) {
                    queue.offer(new int[]{x, y});
                }
            }
        }

        int length = 0; // The longest path so far
        // BFS implements the Topological Sort
        while(!queue.isEmpty()) {
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                int[] cur = queue.poll();
                int x = cur[0];
                int y = cur[1];
                for (int[] dir: dirs) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];
                    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
                        if (matrix[nx][ny] < matrix[x][y] 
                            && --indegree[nx][ny] == 0) {
                           queue.offer(new int[]{nx, ny});
                        }
                    }
                }
            }
            length++;
        }

        return length;
    }