Longest Path of Consecutive Numbers in a 2D Array

Problem

Given a 2D array of integers, find the length of the longest path of consecutive numbers that can be formed starting from any cell in the array.
The path can move in any of the 8 directions – (x,y) to (x+1, y), (x, y+1), (x-1, y), (x, y-1), (x-1, y-1), (x+1,y+1), (x-1,y+1), (x+1,y-1).
Example input:
[[1, 2, 9]
 [5, 3, 8]
 [4, 6, 7]]
Example output:
4

Solution

This solution is in Python. Our A.I. can create solutions in multiple languages.

kayakane

# Solution:
# The solution is to use a depth first search to find the longest path starting from each cell.
# The solution is optimal because it only needs to search each cell once.

def longest_path(matrix):
    longest = 0
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            longest = max(longest, dfs(matrix, i, j))
    return longest

def dfs(matrix, i, j):
    longest = 0
    for x, y in [(i+1, j), (i, j+1), (i-1, j), (i, j-1), (i-1, j-1), (i+1,j+1), (i-1,j+1), (i+1,j-1)]:
        if 0 <= x < len(matrix) and 0 <= y < len(matrix[0]) and matrix[x][y] == matrix[i][j] + 1:
            longest = max(longest, dfs(matrix, x, y))
    return longest + 1

print(longest_path([[1, 2, 9], [5, 3, 8], [4, 6, 7]]))