dsa · hard
Clinic Supply Run
A courier starts at the top-left room of a clinic laid out as rooms (rows × columns) and must reach the bottom-right room, moving only right or down, collecting supplies in every room entered. Rooms hold an integer stash: positive rooms give that many units, non-positive rooms cost that many (a 0 room is neutral, negative rooms drain).
Arguments
rooms— the clinic stash grid; positive gives, negative drains
The courier must never carry a negative balance. Return the **minimum starting balance** that still allows some right/down route where the balance never dips below zero at any point along it.
Example
rooms = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
The route right-right-down-down (-2,-3,3,1,-5) ends at B - 2 - 3 + 3 + 1 - 5 = B - 6, so that route needs at least 6 up front; every other route dips lower earlier (anything through the -3,-10 corridor needs even more). Checking every route, 6 is the smallest starting balance that never dips negative → 6.
rooms = [[5]] → positive room, no headroom needed → 0.
Constraints
1 <= rooms.length <= 200 1 <= rooms[i].length <= 200 -10^5 <= rooms[i][j] <= 10^5 Hidden tests include near-max size for this bound; a slower-than-intended solution TLEs.
Examples
Example 1
Input: [[-2,-3,3],[-5,-10,1],[10,30,-5]] Expected: 6
Example 2
Input: [[5]] Expected: 0
Example 3
Input: [[0]] Expected: 0