Minimum Starting Energy
Problem
A rover crosses a hazard field field. Entering cell (r, c) changes its energy by field[r][c]: negative values drain energy, positive values recharge it. The rover starts at the top-left cell (whose value applies immediately), must reach the bottom-right cell (whose value also applies) and moves only right or down.
The rover's energy must be at least 1 at every moment, including right after the first and the last cell. Return the smallest whole-number starting energy that makes the trip possible.
Example 1
- Input:
- field = [[-3, 4, -6], [-2, -8, 5], [10, -1, -4]]
- Output:
- 6
Start with 6 and go down, down, right, right: 6 → 3 → 1 → 11 → 10 → 6. Every value stays at least 1. Starting with 5, every route drops to 0 or below somewhere.
Example 2
- Input:
- field = [[5]]
- Output:
- 1
The rover needs at least 1 energy to start with, even though the only cell recharges it.
Constraints
- 1 ≤ field.length, field[0].length ≤ 200
- -1000 ≤ field[r][c] ≤ 1000
Hint
Show the first hint
Try a forward DP that tracks the best remaining energy at each cell. Why does it fail? A path can have a high final energy but a deep dip in the middle.
Walkthrough
How to approach it
01Clarify before coding
- Does the start cell's value apply? Yes, before the rover's first check, so a negative start cell already raises the requirement.
- Must the energy be strictly positive at the end too? Yes, at least 1 after the last cell.
- Is the starting energy a whole number? Yes, and the minimum possible answer is 1.
02Brute force
Enumerate every right/down path, compute the lowest prefix sum along it and take 1 - lowest (at least 1); return the minimum over all paths. Or binary search the starting energy and test feasibility with a forward DP.
Cost: Path enumeration is exponential. The binary search version costs O(m · n · log(range)), workable but it hides the clean idea.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.