Minimum cost to reach the last station with chocolates
Filed under Amazon
Free read 3 of 3Understand movement mechanics: moving from i to i+1 changes our inventory by A[i] - A[i+1].
The question
Given an array A representing chocolates at each station and a cost P to buy a chocolate, find the minimum cost to reach the last station such that the chocolate count never drops below zero at any step.
Constraints
- 1 <= A.length <= 10^5
- 0 <= A[i] <= 1000
- Cost P >= 0
Examples
- Input
- A = [3, 2, 5], P = 2
- Output
- 2
- Why
- At station 0 we have 3, moving to station 1 loses 1 chocolate. Buying 1 chocolate at station 1 costs 2 to ensure we never drop below zero.
Approach
Understand movement mechanics: moving from i to i+1 changes our inventory by A[i] - A[i+1].
Simulate every possible buying strategy at each step using recursion, leading to exponential time complexity.
Iterate through the stations while keeping track of current chocolates. If the inventory drops below zero, buy the deficit using cost P and reset inventory to zero.
Array of length 1, zero cost, and strictly decreasing station values.
Tips
- What they are testing: Test cases where initial chocolates are sufficient vs. cases requiring continuous purchases.
- Common mistake: Failing to maintain a running balance and greedily buying only at the exact point where balance drops below zero.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.