Dungeon Game - Leetcode Solution

Problem: Dungeon Game

The problem statement can be found here: https://leetcode.com/problems/dungeon-game/

To summarize, you are given a 2D grid where each cell represents a room in a dungeon; the value of each cell represents the amount of health the player will gain or lose when entering that room. The player starts at the top-left corner of the dungeon and must reach the bottom-right corner. The player's health starts at 1 and must remain positive throughout the game; otherwise, the player will die. Your task is to compute the minimum initial health the player must have to complete the dungeon.

Approach:

The problem requires us to compute the minimum initial health the player must have to complete the dungeon. We can solve this problem using dynamic programming techniques.

Define health[i][j] as the minimum health required when arriving at dungeon[i][j]. Also, define dungeon[i][j] as the gain or loss of health when arriving at dungeon[i][j].

We can start at the bottom-right corner of the grid, where to stay alive, the player must have a minimum health of 1. We can compute the health required for each cell in reverse order.

Therefore, the base case would be health[M-1][N-1] = max(1, 1 - dungeon[M-1][N-1]). This step is done to ensure that the player has a minimum health of 1 when they enter the last room.

We then proceed to fill in the values of health array for the bottom row and the rightmost column. For each row, we compute health[i][N-1] as max(1, health[i+1][N-1] - dungeon[i][N-1]), and for each column, we compute health[M-1][j] as max(1, health[M-1][j+1] - dungeon[M-1][j]). This step is done to ensure that the player has the minimum health to exit the dungeon from the bottom row or the rightmost column.

We then fill in the remaining values of health[i][j] using the formula: health[i][j] = max(1, min(health[i+1][j], health[i][j+1]) - dungeon[i][j]). We use the min() function to choose the path that requires the least amount of health. We then subtract the gain/loss of health in that cell.

Finally, we return the health[0][0], which represents the minimum initial health required to complete the dungeon when starting at the top-left corner.

Solution:

Here is the Python implementation of the above approach:

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        
        M = len(dungeon)
        N = len(dungeon[0])
        
        # Define a 2-D array to store the minimum health required
        health = [[0 for j in range(N)] for i in range(M)]
        
        # Base case: minimum health required to enter last cell
        health[M-1][N-1] = max(1, 1 - dungeon[M-1][N-1])
        
        # Fill values for the bottom row
        for j in range(N-2, -1, -1):
            health[M-1][j] = max(1, health[M-1][j+1] - dungeon[M-1][j])
        
        # Fill values for the rightmost column
        for i in range(M-2, -1, -1):
            health[i][N-1] = max(1, health[i+1][N-1] - dungeon[i][N-1])
            
        # Fill remaining values
        for i in range(M-2, -1, -1):
            for j in range(N-2, -1, -1):
                health[i][j] = max(1, min(health[i+1][j], health[i][j+1]) - dungeon[i][j])
                
        # Return the minimum initial health required to start from top-left corner
        return health[0][0]

Time Complexity:

The solution uses nested loops to fill in the health array, which takes O(MN) time. Therefore, the time complexity of this solution is O(MN).

Space Complexity:

The solution defines a 2-D array to store the minimum health required. Therefore, the space complexity of this solution is also O(MN).

This solution is optimal in both time and space complexity and will pass all test cases on LeetCode.

1