Challenge: Find The Longest Path In Matrix

Question

Find the longest path in a matrix with given constraints

Given a n*n matrix where all numbers are distinct, 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.

We can move in 4 directions from a given cell (i, j), i.e., we can move to (i+1, j) or (i, j+1) or (i-1, j) or (i, j-1) with the condition that the adjacent cells have a difference of 1.

Example:

Input: mat[][] = {{1, 2, 9} {5, 3, 8} {4, 6, 7}} Output: 4 The long

Answer 1

I used recursion
function followPath(num,pathLength,pathnum,val){
if (num <= smallArr.length){
pathLength[pathnum]=val;
if(isPath(num)){
followPath(num+1,pathLength,pathnum,val+1);
}
else{
followPath(num+1,pathLength,num,0);
}
}
return pathLength;
}

https://code.sololearn.com/W3HgARPHhPjT/#html

Answer 2

here's mine
https://code.sololearn.com/c504tNcEUe5I/?ref=app

Answer 3

Here's my C# implementation ✌

I thought this question requires recursion in the first place but found out it's not necessary after I begin to code. Any ideas to improve/simplify my code are welcome!

P/S: The core algorithm is just the last 3 functions only. Short and sweet! ❤😁

https://code.sololearn.com/ca1XX2NMDa6R/?ref=app

Answer 4

@Dirac you can try to post the code 😊

Answer 5

heres mine

https://code.sololearn.com/cY6qxKPjoYC1/?ref=app

## HERE IS SOME OF MY PREVIOUS CHALLENGES ##
(( CHECK IF YOU WANT ))

https://www.sololearn.com/discuss/668821/?ref=app

https://www.sololearn.com/discuss/666260/?ref=app

https://www.sololearn.com/discuss/664933/?ref=app

https://www.sololearn.com/discuss/658245/?ref=app

https://www.sololearn.com/discuss/653982/?ref=app

Answer 6

we can use single source shortest path algorithm

Answer 7

sayan tq..

Answer 8

yeah @Sayan

Answer 9

here, one more of my not easy solutions 😁
https://code.sololearn.com/WKoZGtmITMPL/?ref=app

Answer 10

Hi,

Here's another Python implementation:
https://code.sololearn.com/c9Ul9MwiH85p/#py

Answer 11

@Sivan you can use any method to solve this just post your idea in a implementation😊

Answer 12

@Louis nice js coding style

Answer 13

Gaston which is a source and destination in matrix

Answer 14

to find longest path which is a source vertex

Answer 15

The longest path is 6-7-8-9. in this matrix

Answer 16

Great fun. Lots of constraints make this problem more variable for smaller n.

### Python Version:
https://code.sololearn.com/cDB6Cpg8QI6K/#py
# The key is recognizing that for each position in the matrix [i,j] there is only one unique path that satisfies the constraints. The minimum path is 1 ([i,j] has no adjacent neighbors that satisfy the rules) and the maximum possible path is n^2.
# Additionally, when checking the 4 adjacent positions for validity, once one has been found that satisfies the difference-of-one condition, you do not need to check any other paths. This is because of the "distinct" rule of the generated matrix.

I originally coded my result in R. But it won't run on SoloLearn. Here's the code anyway.

### R Version:
https://code.sololearn.com/c8SbFy3OV14x

Answer 17

#include<bits/stdc++.h>
#define n 3
using namespace std;

// Returns length of the longest path beginning with mat[i][j].
// This function mainly uses lookup table dp[n][n]
int findLongestFromACell(int i, int j, int mat[n][n], int dp[n][n])
{
// Base case
if (i<0 || i>=n || j<0 || j>=n)
return 0;

// If this subproblem is already solved
if (dp[i][j] != -1)
return dp[i][j];

// Since all numbers are unique and in range from 1 to n*n,
// there is atmost one possible direction from any cell
if (j<n-1 && ((mat[i][j] +1) == mat[i][j+1]))
return dp[i][j] = 1 + findLongestFromACell(i,j+1,mat,dp);

if (j>0 && (mat[i][j] +1 == mat[i][j-1]))
return dp[i][j] = 1 + findLongestFromACell(i,j-1,mat,dp);

if (i>0 && (mat[i][j] +1 == mat[i-1][j]))
return dp[i][j] = 1 + findLongestFromACell(i-1,j,mat,dp);

if (i<n-1 && (mat[i][j] +1 == mat[i+1][j]))
return dp[i][j] = 1 + findLongestFromACell(i+1,j,mat,dp);

// If none of the adjacent fours is one greater
return dp[i][j] = 1;
}

// Returns length of the longest path beginning with any cell
int finLongestOverAll(int mat[n][n])
{
int result = 1; // Initialize result

// Create a lookup table and fill all entries in it as -1
int dp[n][n];
memset(dp, -1, sizeof dp);

// Compute longest path beginning from all cells
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
if (dp[i][j] == -1)
findLongestFromACell(i, j, mat, dp);

// Update result if needed
result = max(result, dp[i][j]);
}
}

return result;
}

// Driver program
int main()
{
int mat[n][n] = {{1, 2, 9},
{5, 3, 8},
{4, 6, 7}};
cout << "Length of the longest path is "
<< finLongestOverAll(mat);
return 0;
}

Answer 18

small program in Python
https://code.sololearn.com/c8QbXp9D7Km4/?ref=app

Answer 19

@koushik y Yup you may head to Discuss section and find the keyword "challenge".

There are a lot of interesting challenges over there but this one stand out for this week and congrats to Gawen! 😁

Answer 20

https://code.sololearn.com/cfmbhS0WJ15P/?ref=app