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 Take-home Project rounds at MathWorks.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at MathWorks during technical interviews.

Find shortest path using BFS | MathWorks Coding Question

Find shortest path using BFS

Company: MathWorks

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Take-home Project

Given an m×n grid grid where grid[r][c] = 0 represents an empty cell and 1 represents a wall, a start cell (sr, sc), and a target cell (tr, tc), you may move one step at a time in four directions (up, down, left, right) into empty cells only. Return the length of the shortest path from start to target or -1 if no path exists. Describe the algorithm and its time/space complexity, and implement it in C++/Java/JavaScript.

Quick Answer: This question evaluates a candidate's proficiency with graph traversal algorithms—particularly breadth-first search—and the ability to model grid-based shortest-path problems while reasoning about time and space complexity.

Given an m×n grid `grid` where `grid[r][c] = 0` represents an empty cell and `1` represents a wall, a start cell `(sr, sc)`, and a target cell `(tr, tc)`, you may move one step at a time in four directions (up, down, left, right) into empty cells only. Return the length of the shortest path (number of steps) from start to target, or `-1` if no path exists. If the start and target are the same cell, the answer is `0`. Breadth-first search explores the grid level by level, so the first time the target is dequeued (or reached) it is guaranteed to be via a shortest path.

Constraints

1 <= m, n <= 1000
grid[r][c] is 0 (empty) or 1 (wall)
0 <= sr, tr < m and 0 <= sc, tc < n
Movement is restricted to the four orthogonal directions (no diagonals)
You may only step into empty (0) cells

Examples

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

Expected Output: 4

Explanation: From (0,0) to (2,2) around the central wall: e.g. right, right, down, down = 4 steps.

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

Expected Output: -1

Explanation: The target (1,1) is diagonally adjacent but walls at (0,1) and (1,0) block every orthogonal route, so it is unreachable.

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

Expected Output: 0

Explanation: Start and target are the same single cell, so the path length is 0.

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

Expected Output: 8

Explanation: The middle row is almost entirely walls; the only gap is at column 3, forcing a detour across the top row, down the right edge, and back across the bottom row = 8 steps.

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

Expected Output: 2

Explanation: Open 2x2 grid: down then right (or right then down) reaches the opposite corner in 2 steps.

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

Expected Output: -1

Explanation: The start cell (0,0) is itself a wall, so there is no valid path.

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

Expected Output: 6

Explanation: Start at (2,0), target at (0,0); the wall row forces a detour right along the bottom, up the right column, and back left along the top = 6 steps.

Hints

BFS, not DFS: BFS expands the grid in rings of increasing distance, so the first time you reach the target you have found the shortest path. DFS would not give you that guarantee.
Track distance by storing (row, col, dist) in the queue, or process the queue one level at a time and increment a step counter per level.
Mark a cell visited the moment you enqueue it (not when you dequeue it) to avoid pushing the same cell multiple times.
Handle the corner cases up front: start == target returns 0, and a start or target that sits on a wall returns -1.

Quick Overview

This question evaluates a candidate's proficiency with graph traversal algorithms—particularly breadth-first search—and the ability to model grid-based shortest-path problems while reasoning about time and space complexity.