# 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.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to use dynamic programming. Maintain the 2D matrix, dp[][], where dp[i][j] store the value of length of longest increasing sequence for sub matrix starting from ith row and j-th 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 base case with length of longest increasing sub sequence 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 ` `#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 left 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` `(mat[x][y] < mat[x+1][y]) ` `      ``result = 1 + LIP(dp, mat, n, m, x+1, y); ` `       `  `    ``// If value greater than left cell. ` `    ``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; ` `} `

/div>

## 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 left 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 left 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.  ` `        ``elif` `(mat[x][y] < mat[x ``+` `1``][y]): ` `            ``result ``=` `1` `+` `LIP(dp, mat, n,  ` `                             ``m, x ``+` `1``, y) ` ` `  `        ``# If value greater than left cell. ` `        ``elif` `(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 ``=` `[[``7` `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 left 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 */`

Output:

```7
```

Time Complexity: O(N*M).