Longest Increasing Path in a Matrix

Photo by Stephen Leonardi on Unsplash

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).

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

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

Solution

From the above example, we can see that, from every cell, we can move in at most four directions: up, down, left, and right. We will choose to move in the direction whose cell’s value is greater than the current one. We can use Depth First Search (DFS) algorithm on each cell of the matrix to calculate the maximum number of routers that can be reached from the current cell. We will keep updating the maximum reachable distance for each cell and return this value when the complete matrix has been traversed.

While effective, this approach is not very efficient as its time complexity can reach up to 2​m+n​​. This is because we keep performing duplicate calculations as the value for the same cell can get computed again in a different DFS call. To optimize this DFS, we can cache the results for each cell when its value gets computed. This way, if we encounter the same cell again, instead of calling an expensive DFS function on it, we can simply return its value from the cache. This technique is also known as Memorization.

Let’s see how we might implement this functionality:

1. Initialize a maxPath variable and assign it a value 0.
2. Recursively call DFS on each cell of the matrix, and update maxPath if the result of the DFS call is greater than the current maxPath value.
3. During a DFS call, keep visiting each of the four paths from the current cell if the value in the next cell is greater than the value in the current cell.
4. If the result for a visited cell is not calculated, we compute it and cache (or memorize) it.
5. Otherwise, we get it from the cache directly.
6. Finally, return the maxPath variable.

Let m be the number of rows and n be the number of columns.

Time complexity

The time complexity will be O(m×n) because, in the worst case, we’ll be traversing the complete grid of size m x n.

Space complexity

The space complexity will be O(m×n) because the cache will be of the size m x n.