Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix 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.

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

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:

Preparing this workspace.