Longest Increasing Path in Matrix
Given a matrix of N rows and M columns. From m[i][j], we can move to m[i+1][j], if m[i+1][j] > m[i][j], or can move to m[i][j+1] if m[i][j+1] > m[i][j]. The task is print longest path length if we start from (0, 0).
Examples:
Input : N = 4, M = 4 m[][] = { { 1, 2, 3, 4 }, { 2, 2, 3, 4 }, { 3, 2, 3, 4 }, { 4, 5, 6, 7 } }; Output : 7 Longest path is 1 2 3 4 5 6 7. Input : N = 2, M =2 m[][] = { { 1, 2 }, { 3, 4 } }; Output :3 Longest path is either 1 2 4 or 1 3 4.
The idea is to use dynamic programming. Maintain the 2D matrix, dp[][], where dp[i][j] store the value of the length of the longest increasing sequence for submatrix starting from the ith row and jth column.
Let the longest increasing sub sequence values for m[i+1][j] and m[i][j+1] be known already as v1 and v2 respectively. Then the value for m[i][j] will be max(v1, v2) + 1.
We can start from m[n-1][m-1] as the base case with the length of longest increasing subsequence be 1, moving upwards and leftwards updating the value of cells. Then the LIP value for cell m[0][0] will be the answer.
Below is the implementation of this approach:
C++
// CPP program to find longest increasing // path in a matrix. #include <bits/stdc++.h> #define MAX 10 using namespace std; // Return the length of LIP in 2D matrix int LIP( int dp[][MAX], int mat[][MAX], int n, int m, int x, int y) { // If value not calculated yet. if (dp[x][y] < 0) { int result = 0; // If reach bottom right cell, return 1. if (x == n - 1 && y == m - 1) return dp[x][y] = 1; // If reach the corner of the matrix. if (x == n - 1 || y == m - 1) result = 1; // If value greater than below cell. if (x != n-1) // x reaches last row if (mat[x][y] < mat[x + 1][y]) result = 1 + LIP(dp, mat, n, m, x + 1, y); // If value greater than left cell. if (y != m-1) // y reaches last column if (mat[x][y] < mat[x][y + 1]) result = max(result, 1 + LIP(dp, mat, n, m, x, y + 1)); dp[x][y] = result; } return dp[x][y]; } // Wrapper function int wrapper( int mat[][MAX], int n, int m) { int dp[MAX][MAX]; memset (dp, -1, sizeof dp); return LIP(dp, mat, n, m, 0, 0); } // Driven Program int main() { int mat[][MAX] = { { 1, 2, 3, 4 }, { 2, 2, 3, 4 }, { 3, 2, 3, 4 }, { 4, 5, 6, 7 }, }; int n = 4, m = 4; cout << wrapper(mat, n, m) << endl; return 0; } |
Java
// Java program to find longest increasing // path in a matrix. import java.util.*; class GFG { // Return the length of LIP in 2D matrix static int LIP( int dp[][], int mat[][], int n, int m, int x, int y) { // If value not calculated yet. if (dp[x][y] < 0 ) { int result = 0 ; // If reach bottom right cell, return 1. if (x == n - 1 && y == m - 1 ) return dp[x][y] = 1 ; // If reach the corner of the matrix. if (x == n - 1 || y == m - 1 ) result = 1 ; // If value greater than below cell. if (x + 1 < n && mat[x][y] < mat[x + 1 ][y]) result = 1 + LIP(dp, mat, n, m, x + 1 , y); // If value greater than left cell. if (y + 1 < m && mat[x][y] < mat[x][y + 1 ]) result = Math.max(result, 1 + LIP(dp, mat, n, m, x, y + 1 )); dp[x][y] = result; } return dp[x][y]; } // Wrapper function static int wrapper( int mat[][], int n, int m) { int dp[][] = new int [ 10 ][ 10 ]; for ( int i = 0 ; i < 10 ; i++) Arrays.fill(dp[i], - 1 ); return LIP(dp, mat, n, m, 0 , 0 ); } /* Driver program to test above function */ public static void main(String[] args) { int mat[][] = { { 1 , 2 , 3 , 4 }, { 2 , 2 , 3 , 4 }, { 3 , 2 , 3 , 4 }, { 4 , 5 , 6 , 7 }, }; int n = 4 , m = 4 ; System.out.println(wrapper(mat, n, m)); } } // This code is contributed by Arnav Kr. Mandal. |
Python3
# Python3 program to find longest # increasing path in a matrix. MAX = 20 # Return the length of # LIP in 2D matrix def LIP(dp, mat, n, m, x, y): # If value not calculated yet. if (dp[x][y] < 0 ): result = 0 # // If reach bottom right cell, return 1 if (x = = n - 1 and y = = m - 1 ): dp[x][y] = 1 return dp[x][y] # If reach the corner # of the matrix. if (x = = n - 1 or y = = m - 1 ): result = 1 # If value greater than below cell. if (x + 1 < n and mat[x][y] < mat[x + 1 ][y]): result = 1 + LIP(dp, mat, n, m, x + 1 , y) # If value greater than left cell. if (y + 1 < m and mat[x][y] < mat[x][y + 1 ]): result = max (result, 1 + LIP(dp, mat, n, m, x, y + 1 )) dp[x][y] = result return dp[x][y] # Wrapper function def wrapper(mat, n, m): dp = [[ - 1 for i in range ( MAX )] for i in range ( MAX )] return LIP(dp, mat, n, m, 0 , 0 ) # Driver Code mat = [[ 1 , 2 , 3 , 4 ], [ 2 , 2 , 3 , 4 ], [ 3 , 2 , 3 , 4 ], [ 4 , 5 , 6 , 7 ]] n = 4 m = 4 print (wrapper(mat, n, m)) # This code is contributed # by Sahil Shelangia |
C#
// C# program to find longest increasing // path in a matrix. using System; public class GFG { // Return the length of LIP in 2D matrix static int LIP( int [, ] dp, int [, ] mat, int n, int m, int x, int y) { // If value not calculated yet. if (dp[x, y] < 0) { int result = 0; // If reach bottom right cell, return 1. if (x == n - 1 && y == m - 1) return dp[x, y] = 1; // If reach the corner of the matrix. if (x == n - 1 || y == m - 1) result = 1; // If value greater than below cell. if (x + 1 < n && mat[x, y] < mat[x + 1, y]) result = 1 + LIP(dp, mat, n, m, x + 1, y); // If value greater than left cell. if (y + 1 < m && mat[x, y] < mat[x, y + 1]) result = Math.Max(result, 1 + LIP(dp, mat, n, m, x, y + 1)); dp[x, y] = result; } return dp[x, y]; } // Wrapper function static int wrapper( int [, ] mat, int n, int m) { int [, ] dp = new int [10, 10]; for ( int i = 0; i < 10; i++) { for ( int j = 0; j < 10; j++) { dp[i, j] = -1; } } return LIP(dp, mat, n, m, 0, 0); } /* Driver code */ public static void Main() { int [, ] mat = { { 1, 2, 3, 4 }, { 2, 2, 3, 4 }, { 3, 2, 3, 4 }, { 4, 5, 6, 7 }, }; int n = 4, m = 4; Console.WriteLine(wrapper(mat, n, m)); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript program to find longest increasing path in a matrix. // Return the length of LIP in 2D matrix function LIP(dp, mat, n, m, x, y) { // If value not calculated yet. if (dp[x][y] < 0) { let result = 0; // If reach bottom right cell, return 1. if (x == n - 1 && y == m - 1) return dp[x][y] = 1; // If reach the corner of the matrix. if (x == n - 1 || y == m - 1) result = 1; // If value greater than below cell. if (x + 1 < n && mat[x][y] < mat[x + 1][y]) result = 1 + LIP(dp, mat, n, m, x + 1, y); // If value greater than left cell. if (y + 1 < m && mat[x][y] < mat[x][y + 1]) result = Math.max(result, 1 + LIP(dp, mat, n, m, x, y + 1)); dp[x][y] = result; } return dp[x][y]; } // Wrapper function function wrapper(mat, n, m) { let dp = new Array(10); for (let i = 0; i < 10; i++) { dp[i] = new Array(10); for (let j = 0; j < 10; j++) { dp[i][j] = -1; } } return LIP(dp, mat, n, m, 0, 0); } let mat = [ [ 1, 2, 3, 4 ], [ 2, 2, 3, 4 ], [ 3, 2, 3, 4 ], [ 4, 5, 6, 7 ], ]; let n = 4, m = 4; document.write(wrapper(mat, n, m)); </script> |
7
Time Complexity: O(N*M).
Space Complexity: O(N*M)
Contact Us