LeetCode 3771 - Total Score of Dungeon Runs

The problem describes a dungeon with n rooms, where entering room i reduces your health points by damage[i]. After taking this damage, if your remaining health is at least requirement[i], you earn 1 point for that room.

leetcodemediumarraybinary-searchprefix-sum

LeetCode Problem 3771

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Prefix Sum

Solution

Problem Understanding

The problem describes a dungeon with n rooms, where entering room i reduces your health points by damage[i]. After taking this damage, if your remaining health is at least requirement[i], you earn 1 point for that room. You can start your dungeon run at any room j (1-indexed) and proceed through the rest of the rooms in order. The function score(j) counts the points you earn when starting at room j. The goal is to calculate the sum of scores starting at every room: score(1) + score(2) + ... + score(n).

The input consists of a positive integer hp representing your initial health points, and two 1-indexed arrays damage and requirement of equal length n. The constraints guarantee that 1 <= hp <= 10^9 and 1 <= n <= 10^5, which implies that a naive O(n^2) approach is too slow. Each damage[i] and requirement[i] is bounded by 10^4, so individual room calculations are manageable but must be done efficiently.

Important edge cases include very large damage values relative to hp, small hp, and starting from the last room, which may yield 0 points if hp < damage[n].

Approaches

The brute-force approach is straightforward: simulate each starting room j by iterating from room j to room n, subtracting damage from hp, and checking if the remaining health meets the requirement. While correct, this leads to O(n^2) time complexity, which is infeasible for n = 10^5.

The optimal approach relies on the observation that the damage accumulates cumulatively. If we precompute a prefix sum of damages, the remaining health when entering room i starting from room j is simply hp - (damage[j] + ... + damage[i]). Using prefix sums, we can calculate this in constant time. Furthermore, the problem reduces to counting the number of rooms where hp - cumulative_damage >= requirement[i]. Because we process rooms in order, a binary search can be applied on cumulative sums for each starting room to find the last room that yields a point. This reduces time complexity to O(n log n).

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Simulate starting at each room and sum scores
Optimal O(n log n) O(n) Use prefix sums and binary search to count points efficiently

Algorithm Walkthrough

  1. Compute the prefix sum array of damages, prefix[i] = damage[1] + ... + damage[i], with prefix[0] = 0. This allows fast calculation of total damage from any starting room to any room in O(1).
  2. Initialize a variable total_score = 0.
  3. Iterate over each starting room j from 1 to n.
  4. For each starting room j, perform a binary search to find the farthest room k such that your remaining health after cumulative damage from j to k is at least requirement[k]. The condition is hp - (prefix[k] - prefix[j-1]) >= requirement[k].
  5. The number of points for starting at room j is (k - j + 1) if such k exists; otherwise it is 0.
  6. Add the points to total_score.
  7. Return total_score.

Why it works: The prefix sum ensures that we can compute the remaining health after any sequence of rooms in O(1). Binary search ensures that for each starting room, we efficiently find the maximum stretch of rooms yielding points without iterating linearly.

Python Solution

from typing import List

class Solution:
    def totalScore(self, hp: int, damage: List[int], requirement: List[int]) -> int:
        n = len(damage)
        prefix = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] + damage[i - 1]
        
        total_score = 0
        for start in range(1, n + 1):
            low, high = start, n
            last_valid = start - 1
            while low <= high:
                mid = (low + high) // 2
                remaining_hp = hp - (prefix[mid] - prefix[start - 1])
                if remaining_hp >= requirement[mid - 1]:
                    last_valid = mid
                    low = mid + 1
                else:
                    high = mid - 1
            total_score += last_valid - start + 1
        return total_score

The code first computes prefix sums of the damage array for O(1) range damage calculation. Then, for each starting room, it applies binary search to find the farthest room where health meets the requirement. total_score accumulates all valid points across starting rooms.

Go Solution

func totalScore(hp int, damage []int, requirement []int) int64 {
    n := len(damage)
    prefix := make([]int, n+1)
    for i := 1; i <= n; i++ {
        prefix[i] = prefix[i-1] + damage[i-1]
    }

    var totalScore int64
    for start := 1; start <= n; start++ {
        low, high := start, n
        lastValid := start - 1
        for low <= high {
            mid := (low + high) / 2
            remainingHp := hp - (prefix[mid] - prefix[start-1])
            if remainingHp >= requirement[mid-1] {
                lastValid = mid
                low = mid + 1
            } else {
                high = mid - 1
            }
        }
        totalScore += int64(lastValid - start + 1)
    }
    return totalScore
}

The Go implementation mirrors the Python logic, using slices for prefix sums and int64 for totalScore to avoid integer overflow in large sums.

Worked Examples

Example 1: hp = 11, damage = [3,6,7], requirement = [4,2,5]

Start Room Prefix Damage Range Remaining HP Calculation Points Earned
1 3, 3+6=9, 9+7=16 11-3=8 >= 4, 8-6=2 >=2, 2-7=-5 <5 2
2 6, 6+7=13 11-6=5 >=2, 5-7=-2 <5 1
3 7 11-7=4 <5 0

Total score = 2 + 1 + 0 = 3

Example 2: hp = 2, damage = [10000,1], requirement = [1,1]

Start Room Prefix Damage Range Remaining HP Calculation Points Earned
1 10000, 10001 2-10000=-9998<1, -9998-1=-9999<1 0
2 1 2-1=1>=1 1

Total score = 0 + 1 = 1

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Prefix sums in O(n), binary search for each start room in O(log n), repeated n times
Space O(n) Prefix sum array of size n+1

The prefix sum allows constant-time damage calculation, and binary search avoids O(n^2) iterations.

Test Cases

# Provided examples
assert Solution().totalScore(11, [3,6,7], [4,2,5]) == 3  # normal case
assert Solution().totalScore(2, [10000,1], [1,1]) == 1   # large damage first

# Edge cases
assert Solution().totalScore(1, [1], [1]) == 1           # single room, exact HP
assert Solution().totalScore(5, [10], [1]) == 0          # HP less than damage
assert Solution().totalScore(100, [1]*100000, [1]*100000) == 5000050000  # max n stress test
assert Solution().totalScore(10**9, [10**4]*10**5, [1]*10**5)  # large numbers
Test Why
Normal example Validates the scoring logic
Large damage first Tests negative HP handling
Single room Ensures small input works
HP less than damage No points scenario
Max n stress Validates performance and correctness on large input
Large numbers Validates handling of large hp and damage

Edge Cases

Single room: When n = 1, starting at the only room should yield either 0 or 1 point depending on whether hp - damage[1] >= requirement[1]. The