Find longest Snake sequence in a given matrix

Problem

Given a 2D integer matrix, find a snake sequence with maximum length. A snake sequence can move only right or down; a move from cell a to adjacent cell b is allowed only if abs(a - b) == 1 (difference of exactly 1).

Return one such maximum-length sequence of values (reading sequence in traversal order). If multiple sequences have the same maximum length, any one is acceptable. If the matrix is empty, return an empty sequence.

Examples

Example 1

Input: mat = 
[
 [9, 6, 5, 2],
 [8, 7, 6, 5],
 [7, 6, 5, 4],
 [6, 5, 4, 3]
]
Output: 7

One valid longest snake path (values): [9, 8, 7, 6, 5, 4, 3]

Solution

We use dynamic programming (bottom-up). For every cell (i,j) we compute dp[i][j] — the length of the longest snake sequence that ends at (i,j) when moves are restricted to coming from the top or left. While filling dp we track the cell with the global maximum length, then reconstruct the path by stepping to a neighbor with dp == current-1 whose value differs by one.

Method 1 — Dynamic Programming (Bottom-up) with path reconstruction

Intuition

If a valid snake sequence ends at cell (i,j), its previous cell must be either (i-1,j) (from above) or (i,j-1) (from left). So the best length ending at (i,j) is 1 + max(dp[i-1][j], dp[i][j-1]) for those neighbors where abs(mat[neighbor] - mat[i][j]) == 1. Fill dp row-major and track the maximum cell.

Approach

1. Handle edge cases: if mat is empty return [].
2. Let m = rows, n = cols. Create dp (m×n) filled with 1 (each cell by itself is length 1).
3. Iterate i from 0..m-1, j from 0..n-1:
   • If i > 0 and abs(mat[i][j] - mat[i-1][j]) == 1, set dp[i][j] = max(dp[i][j], dp[i-1][j] + 1).
   • If j > 0 and abs(mat[i][j] - mat[i][j-1]) == 1, set dp[i][j] = max(dp[i][j], dp[i][j-1] + 1).
   • Track maxLen and coordinates (r,c) of the cell with maximum dp.
4. Reconstruct path starting from (r,c): while dp[r][c] > 0, append mat[r][c] to path and move to a neighbor (r-1,c) or (r,c-1) with dp == dp[r][c] - 1 and abs(mat[neighbor] - mat[r][c]) == 1 (prefer up if both possible). Stop when no predecessor found or dp drops to 1. Reverse path and return it.

Edge cases covered: empty matrix, single row/column matrices, multiple paths with same length (we return any).

Code

C++

class Solution {
 public:
  vector<int> longestSnakeSequence(vector<vector<int>>& mat) {
    int m = mat.size();
    if (m == 0) return {};
    int n = mat[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 1));
    int maxLen = 1, r = 0, c = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i > 0 && abs(mat[i][j] - mat[i-1][j]) == 1) {
          dp[i][j] = max(dp[i][j], dp[i-1][j] + 1);
        }
        if (j > 0 && abs(mat[i][j] - mat[i][j-1]) == 1) {
          dp[i][j] = max(dp[i][j], dp[i][j-1] + 1);
        }
        if (dp[i][j] > maxLen) { maxLen = dp[i][j]; r = i; c = j; }
      }
    }
    vector<int> path;
    while (maxLen > 0) {
      path.push_back(mat[r][c]);
      if (r > 0 && dp[r-1][c] == dp[r][c] - 1 && abs(mat[r][c] - mat[r-1][c]) == 1) {
        --r;
      } else if (c > 0 && dp[r][c-1] == dp[r][c] - 1 && abs(mat[r][c] - mat[r][c-1]) == 1) {
        --c;
      } else {
        break;
      }
      --maxLen;
    }
    reverse(path.begin(), path.end());
    return path;
  }
};

Go

package main

func longestSnakeSequence(mat [][]int) []int {
    m := len(mat)
    if m == 0 { return []int{} }
    n := len(mat[0])
    dp := make([][]int, m)
    for i := range dp { dp[i] = make([]int, n); for j := range dp[i] { dp[i][j] = 1 } }
    maxLen, r, c := 1, 0, 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if i > 0 && abs(mat[i][j]-mat[i-1][j]) == 1 {
                if dp[i-1][j]+1 > dp[i][j] { dp[i][j] = dp[i-1][j] + 1 }
            }
            if j > 0 && abs(mat[i][j]-mat[i][j-1]) == 1 {
                if dp[i][j-1]+1 > dp[i][j] { dp[i][j] = dp[i][j-1] + 1 }
            }
            if dp[i][j] > maxLen { maxLen, r, c = dp[i][j], i, j }
        }
    }
    path := make([]int, 0)
    for maxLen > 0 {
        path = append(path, mat[r][c])
        if r > 0 && dp[r-1][c] == dp[r][c]-1 && abs(mat[r][c]-mat[r-1][c]) == 1 { r-- }
        else if c > 0 && dp[r][c-1] == dp[r][c]-1 && abs(mat[r][c]-mat[r][c-1]) == 1 { c-- }
        else { break }
        maxLen--
    }
    // reverse
    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 { path[i], path[j] = path[j], path[i] }
    return path
}

func abs(x int) int { if x < 0 { return -x }; return x }

Java

import java.util.*;

class Solution {
  public List<Integer> longestSnakeSequence(int[][] mat) {
    int m = mat.length;
    if (m == 0) return Collections.emptyList();
    int n = mat[0].length;
    int[][] dp = new int[m][n];
    for (int i = 0; i < m; ++i) Arrays.fill(dp[i], 1);
    int maxLen = 1, r = 0, c = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i > 0 && Math.abs(mat[i][j] - mat[i-1][j]) == 1) dp[i][j] = Math.max(dp[i][j], dp[i-1][j] + 1);
        if (j > 0 && Math.abs(mat[i][j] - mat[i][j-1]) == 1) dp[i][j] = Math.max(dp[i][j], dp[i][j-1] + 1);
        if (dp[i][j] > maxLen) { maxLen = dp[i][j]; r = i; c = j; }
      }
    }
    List<Integer> path = new ArrayList<>();
    while (maxLen > 0) {
      path.add(mat[r][c]);
      if (r > 0 && dp[r-1][c] == dp[r][c] - 1 && Math.abs(mat[r][c] - mat[r-1][c]) == 1) r--;
      else if (c > 0 && dp[r][c-1] == dp[r][c] - 1 && Math.abs(mat[r][c] - mat[r][c-1]) == 1) c--;
      else break;
      maxLen--;
    }
    Collections.reverse(path);
    return path;
  }
}

Python

from typing import List

class Solution:
    def longestSnakeSequence(self, mat: List[List[int]]) -> List[int]:
        if not mat: return []
        m, n = len(mat), len(mat[0])
        dp = [[1]*n for _ in range(m)]
        max_len, r, c = 1, 0, 0
        for i in range(m):
            for j in range(n):
                if i > 0 and abs(mat[i][j] - mat[i-1][j]) == 1:
                    dp[i][j] = max(dp[i][j], dp[i-1][j] + 1)
                if j > 0 and abs(mat[i][j] - mat[i][j-1]) == 1:
                    dp[i][j] = max(dp[i][j], dp[i][j-1] + 1)
                if dp[i][j] > max_len:
                    max_len, r, c = dp[i][j], i, j
        path = []
        while max_len > 0:
            path.append(mat[r][c])
            if r > 0 and dp[r-1][c] == dp[r][c] - 1 and abs(mat[r][c] - mat[r-1][c]) == 1:
                r -= 1
            elif c > 0 and dp[r][c-1] == dp[r][c] - 1 and abs(mat[r][c] - mat[r][c-1]) == 1:
                c -= 1
            else:
                break
            max_len -= 1
        return path[::-1]

Complexity

• ⏰ Time complexity: O(m * n) — we visit each cell once and perform O(1) work (constant neighbor checks and updates).
• 🧺 Space complexity: O(m * n) — for the dp table; plus O(k) for the returned path of length k (≤ m*n).