2214. Minimum Health to Beat Game - Detailed Explanation

Problem Statement

You are given an integer array damage where each element represents the change in your health after completing a level:

• A positive value means you lose that much health (damage).

• A negative value means you gain health (healing).

You play the levels in order. Your goal is to finish all levels without your health ever dropping below 1. Determine the minimum initial health required to accomplish this.

Examples

Example 1:

• Input: damage = [3, 4, 3]
• Output: 11
• Explanation:
  • Start with 11 health.
  • Level 1: 11 – 3 = 8
  • Level 2: 8 – 4 = 4
  • Level 3: 4 – 3 = 1
  • Health never drops below 1.

Example 2:

• Input: damage = [1, 2, 3]
• Output: 7
• Explanation:
  • Start with 7 health.
  • Level 1: 7 – 1 = 6
  • Level 2: 6 – 2 = 4
  • Level 3: 4 – 3 = 1
  • Health never drops below 1.

Example 3:

• Input: damage = [5, -3, 2]
• Output: 6
• Explanation:
  • Start with 6 health.
  • Level 1: 6 – 5 = 1
  • Level 2: 1 + 3 = 4 (healing from -3)
  • Level 3: 4 – 2 = 2
  • Health never drops below 1.

Constraints

• 1 ≤ damage.length ≤ 10⁵
• -10⁴ ≤ damage[i] ≤ 10⁴

Hints

1. Cumulative Health: Think about how your health changes as you progress through each level. Compute the running (or prefix) sum of the damage array.
2. Tracking the Lowest Point: Identify the minimum value reached by the running sum. If at any point your cumulative health is negative, that tells you how much extra initial health you need to avoid ever falling below 1.

Approach Overview

There are multiple ways to solve this problem. Let’s discuss two approaches:

Brute Force Approach

• Idea: Start with an initial health of 1, simulate the game level by level, and check if your health ever falls below 1. If it does, increment the starting health and try again.
• Drawback: This method requires simulating the entire game repeatedly, which results in a high time complexity. For large arrays, this approach is not feasible.

Optimal Approach Using Prefix Sum

• Idea:

  • Compute the running sum of health changes as you progress through the levels.
  • Find the minimum value reached by this running sum.
  • If the minimum value is below 0 (say, –X), you need at least 1 + X extra health to ensure the lowest point is raised to 1.

• How It Works:

  • Let runningSum be the cumulative sum of the damage changes when starting at 0.
  • Let minRunningSum be the minimum value of this running sum.
  • The minimum initial health required is:
    Initial Health = max(1, 1 − minRunningSum)

• Example Walkthrough (damage = [5, -3, 2]):

  • Start with a running sum of 0.
  • After Level 1: 0 – 5 = –5
  • After Level 2: –5 + 3 = –2
  • After Level 3: –2 – 2 = –4
  • The minimum running sum is –5.
  • To ensure that even at the lowest point your health is at least 1, you need an extra 1 – (–5) = 6 initial health.
  • Therefore, the answer is 6.

• Time Complexity: O(n)

• Space Complexity: O(1)

Code Implementation

Python Code