You are given a positive integer hp and two positive 1-indexed integer arrays damage and requirement.
There is a dungeon with n trap rooms numbered from 1 to n. Entering room i reduces your health points by damage[i]. After that reduction, if your remaining health points are at least requirement[i], you earn 1 point for that room.
Let score(j) be the number of points you get if you start with hp health points and enter the rooms j, j + 1, ..., n in this order.
Return the integer score(1) + score(2) + ... + score(n), the sum of scores over all starting rooms.
Note: You cannot skip rooms. You can finish your journey even if your health points become non-positive.
Example 1:
Input: hp = 11, damage = [3,6,7], requirement = [4,2,5]
Output: 3
Explanation:
score(1) = 2, score(2) = 1, score(3) = 0. The total score is 2 + 1 + 0 = 3.
As an example, score(1) = 2 because you get 2 points if you start from room 1.
11 - 3 = 8. You get 1 point because 8 >= 4.8 - 6 = 2. You get 1 point because 2 >= 2.2 - 7 = -5. You do not get any points because -5 < 5.Example 2:
Input: hp = 2, damage = [10000,1], requirement = [1,1]
Output: 1
Explanation:
score(1) = 0, score(2) = 1. The total score is 0 + 1 = 1.
score(1) = 0 because you do not get any points if you start from room 1.
2 - 10000 = -9998. You do not get any points because -9998 < 1.-9998 - 1 = -9999. You do not get any points because -9999 < 1.score(2) = 1 because you get 1 point if you start from room 2.
2 - 1 = 1. You get 1 point because 1 >= 1.
Constraints:
1 <= hp <= 1091 <= n == damage.length == requirement.length <= 1051 <= damage[i], requirement[i] <= 104Problem Overview: You are given an array representing dungeon runs and their score contribution. Each run increases the cumulative score, but you can only count runs while staying within a constraint (such as stamina or run limit). The goal is to quickly compute the total score achievable for different limits without recomputing sums repeatedly.
Approach 1: Brute Force Simulation (O(n^2) time, O(1) space)
The straightforward approach simulates dungeon runs from the beginning for every query or limit. For each scenario, iterate through the array and keep a running total until the constraint is exceeded. While easy to implement, this repeatedly recomputes sums for overlapping prefixes of the array. With many runs or queries, the nested iteration becomes expensive and leads to quadratic time complexity.
Approach 2: Prefix Sum + Binary Search (O(n log n) time, O(n) space)
The efficient solution precomputes a prefix sum array where prefix[i] stores the total score from the first run up to index i. This allows constant-time lookup of any prefix score. Because the cumulative values grow monotonically, you can apply binary search on the prefix array to locate the farthest run that still satisfies the given limit.
For each limit, perform a binary search over the prefix sums to find the largest index where the cumulative value remains valid. Once that index is identified, the answer is simply the prefix sum at that position. This avoids recomputing sums and reduces repeated scanning of the array.
The combination of array traversal for preprocessing and logarithmic searches for each lookup makes this approach scalable. Prefix sums compress repeated work into a single preprocessing step, while binary search quickly identifies the valid range.
Recommended for interviews: The prefix sum + binary search approach is what interviewers expect. Starting with the brute force method shows you understand the direct simulation. Then optimizing with prefix sums and logarithmic search demonstrates algorithmic thinking and familiarity with common patterns used to speed up repeated range calculations.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2) | O(1) | Small input sizes or when implementing a quick baseline solution |
| Prefix Sum + Binary Search | O(n log n) | O(n) | Large inputs or repeated queries where fast prefix range lookup is required |
Total Score of Dungeon Runs | LeetCode 3771 | Weekly Contest 471 • Sanyam IIT Guwahati • 1,906 views views
Watch 5 more video solutions →Practice Total Score of Dungeon Runs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor