Frontend School

Shortest Service Path

DSA
easy

Shortest Service Path

Easy
Graph
Shortest Path
BFS
Matrix

Overview

At Urban Company, efficient service delivery is paramount. Our service technicians navigate various locations to reach customers. To optimize their routes and ensure timely service, we need to calculate the quickest way to a customer's location, especially when some areas are temporarily inaccessible due to maintenance or other reasons. This problem focuses on finding the minimum number of steps a technician needs to take to reach a customer.

What you need to do / Task

You are tasked with implementing a function that calculates the minimum number of moves (steps) required for a service technician to travel from their starting point ('S') to a customer's service location ('T') within a given grid. The technician can move horizontally or vertically (up, down, left, right) to adjacent cells. They cannot move into blocked cells ('X') or outside the grid boundaries.

Your function should:

  1. Find the shortest path in terms of the number of moves.
  2. Return the minimum number of moves.
  3. Return -1 if the target location 'T' is unreachable from 'S'.

Input & Output

The function shortestServicePath takes one argument:

  • grid: A m x n 2D array of characters (string[][]) representing the service area.
    • 'S' denotes the technician's starting position.
    • 'T' denotes the customer's target service location.
    • '.' denotes an open path cell where the technician can move.
    • 'X' denotes a blocked area where the technician cannot move.

The function should return an integer:

  • The minimum number of moves to reach 'T' from 'S'.
  • -1 if 'T' is unreachable from 'S'.

Clarifications

  • Movement is restricted to 4 directions: up, down, left, and right to adjacent cells. Diagonal moves are not allowed.
  • Each move to an adjacent open cell counts as one step.
  • The 'S' and 'T' characters will always be present exactly once in the grid and will be within the grid boundaries.
  • The technician starts at 'S' and needs to reach 'T'. The first move from 'S' to an adjacent cell counts as 1 step.

Examples

1

Example 1

Input:

grid = [["S", ".", "."], [".", "X", "."], [".", ".", "T"]]

Output:

4

Note:

Starting at (0,0), a possible shortest path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2), taking 4 moves.

2

Example 2

Input:

grid = [["S", "X", "."], ["X", "X", "."], [".", "X", "T"]]

Output:

-1

Note:

The starting point 'S' at (0,0) is completely blocked by 'X' cells, making 'T' at (2,2) unreachable.

3

Example 3

Input:

grid = [["S", "T", "."], [".", ".", "."]]

Output:

1

Note:

The target 'T' is directly adjacent to 'S'. One move from (0,0) to (0,1) reaches the target.

4

Example 4

Input:

grid = [["S", ".", "."], ["X", ".", "X"], [".", ".", "T"]]

Output:

5

Note:

Starting at (0,0), a possible shortest path is (0,0) -> (0,1) -> (0,2) -> (1,1) -> (2,1) -> (2,2), taking 5 moves, detouring around 'X' obstacles.

Constraints

Constraints & assumptions

  • 1 <= m, n <= 100 (where m is the number of rows and n is the number of columns in the grid).
  • grid[i][j] will be one of 'S', 'T', '.', or 'X'.
  • Exactly one 'S' and exactly one 'T' will be present in the grid.
  • The technician cannot move into cells marked 'X' or outside the grid boundaries.

What interviewers evaluate

  • Algorithmic Correctness: Correct application of an appropriate graph traversal algorithm (e.g., BFS) to find the shortest path in an unweighted grid.
  • Edge Case Handling: Ability to correctly handle scenarios like an unreachable target, a direct path, or a path around obstacles.
  • Time and Space Complexity: Understanding and optimizing the solution's performance characteristics, typically O(m*n) for both.
  • Code Quality: Writing clean, readable, and well-structured code with appropriate variable names and comments where necessary.

Loading editor...