+ 109

# Challenge: Find The Longest Path In Matrix

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

69 ответов

+ 42

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

+ 25

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

+ 15

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

+ 10

@Dirac you can try to post the code 😊

+ 8

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

+ 8

we can use single source shortest path algorithm

+ 8

sayan tq..

+ 7

yeah @Sayan

+ 7

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

+ 7

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

+ 7

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

+ 7

@Louis nice js coding style

+ 7

Gaston which is a source and destination in matrix

+ 7

to find longest path which is a source vertex

+ 6

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

+ 6

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

+ 5

#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;
}

+ 5

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

+ 5

@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! 😁