Longest Increasing Substring is the most common question asked in DSA interviews. But if we modify this question in a 2D array and find the Longest Increasing Path in the matrix it uses the same concept. In this article, we will learn how to find the Longest Increasing Path using Dynamic Programming.
Longest Increasing Path in a Matrix Problem
The problem is that you are given a matrix of size (n*m) where n is the size of rows in that matrix and m is the size of the column in that matrix. You have to find the length of the longest increasing path in that matrix by starting from any index and taking any adjacent move i.e. you can move up, down, right, and left while in the matrix.
Consider an example you are given a matrix below and also shown its Longest increasing path:
In this case, the length is 7
Note: You can only move in all four directions which is adjacent to the cell for example if you are at cell no c(2,2) you can move to c(2,1), c(1,2), c(3,1), c(2,3) you cannot move diagonally i.e. you cannot move c(1,1) or c(3,3), etc.
Naive Recursive Approach
The first approach that comes to mind is to go at every cell of the matrix and then keep on going till we find some greater value than it and if at some place there is no place to move further backtrack i.e. go to the previous place and repeat the process.
This process is known as the recursive approach. Let us take an example and understand it step by step
- First, we will choose from which cell we want to start for this we make a loop for example we can start from any point either from cell(1,1), or cell(2,3) at any point.
- Once the point is chosen we go in all four directions if it is possible to move that is if the cell lies inside the matrix and the value of that cell is greater than the current cell. In this case, if we start from cell(0,0) we can only move right and down i.e. cell(0,1) and cell(1,0)
- Then we will get the maximum value out of all four directions add 1 in it, and then return that max value out of them for example when we are at cell(0,0) two paths are there one returns 6 and the other returns 2 we take max i.e. 6 and add one to it and return 7.
- Once all the cells are done we return the maximum value among them. In this case, the max value returned is 7 by the [1, 2, 3, 4, 5, 6, 7] path.
Time complexity would be O(n^2*m^2) as we are recursively going on each cell, and from each cell, we are looking for all possible solutions so in the worst case it would be O(n^2*m^2). Space Complexity will be O(1) as there is constant space required in this approach.
Dynamic Programming Approach
This is the optimized approach in this you are using the same approach as used previously but the only difference in this approach is we will not calculate the previously calculated value. We will instead store it at some place and use that value whenever required this reduces our time to repeatedly calculate the same value again and again.
- Firstly we will make an array dp of the same size as of matrix and assign all the values in it with -1.
- Now iterate over the matrix and if the dp value at that place is not -1 we will not move further and if not we will calculate its value by moving in all four directions and taking max of them same as done previously in brute force.
- Now return the max value at last.
Let us know how to implement it.
C++ Code
Here is the C++ program to find the longest increasing path in matrix:
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>>mov={{-1,0},{1,0},{0,-1},{0,1}};
bool is_valid(int x, int y, int row, int col){
if(x<0 || y<0 || x>=row || y>=col) return false;
return true;
}
int dfs(int x, int y, vector<vector<int>>&v, vector<vector<int>>&dp, int row, int col, int par){
//if it's not valid we are returning
if(!is_valid(x, y, row, col)) return 0;
//if par i.e. previous value is greater than the current value return 0
if(par >= v[x][y]) return 0;
if(dp[x][y]!=-1) return dp[x][y];
int len = -1;
for(int i=0; i<4; i++){
int a = x + mov[i].first;
int b = y + mov[i].second;
len = max(len, dfs(a, b, v, dp, row, col, v[x][y]));
}
return dp[x][y] = 1 + len;
}
int main(){
// Given matrix
vector<vector<int>>v={{1,2,3,4},{5,6,1,5},{1,1,7,6}};
//size of row and column
int row=v.size(), col=v[0].size();
//variable that stores the maximum value of the path
int mx=-1;
// making a dp matrix to store the precomputed values initializing the values with -1.
vector<vector<int>>dp(row, vector<int>(col,-1));
// iterating over all values
for(int i=0; i<row; i++){
for(int j=0;j<col;j++){
if(dp[i][j]==-1) dfs(i, j, v, dp, row, col, -1);
mx= max(mx, dp[i][j]);
}
}
cout<<mx<<endl;
return 0;
}Java Code
Here is the Java program to implement the dynamic programming approach:
import java.util.*;
public class Main {
static class Pair {
int first, second;
public Pair(int first, int second) {
this.first = first;
this.second = second;
}
}
static List<Pair> mov = Arrays.asList(new Pair(-1, 0), new Pair(1, 0), new Pair(0, -1), new Pair(0, 1));
static boolean isValid(int x, int y, int row, int col) {
return x >= 0 && y >= 0 && x < row && y < col;
}
static int dfs(int x, int y, int[][] v, int[][] dp, int row, int col, int par) {
if (!isValid(x, y, row, col)) return 0;
if (par >= v[x][y]) return 0;
if (dp[x][y] != -1) return dp[x][y];
int len = -1;
for (Pair pair: mov) {
int a = x + pair.first;
int b = y + pair.second;
len = Math.max(len, dfs(a, b, v, dp, row, col, v[x][y]));
}
return dp[x][y] = 1 + len;
}
public static void main(String[] args) {
// Given matrix
int[][] v = {{1, 2, 3, 4}, {5, 6, 1, 5}, {1, 1, 7, 6}};
int row = v.length;
int col = v[0].length;
int mx = -1;
int[][] dp = new int[row][col];
// Initializing the dp matrix with -1
for (int i = 0; i < row; i++) {
Arrays.fill(dp[i], -1);
}
// Iterating over all values
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (dp[i][j] == -1) dfs(i, j, v, dp, row, col, -1);
mx = Math.max(mx, dp[i][j]);
}
}
System.out.println(mx);
}
}Python Code
You can do it in Python as well:
mov = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# Check if a position is valid
def is_valid(x, y, row, col):
if x < 0 or y < 0 or x >= row or y >= col:
return False
return True
# Depth First Search
def dfs(x, y, v, dp, row, col, par):
if not is_valid(x, y, row, col):
return 0
if par >= v[x][y]:
return 0
if dp[x][y] != -1:
return dp[x][y]
length = -1
for i in range(4):
a = x + mov[i][0]
b = y + mov[i][1]
length = max(length, dfs(a, b, v, dp, row, col, v[x][y]))
dp[x][y] = 1 + length
return dp[x][y]
if __name__ == "__main__":
# Given matrix
v = [
[1, 2, 3, 4],
[5, 6, 1, 5],
[1, 1, 7, 6]
]
# Size of row and column
row = len(v)
col = len(v[0])
# Variable that stores maximum value of the path
mx = -1
# Making a dp matrix to store the precomputed values initializing the values with -1.
dp = [[-1] * col for _ in range(row)]
# Iterating overall values
for i in range(row):
for j in range(col):
if dp[i][j] == -1:
dfs(i, j, v, dp, row, col, -1)
mx = max(mx, dp[i][j])
print(mx)Output:
7In this approach, the time reduces to O(nm) as we are already storing the values that are computed and then just using those value again. Space complexity will now be increased to O(nm) as an array is required to store the values.
Here is a comparison of both the approaches:
| Approach | Time Complexity | Space Complexity | Description |
|---|---|---|---|
| Resurcive/ Naive | O((n^2)*(m^2)) | O(1) | As we are recursively going on each cell, and from each cell, we are looking for all possible solutions. |
| Optimized | O(nm) | O(nm) | As we are storing the previously computed values in the array. |
Conclusion
In this article, we discussed the longest-increasing path problem from leetcode, solves it using the recursive approach which has a time complexity of O(n^2*m^2), and then we optimized this approach by using dynamic programming with a time complexity of O(nm).
