Medium

Sequential Grid Path Cover

LAB

Given grid values and a sequence, return true if a 4-directional path can visit cells matching the sequence in order without reusing a cell.

EXAMPLES

Example 1

Input
{
  "grid": [
    [
      1,
      2,
      3
    ],
    [
      4,
      5,
      6
    ]
  ],
  "sequence": [
    1,
    2,
    3,
    6
  ]
}

Output
true

FUNCTION SHAPE

grid: intMatrixsequence: intArray→bool

SOLUTION NOTE

Note we can do something like 0010203000400. Ie. we can interrupt the ascending sequence with 0's. This is not clear from the problem statement.

Few things: notice how we can use a global res variable to terminate our backtracking, and indicate if it is a success or not. Also, if we maintain a visited set in our backtracking, we need to remember to pop it at the end of the function. Other than that, this is just the template. If the neighbour is 0 or the next number in the sequence, this is a valid neighbour and we backtrack on it. We need to maintain prev, and remember to not reset it to 0 because we can have 0's that interrupt the ascending sequence.

Reveal reference solution +

pythonREFERENCE

def findPath(self, grid: List[List[int]], k: int) -> List[List[int]]:
    dirs = [(0,1),(1,0),(-1,0), (0,-1)]
    m, n = len(grid), len(grid[0])

    def isInBounds(i, j):
        return 0 <= i < m and 0 <= j < n

    for i in range(m):
        for j in range(n):
            curr = []
            res = None

            # prev represents the latest non-zero value on the path up to
            # and including the current (i,j) (or 0 if there were no no-zero values)
            def backtrack(i, j, visited, prev):
                nonlocal curr, res
                if res: return
                if (i, j) in visited: return
                visited.add((i, j))

                if len(curr) == m*n-1:
                    res = curr.copy() + [[i, j]]
                    return

                for x, y in dirs:
                    ii, jj = i+x, j+y
                    if isInBounds(ii, jj) and (grid[ii][jj] == 0 or grid[ii][jj] == prev+1):
                        curr.append([i, j])
                        backtrack(ii, jj, visited, prev+(grid[ii][jj] == prev+1))
                        curr.pop()

                visited.discard((i, j))  # need this

            backtrack(i, j, set(), grid[i][j])
            if res: return res

    return []

TimeO(m*n * (m*n)!)

SpaceO(m*n)

Open on LeetCode ↗