Frontend School

Zepto Route Optimization with Express Lanes

DSA
medium

Zepto Route Optimization with Express Lanes

Medium
Dynamic Programming
1D DP

Overview

Zepto, committed to rapid delivery and driver well-being, is optimizing its last-mile delivery routes. Each potential delivery zone along a route offers a certain profit. However, to manage driver fatigue and ensure timely deliveries, there are specific rules about which zones can be visited consecutively. Your task is to help Zepto maximize its total profit by strategically selecting delivery zones.

What you need to do / Task

Implement the function maxExpressLaneProfit that takes an array of profits for each delivery zone and an expressBonus value. Your function should return the maximum total profit achievable following these rules:

  1. A delivery cannot be made at two immediately adjacent zones (e.g., if zone i is visited, zone i+1 cannot be visited).
  2. An expressBonus is earned for a delivery at zone i if the previous delivery was exactly at zone i-2 (i.e., zone i-1 was skipped). This bonus is added to the profit of zone i. If the previous delivery was at zone i-3 or earlier, or if i-2 was skipped, no expressBonus is earned for zone i from that specific pattern.

Input & output

  • profits: An array of numbers profits[i] representing the base profit for making a delivery at zone i.
  • expressBonus: A number representing the additional bonus earned for specific express lane usage.
  • Returns: A number, the maximum total profit achievable.

Clarifications

  • An empty profits array should result in 0 profit.
  • profits can contain negative values, indicating a cost rather than a profit.
  • expressBonus will always be a non-negative integer.

Examples

1

Example 1

Input:

profits = [10, 20, 30, 40], expressBonus = 5

Output:

65

Note:

The optimal path is to take zones at index 1 and 3. Taking zone 1 yields 20. Skipping zone 2. Taking zone 3 yields 40. Since zone 1 was the previous delivery and (3 - 2 = 1), zone 3 receives an express bonus of 5. Total profit = 20 + (40 + 5) = 65.

2

Example 2

Input:

profits = [5, 1, 5, 1, 5], expressBonus = 10

Output:

35

Note:

The optimal path is to take zones at indices 0, 2, and 4. Taking zone 0 yields 5. Skipping zone 1. Taking zone 2 yields 5, and gets a bonus of 10 (since 2-2=0, and zone 0 was taken). Skipping zone 3. Taking zone 4 yields 5, and gets a bonus of 10 (since 4-2=2, and zone 2 was taken). Total profit = 5 + (5+10) + (5+10) = 35.

3

Example 3

Input:

profits = [1, 2, 3], expressBonus = 10

Output:

14

Note:

The optimal path is to take zones at index 0 and 2. Taking zone 0 yields 1. Skipping zone 1. Taking zone 2 yields 3, and gets a bonus of 10 (since 2-2=0, and zone 0 was taken). Total profit = 1 + (3 + 10) = 14.

Constraints

Constraints & assumptions

  • 1 <= profits.length <= 10^5
  • -1000 <= profits[i] <= 1000
  • 0 <= expressBonus <= 500
  • Time complexity: O(N)
  • Space complexity: O(N) (can be optimized to O(1) for DP)

What interviewers evaluate

  • Correct application of Dynamic Programming principles to solve the problem.
  • Ability to correctly define DP states and transitions, handling edge cases.
  • Optimized time and space complexity.
  • Clean, readable, and well-structured code.

Loading editor...