Problem

Given a 2D array of integers, find the length of the longest path of consecutive numbers that can be formed in the array. The path can start and end at any location in the array.
Example input:
[[3,4,5],
 [2,3,6],
 [1,2,3]]
Example output:
6

Solution

# Solution:
# The solution is to use a DFS algorithm to find the longest path.
# The algorithm is optimal because it only needs to traverse the array once.
# The time complexity is O(n) where n is the number of elements in the array.
# The space complexity is O(n) where n is the number of elements in the array.

def longest_path(arr):
    if not arr:
        return 0
    longest = 0
    visited = set()
    for i in range(len(arr)):
        for j in range(len(arr[0])):
            longest = max(longest, dfs(arr, i, j, visited))
    return longest

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

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