Longest Increasing Path in a Matrix
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).
Examples
Constraints
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 2^31 - 1
DFS with Memoization
Approach
We can find the longest increasing path starting from any cell using Depth-First Search (DFS). Since recalculating paths from the same cell is redundant and leads to exponential time complexity, we memoize the results. `dp[i][j]` stores the length of the longest increasing path starting from `(i, j)`. For each cell, we explore its 4 neighbors. If a neighbor is within bounds and strictly greater than the current cell, we recursively call DFS on it and take the maximum path length plus 1. The global maximum among all cells is our answer.
Complexity Analysis
Due to memoization, each cell is visited and its neighbors are checked at most once. Therefore, the time complexity is proportional to the number of cells O(m * n). The space complexity is O(m * n) for the memoization table and recursion stack.
class Solution { private int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; public int longestIncreasingPath(int[][] matrix) { if (matrix == null || matrix.length == 0) return 0; int m = matrix.length; int n = matrix[0].length; int[][] memo = new int[m][n]; int longestPath = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { longestPath = Math.max(longestPath, dfs(matrix, i, j, memo)); } } return longestPath; } private int dfs(int[][] matrix, int i, int j, int[][] memo) { if (memo[i][j] > 0) return memo[i][j]; int max = 1; for (int[] dir : dirs) { int x = i + dir[0]; int y = j + dir[1]; if (x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length && matrix[x][y] > matrix[i][j]) { max = Math.max(max, 1 + dfs(matrix, x, y, memo)); } } memo[i][j] = max; return max; }}