Log inSign up
hardLeetCodeNot Started

Dungeon Game

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers).

To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Return the knight's minimum initial health so that he can rescue the princess.

Example 1 · Standard 3x3 Dungeon:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The optimal path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) with minimum initial health of 7: - Starts with 7 health - (0,0): 7 + (-2) = 5 - (0,1): 5 + (-3) = 2 - (0,2): 2 + 3 = 5 - (1,2): 5 + 1 = 6 - (2,2): 6 + (-5) = 1 (rescues princess with 1 HP remaining!).

Example 2 · Single Room Dungeon:

Input: dungeon = [[0]]
Output: 1
Explanation: Knight needs at least 1 HP to stay alive.

Constraints:

  • m == dungeon.length
  • n == dungeon[i].length
  • 1 <= m, n <= 200
  • -1000 <= dungeon[i][j] <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D Dynamic Programming table formulation
  • Understanding why reverse (backward) DP resolves future state dependency
  • Rolling 1D array space optimization

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why backward dynamic programming is required when future states dictate boundary constraints.
  • Formulate the non-linear transition max(1, next_health - cell_value).
  • Compress 2D grid DP tables into 1D rolling memory.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Minimum Path SumUnique PathsCherry Pickup

1. Brute Force — Recursive Backtracking

Intuition

At each cell (r, c), recursively compute the minimum health needed to finish the game by taking the right path and the down path.

Algorithm

  1. Initialize required state variables and allocate data structures for Brute Force — Recursive Backtracking.
  2. Iterate through the input array and apply the core algorithmic condition.
  3. Update boundaries, frequencies, or pointers in accordance with the invariant.
  4. Return the computed result or transformed array.

Recursive Backtracking Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [(0,0):-2, (0,1):-3, (0,2):3, (1,0):-5, (1,1):-10, (1,2):1, (2,0):10, (2,1):30, (2,2):-5]
Current operationSTEP 1 OF 6
Princess room at (2,2) with val = -5
Visual state
Values and pointers at this exact step
pointers
S
-5
0
↑ Princess
Variables at this step
r
2
c
2
val
-5
required
6
Check / comparison
minHealth(2,2) = max(1, 1 - (-5)) = 6
Decision / next transition
Base condition: entering (2,2) requires at least 6 health.
Why this step matters

