Problem

Given a 2D array of integers, write a function that returns the length of the longest path of consecutive integers starting from the top left corner of the array. The path can move up, down, left, or right.
Input:
[[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]]
Output:
4 (1, 2, 3, 4)

Solution

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int longestPath(vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();
    vector<vector<int>> dp(n, vector<int>(m, 1));
    int res = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i > 0 && matrix[i][j] == matrix[i - 1][j] + 1) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + 1);
            }
            if (j > 0 && matrix[i][j] == matrix[i][j - 1] + 1) {
                dp[i][j] = max(dp[i][j], dp[i][j - 1] + 1);
            }
            res = max(res, dp[ i][j]);
        }
    }
    return res;
}

int main() {
    vector<vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    cout << longestPath(matrix) << endl;
    return 0;
}