Computer Science
Updated about 17 hours ago | GitHub

Dungeon Game

Problem Highlights

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • Why does the knight need to go RIGHT->RIGHT->DOWN->DOWN path? What if he went DOWN->DOWN->RIGHT-RIGHT path, there is lot of positive energy in this path. He doesn’t need initial energy to start with, and he could gather positive energy on the way.

    • If the knight follows the DOWN->DOWN->RIGHT-RIGHT path, the knight would need 8 health to begin with to not die when hitting the left bottom corner.

  • What is the minimum initial health required for the knight to survive the journey (aka. bare minimum health points)?

    • The bare minimum health points corresponds with the healthiest path (aka. most energy preserving path)

  • How can we achieve the healthiest path?

    • To achieve the healthiest path, the knight needs to constantly choose: the cell that consumes the least energy of all available cells (aka. the cell with the least powerful demon) or even better, choose cells that provides the knight with more energy (aka. cells containing magical orbs).
Example 1:
Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

Example 2:
Input: dungeon = [0](/compsci/0)
Output: 1

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

As a general pattern of dynamic programming, usually we construct a array of one or two dimensions (i.e. dp[i]) where each element holds the optimal solution for the corresponding subproblem.

To calculate one particular element in the dp[i] array, we would refer to the previously calculated elements. And the last element that we figure out in the array would be the desired solution for the original problem. We need to examine the optimal path and look at our knight’s health at each step along the journey. The lowest health points is the worst health condition that our knight had to endure during the journey. That value should be the basis upon which the minimum initial health is to be calculated.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: The main idea is to build a 2D array dp to store the minimum initial health required at each position to reach the bottom-right corner. We start from the bottom-right corner and work our way backwards to the top-left corner.

At each position, we take the minimum of the minimum initial health required at the position below and the position to the right, and subtract the dungeon value at the current position. If the result is less than or equal to 0, we set it to 1 (since the knight needs to have at least 1 health point to be alive). Finally, we return the value at the top-left corner of the dp array.

To handle the boundary cases, we add an extra row and an extra column to the dp array, and set them all to infinity except for dp[m-1][n] and dp[m][n-1], which are set to 1.

⚠️ Common Mistakes

dp[i][j] stores the minimum starting health needed to enter cell (i, j) and reach the princess alive — not an accumulated path cost. Recurrence: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]). Common ways to get this wrong:

  • Filling the table top-left → bottom-right. The minimum starting health at (i, j) depends on the minimum health required at (i+1, j) and (i, j+1), so the table must be filled bottom-right → top-left. A forward pass has no way to know how much future damage the knight still has to absorb.
  • Using max instead of min when combining the two neighbors. Between the down and right options you want the path that demands the least future health, which is min(dp[i+1][j], dp[i][j+1]). Using max picks the more punishing path and inflates the answer.
  • Adding dungeon[i][j] instead of subtracting it. A positive dungeon[i][j] is a magic orb that heals the knight, so it reduces the health needed on entry; a negative value is a demon that raises the requirement. That sign convention is what makes - dungeon[i][j] correct.
  • Dropping the max(..., 1) floor. Without it, a large magic orb can drive the requirement to zero or below, but the knight must stay at ≥1 HP at every cell — including the entry cell. The max(..., 1) clamps that invariant.
  • Mis-seeding the sentinel row and column. Only the two cells one step past the princess (dp[m-1][n] and dp[m][n-1]) should be initialized to 1; every other boundary cell must be ∞ so the min never chooses a non-existent path.

4: I-mplement

Implement the code to solve the algorithm.

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [[float('inf')] * (n+1) for _ in range(m+1)]
        dp[m-1][n] = dp[m][n-1] = 1
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1, -1):
                dp[i][j] = max(min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j], 1)
        return dp[0][0]

class Solution {
  int inf = Integer.MAX_VALUE;
  int[][] dp;
  int rows, cols;

  public int getMinHealth(int currCell, int nextRow, int nextCol) {
    if (nextRow >= this.rows || nextCol >= this.cols)
      return inf;
    int nextCell = this.dp[nextRow][nextCol];
    // hero needs at least 1 point to survive
    return Math.max(1, nextCell - currCell);
  }

  public int calculateMinimumHP(int[][] dungeon) {
    this.rows = dungeon.length;
    this.cols = dungeon[0].length;
    this.dp = new int[rows][cols];
    for (int[] arr : this.dp) {
      Arrays.fill(arr, this.inf);
    }
    int currCell, rightHealth, downHealth, nextHealth, minHealth;
    for (int row = this.rows - 1; row >= 0; --row) {
      for (int col = this.cols - 1; col >= 0; --col) {
        currCell = dungeon[row][col];

        rightHealth = getMinHealth(currCell, row, col + 1);
        downHealth = getMinHealth(currCell, row + 1, col);
        nextHealth = Math.min(rightHealth, downHealth);

        if (nextHealth != inf) {
          minHealth = nextHealth;
        } else {
          minHealth = currCell >= 0 ? 1 : 1 - currCell;
        }
        this.dp[row][col] = minHealth;
      }
    }
    return this.dp[0][0];
  }
}

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

  • Trace through your code with an input to check for the expected output
  • Catch possible edge cases and off-by-one errors

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

  • Time Complexity: O(mn)
  • Space Complexity: O(mn)