Princess room at (2,2) with val = -5. Knight must have >= 1 health after room: health - 5 >= 1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6using namespace std;
7
8class Solution {
9private:
10 int solve(const vector<vector<int>>& dungeon, int r, int c, int m, int n) {
11 if (r == m - 1 && c == n - 1) {
12 return max(1, 1 - dungeon[r][c]);
13 }
14
15 int right = (c + 1 < n) ? solve(dungeon, r, c + 1, m, n) : INT_MAX;
16 int down = (r + 1 < m) ? solve(dungeon, r + 1, c, m, n) : INT_MAX;
17
18 int minHealthNext = min(right, down);
19 return max(1, minHealthNext - dungeon[r][c]);
20 }
21
22public:
23 int calculateMinimumHP(vector<vector<int>>& dungeon) {
24 int m = dungeon.size(), n = dungeon[0].size();
25 return solve(dungeon, 0, 0, m, n);
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<vector<int>> dungeon = {{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}};
32 cout << "Input: [[-2,-3,3],[-5,-10,1],[10,30,-5]]\n";
33 cout << "Brute Force Min HP: " << sol.calculateMinimumHP(dungeon) << "\n";
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Brute Force — Recursive Backtracking.
  • Space complexity: O(1) — Space complexity for Brute Force — Recursive Backtracking.

Why Brute Force Doesn't Scale:

For a 20x20 dungeon, 240 exceeds 1 trillion operations.

1D Dynamic Programming solves a 200x200 grid (40,000 cells) in under 1 millisecond using just 201 integers of memory.

2. Better — 2D Dynamic Programming Table

Intuition

Construct an (M + 1) x (N + 1) DP table filled with infinity. Set dp[m][n-1] = dp[m-1][n] = 1. Traverse backwards from (m-1, n-1) to (0, 0) using dp[r][c] = max(1, min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c]).

Algorithm

  1. Construct an (M + 1) x (N + 1) DP table filled with infinity
  2. Set dp[m][n-1] = dp[m-1][n] = 1
  3. Traverse backwards from (m-1, n-1) to (0, 0) using dp[r][c] = max(1, min(dp[r+1][c], dp[r][c+1]) - dungeon[r][c]).

2D Dynamic Programming Table Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [dp[0][0]=7, dp[0][1]=5, dp[0][2]=2, dp[1][0]=6, dp[1][1]=11, dp[1][2]=5, dp[2][0]=1, dp[2][1]=1, dp[2][2]=6]
Current operationSTEP 1 OF 6
Allocate dp[4][4] initialized to INF, with guards dp[3][2]=1, dp[2][3]=1
Visual state
Values and pointers at this exact step
pointers
S
6
0
↑ base dp=6
Variables at this step
r
2
c
2
dp22
6
Check / comparison
dp[2][2] = max(1, min(1, 1) - (-5)) = 6
Decision / next transition
Set dp[2][2] = 6.
Why this step matters

Allocate dp[4][4] initialized to INF, with guards dp[3][2]=1, dp[2][3]=1.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6using namespace std;
7
8class Solution {
9public:
10 int calculateMinimumHP(vector<vector<int>>& dungeon) {
11 int m = dungeon.size(), n = dungeon[0].size();
12 vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
13
14 // Base cases: 1 HP required to exit dungeon
15 dp[m][n - 1] = 1;
16 dp[m - 1][n] = 1;
17
18 for (int r = m - 1; r >= 0; r--) {
19 for (int c = n - 1; c >= 0; c--) {
20 int minNext = min(dp[r + 1][c], dp[r][c + 1]);
21 dp[r][c] = max(1, minNext - dungeon[r][c]);
22 }
23 }
24
25 return dp[0][0];
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<vector<int>> dungeon = {{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}};
32 cout << "Input: [[-2,-3,3],[-5,-10,1],[10,30,-5]]\n";
33 cout << "2D DP Min HP: " << sol.calculateMinimumHP(dungeon) << "\n";
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Better — 2D Dynamic Programming Table.
  • Space complexity: O(N) — Space complexity for Better — 2D Dynamic Programming Table.

3. Optimal — 1D Space-Optimized Dynamic Programming

Intuition

Notice dp[r][c] only requires dp[r+1][c] (current column value before update) and dp[r][c+1] (previous column in the current row). We can compress the 2D matrix into a 1D vector of length n + 1.

Algorithm

  1. Notice dp[r][c] only requires dp[r+1][c] (current column value before update) and dp[r][c+1] (previous column in the current row)
  2. We can compress the 2D matrix into a 1D vector of length n + 1.

1D Rolling Space-Optimized DP Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [dp[0]=7, dp[1]=5, dp[2]=2, dp[3]=INF]
Current operationSTEP 1 OF 6
Allocate 1D array dp[4] initialized to INF, with dp[2] set to 1 before processing bottom row
Visual state
Values and pointers at this exact step
pointers
S
1
INF
0
↑ init
1
Variables at this step
dp
["INF","INF",1,"INF"]
Check / comparison
dp size = N + 1
Decision / next transition
Process row 2 (bottom row) right to left.
Why this step matters

Allocate 1D array dp[4] initialized to INF, with dp[2] set to 1 before processing bottom row.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6using namespace std;
7
8class Solution {
9public:
10 int calculateMinimumHP(vector<vector<int>>& dungeon) {
11 int m = dungeon.size(), n = dungeon[0].size();
12 vector<int> dp(n + 1, INT_MAX);
13
14 dp[n - 1] = 1;
15
16 for (int r = m - 1; r >= 0; r--) {
17 for (int c = n - 1; c >= 0; c--) {
18 int minNext = min(dp[c], dp[c + 1]);
19 dp[c] = max(1, minNext - dungeon[r][c]);
20 }
21 dp[n] = INT_MAX; // Reset boundary for next row up
22 }
23
24 return dp[0];
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<vector<int>> dungeon = {{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}};
31 cout << "Input: [[-2,-3,3],[-5,-10,1],[10,30,-5]]\n";
32 cout << "Optimal 1D DP Min HP: " << sol.calculateMinimumHP(dungeon) << "\n";
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Optimal — 1D Space-Optimized Dynamic Programming.
  • Space complexity: O(1) — Space complexity for Optimal — 1D Space-Optimized Dynamic Programming.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Top-Down Recursive ExplorationO(2^(M + N))O(M + N)Recursively explore all possible right and down paths, tracking minimum initial health needed for each path.Overlapping subproblems computed exponentially.
2.Better — 2D Dynamic Programming TableO(M * N)O(M * N)Construct an (M + 1) x (N + 1) DP table initialized to infinity. Set princess destination boundary dp[m][n-1] = dp[m-1][n] = 1. Fill backwards from bottom-right to top-left.2D table memory allocations.
3.Optimal — Space-Optimized 1D Dynamic ProgrammingOptimalO(M * N)O(N)Observe that dp[r][c] depends only on dp[r+1][c] (same column, previous row) and dp[r][c+1] (next column, same row). Compress table into a single 1D array of size N + 1.None; theoretical optimum.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty or Single Element Array — Handle minimal input sizes (N = 0 or N = 1) cleanly without out-of-bounds errors.
  • Duplicate Elements — Verify behavior when all elements are identical (e.g. all 0s or all equal values).
  • Extreme Numerical Values — Account for maximum/minimum allowed constraint values (-109 to 109) to prevent overflow.
  • Boundary Conditions — Ensure correct execution when target or match is located at the first or last index.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Dungeon Game?

2.Why is the brute force approach suboptimal for large inputs in Dungeon Game?

3.Which data structure or technique enables the optimal solution for Dungeon Game?

Back to DSA Sheet