# 0329. 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:** ![](https://assets.leetcode.com/uploads/2021/01/05/grid1.jpg) ``` **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:** ![](https://assets.leetcode.com/uploads/2021/01/27/tmp-grid.jpg) ``` **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 ```java 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. ```java 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 I think this is a littble bit irrelevant and overkill. But interesting thoughts: use topological sort to iterate a graph, where order matters. ```java 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 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; } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://jaywin.gitbook.io/leetcode/solutions/0329-longest-increasing-path-in-a-matrix.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.