New update is available. Click here to update.

Topics

You are given a ‘N’ * ‘N’ matrix where all numbers are distinct from (1 to N * N). You are required to find the maximum length path (starting from any cell) such that all cells along the path are in increasing order with a difference of 1.

Only four possible movements are allowed i.e, Up, Down, Left , and Right.

```
Input: Mat [ ][ ] = { { 9 , 1 , 3 }
{ 7 , 4 , 2 }
{ 6 , 5 , 8 } }
Output: 4
Explanation: The longest path is of length ‘4’ { 4 - 5 - 6 - 7 }
```

Detailed explanation

```
1 <= T <= 100
1 <= N <= 10^3
Time Limit : 1 sec
```

```
2
3
1 2 9
5 3 8
4 6 7
4
1 15 13 14
2 8 9 10
3 11 16 12
4 5 6 7
```

```
4
7
```

```
In test case 1:
For ‘N’ = 3,
1 2 9
5 3 8
4 6 7
The longest path is of length ‘4’ { 6 -> 7 -> 8 -> 9 }
In test case 2:
For ‘N’ = 4,
1 15 13 14
2 8 9 10
3 11 16 12
4 5 6 7
The longest path is of length ‘7’ { 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 }
```

```
2
2
1 2
3 4
3
1 5 6
9 4 7
2 3 8
```

```
2
7
```