How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Amazon during technical interviews.

Find shortest path in a grid with obstacles

Company: Amazon

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a 2D grid of size `m x n` representing a maze. Each cell in the grid is either empty (0) or blocked (1). You are also given two coordinates: - `start = (sx, sy)` - `end = (ex, ey)` You can move from a cell to its 4-directional neighbors (up, down, left, right), but you **cannot** move into or through blocked cells, and you must remain inside the grid. Return the length of the shortest path (in number of steps) from `start` to `end`. If there is no valid path, return `-1`. Assumptions and details: - `0 <= sx, ex < m` - `0 <= sy, ey < n` - `grid[sx][sy] == 0` and `grid[ex][ey] == 0` - `1 <= m, n <= 10^3` - Time complexity should be efficient for the upper bounds (you may consider BFS or DFS-based approaches). **Input format (for reference):** - `m, n` (integers) - `grid` as an `m x n` matrix of 0s and 1s - `start` coordinate - `end` coordinate **Output:** - An integer representing the length of the shortest path, or `-1` if unreachable.

Quick Answer: This question evaluates understanding of pathfinding in grid-based environments, graph traversal concepts, and algorithmic complexity when navigating obstacles and boundary constraints in an unweighted 2D search space.

You are given a 2D grid of size `m x n` representing a maze. Each cell is either empty (`0`) or blocked (`1`). You are also given two coordinates: - `start = (sx, sy)` - `end = (ex, ey)` From a cell you may move to its 4-directional neighbors (up, down, left, right). You **cannot** move into or through a blocked cell, and you must stay inside the grid. Return the length of the shortest path (in number of steps) from `start` to `end`. If no valid path exists, return `-1`. A path's length is the number of moves; the path from a cell to itself has length `0`. **Example** ``` grid = [[0,0,0], [0,1,0], [0,0,0]] start = (0,0), end = (2,2) -> 4 ``` One shortest route is (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2), which is 4 steps.

Constraints

1 <= m, n <= 10^3
Each grid cell is 0 (empty) or 1 (blocked)
0 <= sx, ex < m and 0 <= sy, ey < n
grid[sx][sy] == 0 and grid[ex][ey] == 0
Movement is 4-directional only (no diagonals)

Examples

Input: ([[0,0,0],[0,1,0],[0,0,0]], (0,0), (2,2))

Expected Output: 4

Explanation: Go around the central obstacle: (0,0)->(1,0)->(2,0)->(2,1)->(2,2) = 4 steps.

Input: ([[0,1],[1,0]], (0,0), (1,1))

Expected Output: -1

Explanation: The empty cells (0,0) and (1,1) are diagonal; the two cells between them are blocked, so no 4-directional path exists.

Input: ([[0]], (0,0), (0,0))

Expected Output: 0

Explanation: Start equals end on a single empty cell; zero moves are needed.

Input: ([[0,0,0,0],[1,1,1,0],[0,0,0,0],[0,1,1,1],[0,0,0,0]], (0,0), (4,3))

Expected Output: 13

Explanation: Walls on rows 1 and 3 force a serpentine detour through column 3 then back across row 2 and down column 0: 13 steps is the only feasible shortest route.

Input: ([[0,0],[0,0]], (0,0), (0,1))

Expected Output: 1

Explanation: Adjacent empty cells reached in a single move.

Input: ([[0,1,0],[0,1,0],[0,0,0]], (0,0), (0,2))

Expected Output: 6

Explanation: A column of obstacles separates the two top corners; the path must descend to the open bottom row and come back up: (0,0)->(1,0)->(2,0)->(2,1)->(2,2)->(1,2)->(0,2) = 6 steps.

Hints

Shortest path in an unweighted grid where every move costs 1 is the textbook case for breadth-first search (BFS), not DFS — BFS visits cells in increasing distance order, so the first time you reach the target you have the minimum number of steps.
Track a visited matrix so each cell is enqueued at most once; this keeps the whole traversal O(m*n) even for the 1000x1000 upper bound.
Handle the degenerate case where start == end (answer 0) before the search, and remember to return -1 when the queue empties without reaching the target.

Quick Overview

This question evaluates understanding of pathfinding in grid-based environments, graph traversal concepts, and algorithmic complexity when navigating obstacles and boundary constraints in an unweighted 2D search space.