329. Longest Increasing Path in a Matrix
Longest Increasing Path in a Matrix (LeetCode 329) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Unique Paths on Grid) subpattern.
- NeetCode 150 · #117 of 150 · 2-D Dynamic Programming
- NeetCode 250 · #202 of 250 · 2-D Dynamic Programming
How to solve Longest Increasing Path in a Matrix
Longest Increasing Path in a Matrix is a Unique Paths on Grid problem, part of Dynamic Programming (DP) Patterns. Count paths and find optimal paths in grids using 2D dynamic programming.
Work towards the solution in these steps:
- Think of each cell as a state whose answer is the longest increasing path beginning there.
- When considering a neighboring cell, only neighbors with a larger value can extend the current path.
- Cache the result computed for each cell so that the same starting position is not solved repeatedly.
The reference solution runs in O(rows * cols) time and O(rows * cols) space.
The Longest Increasing Path in a Matrix solution and editorial walks through the full approach with reference code.
Problem statement
Implement longestIncreasingPath to analyze the integer grid in matrix. A cell is identified by its row and column, and two cells are adjacent when one is directly above, below, left, or right of the other; diagonal movement is not allowed.
A path may begin at any cell and may move only to an adjacent cell whose value is strictly greater than the value of the current cell. The path length is the number of cells visited, including its starting cell. Return the greatest path length available in matrix.
The input grid is not modified, and paths may not move outside the grid. If every possible move would fail, a single cell still forms a path of length 1.
Example 1:
Input: matrix = [[-3,-2,-1],[4,3,0],[5,6,7]] Output: 9 Explanation: The cells can be visited in the strictly increasing order -3, -2, -1, 0, 3, 4, 5, 6, 7, with each consecutive pair orthogonally adjacent.
Example 2:
Input: matrix = [[7,7],[7,7]] Output: 1 Explanation: Equal values cannot be used for a move because each next cell must be strictly greater, so every path has length 1.
Example 3:
Input: matrix = [[12,1,2,3],[11,10,9,4]] Output: 8 Explanation: A longest path is 1 → 2 → 3 → 4 → 9 → 10 → 11 → 12, and every consecutive pair is orthogonally adjacent.
Constraints:
- 1 <= matrix.length <= 200 - 1 <= matrix[0].length <= 200 - All rows in matrix have the same length. - -2^31 <= matrix[row][column] <= 2^31 - 1 - matrix contains at least one cell.
Topics and companies
Topics: Array, Matrix, Dynamic Programming, Depth-First Search, Memoization.
How to practise Longest Increasing Path in a Matrix on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(rows * cols) time and O(rows * cols) space.
Open Longest Increasing Path in a Matrix in the code editor, or read the Longest Increasing Path in a Matrix editorial for a worked solution with its approach and complexity analysis.
Where Longest Increasing Path in a Matrix sits in the DSA pattern sheet
- Dynamic Programming (DP) Patterns pattern guide
- 2D Array (Unique Paths on Grid) subpattern
- The full DSA patterns sheet
Problems related to Longest Increasing Path in a Matrix
Other problems that use the same 2D Array (Unique Paths on Grid) and Dynamic Programming (DP) Patterns techniques:
- Count Square Submatrices with All Ones — Medium, same subpattern
- Interleaving String — Medium, same subpattern
- Maximal Square — Medium, same subpattern
- Minimum Falling Path Sum — Medium, same subpattern
- Minimum Path Sum — Medium, same subpattern
- Triangle — Medium, same subpattern
Longest Increasing Path in a Matrix FAQ
What is the LeetCode number of Longest Increasing Path in a Matrix?
Longest Increasing Path in a Matrix is LeetCode problem 329, rated Hard.
What pattern is used to solve Longest Increasing Path in a Matrix?
Longest Increasing Path in a Matrix is a Unique Paths on Grid problem. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Unique Paths on Grid) subpattern.
What is the time complexity of Longest Increasing Path in a Matrix?
The reference solution runs in O(rows * cols) time and O(rows * cols) space.