LeetCode 2214: Minimum Health to Beat Game Solution

Master LeetCode problem 2214 (Minimum Health to Beat Game), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2214. Minimum Health to Beat Game

Medium

Array Greedy

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming. We can start from the bottom-right corner of the dungeon and calculate the minimum health required to reach the princess. We can iterate backward through the dungeon, calculating the minimum health required to reach each cell.

At each cell, we need to calculate the minimum health needed to reach the princess from that cell. We can calculate this minimum health based on the health required to move to the next cell and the health available at that cell.

If the health available at a cell is greater than the health required to move to the next cell, then the minimum health required is 1. Otherwise, we need to calculate the difference between the health required to move to the next cell and the health available at the current cell.

The final answer will be the minimum health required to reach the princess from the starting cell.

Time Complexity:

The time complexity of this approach is O(m*n), where m is the number of rows and n is the number of columns in the dungeon.

Space Complexity:

The space complexity is O(m*n) as well, as we use a 2D dp array to store the minimum health required at each cell.

: :

Solution Code

public int calculateMinimumHP(int[][] dungeon) {
    int m = dungeon.length;
    int n = dungeon[0].length;
    
    int[][] dp = new int[m][n];
    
    dp[m-1][n-1] = Math.max(1 - dungeon[m-1][n-1], 1);
    
    for (int i = m-2; i >= 0; i--) {
        dp[i][n-1] = Math.max(dp[i+1][n-1] - dungeon[i][n-1], 1);
    }
    
    for (int j = n-2; j >= 0; j--) {
        dp[m-1][j] = Math.max(dp[m-1][j+1] - dungeon[m-1][j], 1);
    }
    
    for (int i = m-2; i >= 0; i--) {
        for (int j = n-2; j >= 0; j--) {
            int minHealth = Math.min(dp[i+1][j], dp[i][j+1]);
            dp[i][j] = Math.max(minHealth - dungeon[i][j], 1);
        }
    }
    
    return dp[0][0];
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2214 (Minimum Health to Beat Game)?

This page provides optimized solutions for LeetCode problem 2214 (Minimum Health to Beat Game) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2214 (Minimum Health to Beat Game)?

The time complexity for LeetCode 2214 (Minimum Health to Beat Game) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2214 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2214 in Java, C++, or Python.

Back to LeetCode Solutions