Frontend School

Max Reachable Delivery Points

DSA
medium

Max Reachable Delivery Points

Medium
Matrix
BFS
Graph
Traversal

Overview

Delhivery operates a vast network of logistics and delivery services. Optimizing delivery routes and ensuring agents can efficiently reach designated points is crucial for timely deliveries and operational efficiency. This problem simulates a scenario where a delivery agent needs to explore a given area, such as a warehouse or a city block, to identify the maximum number of unique delivery points they can access within a specified time limit, while navigating around obstacles.

What you need to do / Task

Your task is to implement a function that calculates the maximum number of unique delivery points a Delhivery agent can reach starting from a given position within a maximum number of moves.

  1. Traverse the provided grid representing the delivery area.
  2. Identify and count unique 'D' (Delivery) points reachable within maxMoves from the startRow, startCol.
  3. Movement is restricted to 4 directions (up, down, left, right) and cannot pass through '1' (Obstacle) cells.
  4. Each move costs 1 unit.

Input & output

Input:

  • grid: An m x n matrix (2D array) of characters representing the delivery area. Each cell can be:
    • '0': An open path, traversable.
    • '1': An obstacle, non-traversable.
    • 'D': A delivery point, traversable and counts towards reachable delivery points.
  • startRow: An integer representing the starting row index of the agent.
  • startCol: An integer representing the starting column index of the agent.
  • maxMoves: An integer representing the maximum number of moves the agent can make.

Output:

  • An integer representing the total count of unique delivery points reachable within maxMoves.

Clarifications

  • The agent can start on any type of cell ('0', '1', 'D'). If starting on 'D', it counts as one reachable delivery point if maxMoves >= 0. However, they cannot move from an obstacle cell. Assume startRow, startCol will always be a valid, non-obstacle cell.
  • If maxMoves is 0, the agent can only "reach" the starting cell. If it's a 'D', count 1. Otherwise, 0.
  • A delivery point is considered "reached" if the agent steps onto that cell. Multiple visits to the same delivery point only count as one unique point.

Examples

1

Example 1

Input:

grid = [["0","D","0"],["0","1","0"],["D","0","0"]], startRow = 0, startCol = 0, maxMoves = 2

Output:

2

Note:

From (0,0):

  • (0,1) ('D') is reachable in 1 move.
  • (1,0) ('0') is reachable in 1 move.
  • From (1,0), (2,0) ('D') is reachable in 1 more move, totaling 2 moves from (0,0). Unique delivery points (0,1) and (2,0) are both reachable within 2 moves.
2

Example 2

Input:

grid = [["D","0","D"],["0","1","0"],["D","0","D"]], startRow = 0, startCol = 0, maxMoves = 0

Output:

1

Note:

The agent starts at (0,0) which is a 'D' point. With 0 moves, only the starting cell can be reached, thus counting 1 unique delivery point.

3

Example 3

Input:

grid = [["0","0","0"],["0","1","0"],["0","0","0"]], startRow = 0, startCol = 0, maxMoves = 1

Output:

0

Note:

From (0,0), the agent can move to (0,1) or (1,0). Neither of these cells are 'D' points. No 'D' points reachable within 1 move.

Constraints

Constraints & assumptions

  • 1 <= m, n <= 100 (grid dimensions)
  • grid[i][j] will be one of '0', '1', 'D'.
  • 0 <= startRow < m
  • 0 <= startCol < n
  • grid[startRow][startCol] will not be '1'.
  • 0 <= maxMoves <= m * n
  • Time complexity: Aim for O(m * n) or O(m * n * maxMoves) if necessary, but O(m*n) is preferred.
  • Space complexity: Aim for O(m * n).

What interviewers evaluate

  • Correctness of the BFS/graph traversal algorithm for finding reachable nodes.
  • Effective handling of the maxMoves constraint.
  • Accurate tracking and counting of unique delivery points.
  • Optimal time and space complexity for the given constraints.
  • Code readability, structure, and edge case handling.

Loading editor...