Frontend School

Maximum Profit Delivery Route

DSA
medium

Maximum Profit Delivery Route

Medium
Dynamic Programming
2D Array
Grid

Overview

Shiprocket is constantly optimizing its delivery operations to enhance efficiency and profitability. Imagine a city represented as a grid, where each cell (i, j) corresponds to a potential package pickup location with an associated profit. A delivery agent needs to navigate this grid, starting from the top-left corner and reaching the bottom-right corner, collecting packages along their path to maximize total profit.

What you need to do / Task

Your task is to implement a function getMaxProfit that calculates the maximum total profit a delivery agent can collect. The agent starts at the top-left corner (0, 0) and must reach the bottom-right corner (M-1, N-1). At each step, the agent can only move either right or down. Some cells might be blocked (obstacles), meaning the agent cannot enter or pass through them.

Input & output

  • Input:
    • profits: A 2D array (matrix) of integers M x N. profits[i][j] represents the profit obtainable from cell (i, j).
      • If profits[i][j] >= 0, it's a valid location with the specified profit.
      • If profits[i][j] == -1, it signifies an obstacle, and the agent cannot enter this cell.
  • Output:
    • An integer representing the maximum total profit that can be collected from (0, 0) to (M-1, N-1).
    • If (0, 0) or (M-1, N-1) is an obstacle, or if no valid path exists to the destination, return -1.

Clarifications

  • The agent must pick up the package (collect profit) from every cell they visit, including the start and end cells.
  • If the start cell (0, 0) or the end cell (M-1, N-1) is marked as an obstacle (-1), no valid path can exist, and the function should return -1.
  • The grid will always be non-empty (M >= 1, N >= 1).
  • A path is considered valid only if all cells along the path (including start and end) are not obstacles.

Examples

1

Example 1

Input:

profits = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

Output:

29

Note:

The path (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) yields 1 + 4 + 7 + 8 + 9 = 29, which is the maximum profit.

2

Example 2

Input:

profits = [[1, 10, -1], [1, -1, 5], [1, 1, 100]]

Output:

104

Note:

Cells (0,2) and (1,1) are obstacles. The only valid path is (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2), yielding 1 + 1 + 1 + 1 + 100 = 104.

3

Example 3

Input:

profits = [[1, -1], [-1, 10]]

Output:

-1

Note:

Cells (0,1) and (1,0) are obstacles, making it impossible to reach (1,1) from (0,0). Thus, no valid path exists.

4

Example 4

Input:

profits = [[-1]]

Output:

-1

Note:

The start cell (0,0) is an obstacle, so no path is possible.

Constraints

Constraints & assumptions

  • 1 <= M, N <= 200 (where M is the number of rows, N is the number of columns)
  • -1 <= profits[i][j] <= 1000
  • Time complexity: Aim for O(M * N).
  • Space complexity: Aim for O(M * N) or O(N) (optimized).
  • The solution should correctly handle cases where no path exists.

Out of scope

  • Diagonal movements.
  • Moving up or left.
  • Multiple agents or concurrent deliveries.
  • Finding all possible paths or the shortest path (only maximum profit).

What interviewers evaluate

  • Correctly identifies and applies a 2D Dynamic Programming approach.
  • Handles base cases and edge conditions, especially obstacles and unreachable paths.
  • Demonstrates efficient state transitions for maximum profit.
  • Analyzes and optimizes time and space complexity.

Loading editor...