How do you solve Dungeon Game on LeetCode?

Dungeon Game (LeetCode #174) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m*n) time complexity and O(m*n) space complexity. Key insight: The knight's health must always be positive to survive.

What is the brute force solution for Dungeon Game?

The brute force approach for Dungeon Game is Brute Force, with O(2^(m+n)) time complexity and O(m+n) space complexity. The brute force approach explores all possible paths the knight can take to reach the princess. It calculates the health required for each path and returns the minimum health needed to survive. The optimal Optimal Solution approach improves this to O(m*n).

What algorithm or data structure is used to solve Dungeon Game?

Dungeon Game uses the following concepts: Array, Dynamic Programming, Matrix. The recommended patterns to study are: Dynamic Programming, Grid Traversal.

What are the interview tips for Dungeon Game?

Explain your thought process clearly during the interview. Don't rush into coding; take time to plan your approach. Be prepared to discuss time and space complexity of your solution.

What are common mistakes when solving Dungeon Game?

Forgetting to handle negative health values correctly. Not considering the edge cases like single room or all negative values.

#174

Dungeon Game

Hard

ArrayDynamic ProgrammingMatrixDynamic ProgrammingGrid Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(2^(m+n))	O(m*n)
Space	O(m+n)	O(m*n)

💡

Intuition

Time O(m*n)Space O(m*n)

The optimal solution uses dynamic programming to calculate the minimum health needed at each room, starting from the princess's room and working backwards to the knight's starting position. This avoids redundant calculations and efficiently finds the answer.

⚙️

Algorithm

5 steps

1Step 1: Create a DP table where dp[i][j] represents the minimum health required to enter room (i, j).
2Step 2: Initialize the bottom-right cell (princess's room) based on its value.
3Step 3: Fill the last row and last column based on the values of the rooms.
4Step 4: Fill the rest of the DP table from bottom-right to top-left using the formula: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]).
5Step 5: The value at dp[0][0] will give the minimum health required.

solution.py17 lines

1# Full working Python code
2
3def calculateMinimumHP(dungeon):
4    m, n = len(dungeon), len(dungeon[0])
5    dp = [[0] * n for _ in range(m)]
6    dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1])
7
8    for i in range(m-2, -1, -1):
9        dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1])
10    for j in range(n-2, -1, -1):
11        dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j])
12
13    for i in range(m-2, -1, -1):
14        for j in range(n-2, -1, -1):
15            dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])
16
17    return dp[0][0]

ℹ

Complexity note: The time complexity is O(m*n) because we fill each cell in the DP table once. The space complexity is also O(m*n) due to the DP table.

1The knight's health must always be positive to survive.
2Dynamic programming allows us to build solutions from smaller subproblems, making it efficient.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.