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 position in the array.
Example input:
[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]
Example output:
3 (1 -> 2 -> 3 or 5 -> 6 -> 7)

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.

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

def dfs(arr, i, j):
    if i < 0 or i >= len(arr) or j < 0 or j >= len(arr[0]):
        return 0
    if arr[i][j] == -1:
        return 0
    curr = arr[i][j]
    arr[i][j] = -1
    path = 1 + max(dfs(arr, i + 1, j), dfs(arr, i - 1, j), dfs(arr, i, j + 1), dfs(arr, i, j - 1))
    arr[i][j] = curr return path

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