Shortest Land Path
Google● MediumNEW GRADFULLTIMEPHONE SCREENProblem statement
Given a square binary grid, find a shortest path from start to target using only land. A cell containing 0 is land; a cell containing 1 is water.
Both endpoint arrays are zero-based coordinates [row, column]. A move travels one cell up, down, left or right, stays inside the grid, and never enters water. Each move has equal cost.
Return the path as an ordered array of coordinates, including the start and target. Minimize the number of moves. If several shortest paths exist, return the lexicographically smallest coordinate sequence: compare the first differing coordinates by row, then column.
Examples
Example 1
grid = [[0,0,0],[1,1,0],[0,0,0]]start = [0,0]target = [2,0]return = [[0,0],[0,1],[0,2],[1,2],[2,2],[2,1],[2,0]]The only land route follows the top row, descends along column 2, then moves left along the bottom row. It uses 6 moves and includes both endpoints.
Unlock this recently reported problem
FastPrep Pro gives you full access to interview problems reported within the last week.
- Full problem statement and constraints
- 2 more worked examples, explained
- Guided hints and editorial
- Run your code on real test cases
$99 billed yearly — or $19 month-to-month. Cancel anytime.