Using dynamic programming.

LengthOfLongestSequenceEndingAt(i, j) is 1 if none of the eight neighbors of matrix[i][j] are one less than matrix[i][j]. If it has a consecutive neighbor, LengthOfLongestSequenceEndingAt(i, j) is 1 + LengthOfLongestSequenceEndingAt of the neighbor with the highest LengthOfLongestSequenceEndingAt.

The answer then is the maximum LengthOfLongestSequenceEndingAt(i,j) for all i's and j's.

Below is a C++ implementation:

#include

#include

using namespace std;

using mat_t = vector>;

int longestEndingAt(int i, int j, mat_t &longestEndingAtMatrix, const mat_t &M) {

if(longestEndingAtMatrix[i][j] != 0) return longestEndingAtMatrix[i][j];

int longest = 1;

for(auto dx : {-1, 0, 1}) {

if((i + dx = M.size())) continue;

for(auto dy : {-1, 0, 1}) {

if((j + dy = M[0].size())) continue;

if(M[i + dx][j + dy] == M[i][j] - 1) {

auto current = longestEndingAt(i + dx, j + dy, longestEndingAtMatrix, M) + 1;

if(current > longest) longest = current;

}

}

}

longestEndingAtMatrix[i][j] = longest;

return longest;

}

int longest(mat_t M) {

mat_t longestEndingAtMatrix(M.size(),vector(M[0].size(), 0));

int result = 0;

for(int i = 0; i result) result = d;

}

}

return result;

}

int main() {

mat_t A = {{2, 3, 4},{8, 7, 7},{5, 6, 5}};

cout << longest(A) << endl;

return 0;

}

output: 4

complexity: O(n^2)

I first devised an O(n^4) algorithm but with the help of the interviewer we formulated one in O(n^2).