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.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 231 - 1This approach uses a combination of Depth First Search (DFS) and memoization to solve the problem efficiently. We explore each cell, attempting to find the longest increasing path starting from that cell. To avoid recalculating the path length for each call from the same cell, we use memoization to store already computed results.
In this Python solution, we define a helper function dfs that performs DFS on the matrix starting from a given cell. We utilize a memo table to store the longest path from each cell to avoid redundant calculations, improving performance significantly. The main function starts by iterating over each cell to compute the maximum length path by considering each cell as a starting point.
C++
Java
The time complexity is O(m * n) because each cell is computed once and cached. The space complexity is also O(m * n) due to the memoization table.
This approach systematically calculates the longest increasing path dynamically by first iterating over the matrix and then updating results based on previously computed values. By using a dynamic programming table, we determine, for each cell, the longest chain it can contribute to incrementally.
The JavaScript solution uses dynamic programming. For each cell, the function dfs recursively explores valid neighbors, resulting in the longest increasing path starting from that cell. The result for each cell is stored in a DP table before being returned, which ensures efficiency by preventing the recalculation of already known results.
C#
The time complexity is O(m * n) due to the fact that each matrix cell can be a starting point and is only calculated once with memoization guidance. The space complexity is O(m * n) because a result is stored for each cell in the DP table.
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) with Memoization | The time complexity is |
| Dynamic Programming | The time complexity is |
Longest Increasing Path in a Matrix - Leetcode 329 • NeetCode • 73,336 views views
Watch 9 more video solutions →Practice Longest Increasing Path in a Matrix with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor