Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Binary Search
11 [3,6,7] [4,2,5]
2 [10000,1] [1,1]
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3771: Total Score of Dungeon Runs
// Auto-generated Java example from go.
class Solution {
public void exampleSolution() {
}
}
// Reference (go):
// // Accepted solution for LeetCode #3771: Total Score of Dungeon Runs
// package main
//
// import "sort"
//
// // https://space.bilibili.com/206214
// func totalScore1(hp int, damage []int, requirement []int) (ans int64) {
// sum := make([]int, len(damage)+1)
// for i, req := range requirement {
// sum[i+1] = sum[i] + damage[i]
// low := sum[i+1] + req - hp
// j := sort.SearchInts(sum[:i+1], low)
// ans += int64(i - j + 1)
// }
// return
// }
//
// func totalScore(hp int, damage, requirement []int) int64 {
// n := len(damage)
// sum := make([]int, n+1)
// ans := n * (n + 1) / 2
// for i, req := range requirement {
// sum[i+1] = sum[i] + damage[i]
// low := sum[i+1] + req - hp
// if low > 0 {
// ans -= sort.SearchInts(sum[:i+1], low)
// }
// }
// return int64(ans)
// }
// Accepted solution for LeetCode #3771: Total Score of Dungeon Runs
package main
import "sort"
// https://space.bilibili.com/206214
func totalScore1(hp int, damage []int, requirement []int) (ans int64) {
sum := make([]int, len(damage)+1)
for i, req := range requirement {
sum[i+1] = sum[i] + damage[i]
low := sum[i+1] + req - hp
j := sort.SearchInts(sum[:i+1], low)
ans += int64(i - j + 1)
}
return
}
func totalScore(hp int, damage, requirement []int) int64 {
n := len(damage)
sum := make([]int, n+1)
ans := n * (n + 1) / 2
for i, req := range requirement {
sum[i+1] = sum[i] + damage[i]
low := sum[i+1] + req - hp
if low > 0 {
ans -= sort.SearchInts(sum[:i+1], low)
}
}
return int64(ans)
}
# Accepted solution for LeetCode #3771: Total Score of Dungeon Runs
#
# @lc app=leetcode id=3771 lang=python3
#
# [3771] Total Score of Dungeon Runs
#
# @lc code=start
from bisect import bisect_left
from typing import List
class Solution:
def totalScore(self, hp: int, damage: List[int], requirement: List[int]) -> int:
n = len(damage)
# prefix_damage[k] stores sum of damage[0]...damage[k-1]
# prefix_damage[0] = 0
prefix_damage = [0] * (n + 1)
for i in range(n):
prefix_damage[i+1] = prefix_damage[i] + damage[i]
total_points = 0
# Iterate through each room 'i' considering it as the room where we potentially score a point.
# We need to find how many starting rooms 'j' (where 1 <= j <= i+1) satisfy the condition.
# In 0-indexed terms, let current room be 'i' (0 to n-1).
# Starting room 'j' corresponds to index 'start_idx' (0 to i).
# Damage taken from start_idx to i is: prefix_damage[i+1] - prefix_damage[start_idx]
# Condition: hp - (prefix_damage[i+1] - prefix_damage[start_idx]) >= requirement[i]
# Rearranging: prefix_damage[start_idx] >= prefix_damage[i+1] + requirement[i] - hp
for i in range(n):
target = prefix_damage[i+1] + requirement[i] - hp
# We need to count valid 'start_idx' in range [0, i] such that
# prefix_damage[start_idx] >= target.
# Since prefix_damage is sorted (damages are positive), we can use binary search.
# Find the first index 'k' in prefix_damage such that prefix_damage[k] >= target.
# We are only interested in indices up to 'i'.
# Actually, the search space for start_idx is 0 to i.
# However, bisect_left on the whole array or a slice is fine, but we only care if the found index <= i.
# Optimization: since we need start_idx in [0, i], we can search in that range specifically
# or just search globally and cap the result.
# Let's search in the full prefix_damage array but interpret result.
idx = bisect_left(prefix_damage, target, 0, i + 1)
# All indices from 'idx' to 'i' satisfy the condition because prefix_damage is increasing.
# The number of such indices is (i - idx + 1).
if idx <= i:
total_points += (i - idx + 1)
return total_points
# @lc code=end
// Accepted solution for LeetCode #3771: Total Score of Dungeon Runs
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (go):
// // Accepted solution for LeetCode #3771: Total Score of Dungeon Runs
// package main
//
// import "sort"
//
// // https://space.bilibili.com/206214
// func totalScore1(hp int, damage []int, requirement []int) (ans int64) {
// sum := make([]int, len(damage)+1)
// for i, req := range requirement {
// sum[i+1] = sum[i] + damage[i]
// low := sum[i+1] + req - hp
// j := sort.SearchInts(sum[:i+1], low)
// ans += int64(i - j + 1)
// }
// return
// }
//
// func totalScore(hp int, damage, requirement []int) int64 {
// n := len(damage)
// sum := make([]int, n+1)
// ans := n * (n + 1) / 2
// for i, req := range requirement {
// sum[i+1] = sum[i] + damage[i]
// low := sum[i+1] + req - hp
// if low > 0 {
// ans -= sort.SearchInts(sum[:i+1], low)
// }
// }
// return int64(ans)
// }
// Accepted solution for LeetCode #3771: Total Score of Dungeon Runs
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3771: Total Score of Dungeon Runs
// package main
//
// import "sort"
//
// // https://space.bilibili.com/206214
// func totalScore1(hp int, damage []int, requirement []int) (ans int64) {
// sum := make([]int, len(damage)+1)
// for i, req := range requirement {
// sum[i+1] = sum[i] + damage[i]
// low := sum[i+1] + req - hp
// j := sort.SearchInts(sum[:i+1], low)
// ans += int64(i - j + 1)
// }
// return
// }
//
// func totalScore(hp int, damage, requirement []int) int64 {
// n := len(damage)
// sum := make([]int, n+1)
// ans := n * (n + 1) / 2
// for i, req := range requirement {
// sum[i+1] = sum[i] + damage[i]
// low := sum[i+1] + req - hp
// if low > 0 {
// ans -= sort.SearchInts(sum[:i+1], low)
// }
// }
// return int64(ans)
// }
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.