How should I practice Find and Reconstruct a Binary-Matrix Path?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Meta phone screen problems in FastPrep.

Is Find and Reconstruct a Binary-Matrix Path associated with Meta?

FastPrep tags this as a Meta phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Find and Reconstruct a Binary-Matrix Path

Learn this problem

● Medium

MetaFULLTIMEPHONE SCREEN

See Meta hiring insights

Problem statement

You are given a non-empty rectangular binary matrix grid. A cell containing 0 is passable and a cell containing 1 is blocked.

Return a shortest path from the top-left cell [0,0] to the bottom-right cell [rows-1,cols-1]. Consecutive cells may move one step up, left, right, or down, and the path must contain only passable cells.

The returned array contains the coordinates in travel order, including both endpoints. If no path exists, return an empty array. If several shortest paths exist, return the lexicographically smallest coordinate sequence, comparing a coordinate by row and then column.

Function

shortestBinaryMatrixPath(grid: int[][]) → int[][]

Examples

Example 1

grid = [[0,0,1],[1,0,0],[1,1,0]]return = [[0,0],[0,1],[1,1],[1,2],[2,2]]

The displayed route is the only shortest path through passable cells.

Example 2

grid = [[0,0],[0,0]]return = [[0,0],[0,1],[1,1]]

Both two-step routes are shortest. Moving right first produces the lexicographically smaller coordinate sequence.

Example 3

grid = [[0,1],[1,0]]return = []

The two passable endpoints are disconnected by blocked cells.

Constraints

grid is non-empty and rectangular.
Every cell is either 0 or 1.
Coordinate sequences are compared lexicographically by [row,column].