Dungeon Game

Hard

#0174Time: O(2^(m+n))Space: O(m + n)1 company

Patterns

Dynamic Programming

Data structures

Array Matrix

Companies

Flipkart

Prompt

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 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.

Note that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

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]]
Output: 1

Constraints:

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

Approaches

4 approaches with complexity analysis and trade-offs.

This approach uses simple recursion to explore all possible paths from the knight's starting position to the princess. The core idea is to work backward from the destination. We define a function that calculates the minimum health required at a cell (i, j) to guarantee survival until the end. This function recursively calls itself for the next possible cells (down and right) and chooses the path that requires less health.

Algorithm

Define a recursive function findMinHealth(row, col) that returns the minimum health needed upon entering cell (row, col).
Base Case: If the cell is the princess's room (m-1, n-1), the health h needed must satisfy h + dungeon[m-1][n-1] >= 1. So, the required health is max(1, 1 - dungeon[m-1][n-1]).
Boundary Conditions: If row or col goes out of the grid, it's an invalid path. Return a very large value (e.g., Integer.MAX_VALUE) to ensure this path is not chosen.
Recursive Step: For any other cell (row, col), the knight can move down or right. The minimum health required for the rest of the journey is the minimum of the health needed for the path starting from (row+1, col) and the path from (row, col+1).
- minHealthForFuture = min(findMinHealth(row+1, col), findMinHealth(row, col+1))
- The health h at (row, col) must satisfy h + dungeon[row][col] >= minHealthForFuture. Therefore, the health needed is max(1, minHealthForFuture - dungeon[row][col]).
The initial call is findMinHealth(0, 0).

Walkthrough

We define a recursive function, say findMinHealth(row, col), which calculates the minimum health required upon entering the cell (row, col) to be able to reach the princess. The function works as follows:

The base case is the princess's room at (m-1, n-1). To survive this room, the knight's health h must satisfy h + dungeon[m-1][n-1] >= 1. Since health must always be at least 1, the minimum health required upon entering this cell is max(1, 1 - dungeon[m-1][n-1]).
For any other cell (row, col), the knight can move down to (row+1, col) or right to (row, col+1). He will logically choose the path that requires a lower initial health. The minimum health needed for the subsequent journey is min(findMinHealth(row+1, col), findMinHealth(row, col+1)). Let's call this minHealthForFuture.
The health h upon entering (row, col) must be sufficient to survive the current room and the rest of the journey. This means h + dungeon[row][col] >= minHealthForFuture. Thus, the health needed at (row, col) is max(1, minHealthForFuture - dungeon[row][col]).

This recursive structure explores all possibilities, but since findMinHealth for the same cell is called multiple times through different paths, it leads to an exponential number of computations.

1class Solution {2    public int calculateMinimumHP(int[][] dungeon) {3        // This will likely time out for larger inputs.4        return findMinHealth(dungeon, 0, 0);5    }6 7    private int findMinHealth(int[][] dungeon, int row, int col) {8        int m = dungeon.length;9        int n = dungeon[0].length;10 11        if (row >= m || col >= n) {12            return Integer.MAX_VALUE;13        }14 15        if (row == m - 1 && col == n - 1) {16            return Math.max(1, 1 - dungeon[row][col]);17        }18 19        int healthFromDown = findMinHealth(dungeon, row + 1, col);20        int healthFromRight = findMinHealth(dungeon, row, col + 1);21 22        int minHealthForFuture = Math.min(healthFromDown, healthFromRight);23        24        int neededHealth = minHealthForFuture - dungeon[row][col];25 26        return Math.max(1, neededHealth);27    }28}

Complexity

Time

O(2^(m+n))

Space

O(m + n)

Trade-offs

Pros

Conceptually simple and a direct translation of the problem's recursive nature.

Cons

Extremely inefficient due to re-computation of the same subproblems.
Will result in a 'Time Limit Exceeded' error for all but the smallest of grids.

This approach, also known as top-down dynamic programming, optimizes the brute-force recursion by using memoization. It stores the result for each cell (i, j) after computing it for the first time in a 2D array. When the function is called again for the same cell, it retrieves the result from the array instead of re-computing it, thus avoiding redundant calculations.

Algorithm

Create a 2D array memo[m][n] to store the results of subproblems, initialized with a value indicating 'not computed' (e.g., null or -1).
Use the same recursive function findMinHealth(row, col) as the brute-force approach.
Before any computation, check if memo[row][col] already contains a computed result. If yes, return it directly.
If the result is not in the memo table, perform the computation using the same base case and recursive step as before.
After computing the result, store it in memo[row][col] before returning it.

Walkthrough

The problem with the brute-force approach is that it solves the same subproblems repeatedly. We can fix this by storing the results. We introduce a 2D array, memo, of the same size as the dungeon, to cache the minimum health required for each cell (row, col).

The findMinHealth(row, col) function is modified:

It first checks if memo[row][col] has been computed. If so, it returns the stored value.
If not, it proceeds with the calculation as in the brute-force method.
Once the result is calculated, it's stored in memo[row][col] for future use.

This ensures that the calculation for each cell is performed only once, dramatically improving the time complexity from exponential to polynomial.

1class Solution {2    public int calculateMinimumHP(int[][] dungeon) {3        int m = dungeon.length;4        int n = dungeon[0].length;5        Integer[][] memo = new Integer[m][n];6        return findMinHealth(dungeon, 0, 0, m, n, memo);7    }8 9    private int findMinHealth(int[][] dungeon, int row, int col, int m, int n, Integer[][] memo) {10        if (row >= m || col >= n) {11            return Integer.MAX_VALUE;12        }13 14        if (memo[row][col] != null) {15            return memo[row][col];16        }17 18        if (row == m - 1 && col == n - 1) {19            int needed = 1 - dungeon[row][col];20            return memo[row][col] = Math.max(1, needed);21        }22 23        int healthFromDown = findMinHealth(dungeon, row + 1, col, m, n, memo);24        int healthFromRight = findMinHealth(dungeon, row, col + 1, m, n, memo);25 26        int minHealthForFuture = Math.min(healthFromDown, healthFromRight);27        28        int neededHealth = minHealthForFuture - dungeon[row][col];29 30        return memo[row][col] = Math.max(1, neededHealth);31    }32}

Complexity

Time

O(m * n)

Space

O(m * n)

Trade-offs

Pros

Efficient time complexity, solving the overlapping subproblems issue.
Maintains the recursive structure which can be intuitive.

Cons

Uses O(m * n) space for the memoization table.
May lead to a StackOverflowError for very large grids due to deep recursion.

This approach, also known as bottom-up dynamic programming, is an iterative alternative to memoization. It systematically fills a 2D table (dp) representing the minimum health required at each cell. By starting from the destination and working backward to the start, we ensure that when we calculate the value for a cell, the values for the subsequent cells (down and right) have already been computed.

Algorithm

Create a 2D DP table dp[m][n], where dp[i][j] will store the minimum health needed upon entering cell (i, j).
Iterate through the grid in reverse, from i = m-1 down to 0 and j = n-1 down to 0.
For each cell (i, j), calculate dp[i][j] based on the values of already computed cells dp[i+1][j] and dp[i][j+1].
- Destination (m-1, n-1): dp[m-1][n-1] = max(1, 1 - dungeon[m-1][n-1]).
- Last Row (i = m-1): dp[m-1][j] = max(1, dp[m-1][j+1] - dungeon[m-1][j]).
- Last Column (j = n-1): dp[i][n-1] = max(1, dp[i+1][n-1] - dungeon[i][n-1]).
- General Case: dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]).
The final answer is the value computed for the starting cell, dp[0][0].

Walkthrough

Instead of using recursion, we can solve the problem iteratively by building up the solution. We use a 2D array dp of size m x n, where dp[i][j] stores the minimum health the knight must have upon entering cell (i, j) to survive.

We fill this table starting from the bottom-right corner and moving towards the top-left. This order ensures that when we compute dp[i][j], the values dp[i+1][j] (cell below) and dp[i][j+1] (cell to the right) are already known.

The calculation for each cell follows the same logic as the recursive approaches. The final result, the minimum initial health required at the start (0,0), will be stored in dp[0][0] after the loops complete.

1class Solution {2    public int calculateMinimumHP(int[][] dungeon) {3        int m = dungeon.length;4        int n = dungeon[0].length;5        int[][] dp = new int[m][n];6 7        for (int i = m - 1; i >= 0; i--) {8            for (int j = n - 1; j >= 0; j--) {9                if (i == m - 1 && j == n - 1) {10                    // Princess's room11                    dp[i][j] = Math.max(1, 1 - dungeon[i][j]);12                } else if (i == m - 1) {13                    // Last row14                    dp[i][j] = Math.max(1, dp[i][j + 1] - dungeon[i][j]);15                } else if (j == n - 1) {16                    // Last column17                    dp[i][j] = Math.max(1, dp[i + 1][j] - dungeon[i][j]);18                } else {19                    // General case20                    int minHealthForFuture = Math.min(dp[i + 1][j], dp[i][j + 1]);21                    dp[i][j] = Math.max(1, minHealthForFuture - dungeon[i][j]);22                }23            }24        }25        return dp[0][0];26    }27}

Complexity

Time

O(m * n)

Space

O(m * n)

Trade-offs

Pros

Efficient O(m * n) time complexity.
Avoids recursion, thus preventing stack overflow errors and reducing overhead.
The logic is systematic and easy to follow.

Cons

Uses O(m * n) space, which can be substantial for large grids.

This is the most optimized approach in terms of space. By observing the dependency in the 2D DP recurrence relation (dp[i][j] only depends on dp[i+1][...] and dp[i][j+1]), we can see that we only need to keep track of the previous row's DP values to compute the current row's. This allows us to reduce the space from a 2D table to a 1D array.

Algorithm

Create a 1D array dp of size n (number of columns).
Iterate through the grid rows in reverse, from i = m-1 down to 0.
For each row i, iterate through its columns in reverse, from j = n-1 down to 0.
Update dp[j] using the same logic as the 2D DP, but leveraging the 1D array. When calculating the new dp[j] (for row i), the old dp[j] holds the value from row i+1, and dp[j+1] holds the already updated value for the current row i.
- General Case Update: dp[j] = max(1, min(dp[j], dp[j+1]) - dungeon[i][j]).
- Handle boundary cases (last row, last column) appropriately within the loops.
After all iterations, dp[0] will hold the final answer.

Walkthrough

We can optimize the space complexity of the 2D DP solution. Notice that to compute the values for row i, we only need the values from row i+1. This means we don't need to store the entire m x n table. A 1D array of size n is sufficient.

Let dp be a 1D array of size n. We iterate from the last row (m-1) up to the first (0). For each row i, we iterate through its columns j from right to left (n-1 down to 0).

When we compute the value for (i, j) and update dp[j], the dp array cleverly holds a mix of values from row i and i+1. Specifically, dp[j] still holds the value from (i+1, j), while dp[j+1] has already been updated to hold the value for (i, j+1). The recurrence min(dp[j], dp[j+1]) correctly uses the required values to compute the new dp[j]. This in-place update is possible because of the right-to-left column traversal.

After processing all rows, dp[0] will contain the final answer, dp[0][0].

1class Solution {2    public int calculateMinimumHP(int[][] dungeon) {3        int m = dungeon.length;4        int n = dungeon[0].length;5        int[] dp = new int[n];6 7        for (int i = m - 1; i >= 0; i--) {8            for (int j = n - 1; j >= 0; j--) {9                if (i == m - 1 && j == n - 1) {10                    dp[j] = Math.max(1, 1 - dungeon[i][j]);11                } else if (i == m - 1) {12                    dp[j] = Math.max(1, dp[j + 1] - dungeon[i][j]);13                } else if (j == n - 1) {14                    dp[j] = Math.max(1, dp[j] - dungeon[i][j]);15                } else {16                    int minHealthForFuture = Math.min(dp[j], dp[j + 1]);17                    dp[j] = Math.max(1, minHealthForFuture - dungeon[i][j]);18                }19            }20        }21        return dp[0];22    }23}

Complexity

Time

O(m * n)

Space

O(n)

Trade-offs

Pros

Optimal space complexity of O(n) (or O(min(m, n))).
Maintains the efficient O(m * n) time complexity.

Cons

The in-place update logic can be slightly less intuitive to grasp compared to the 2D DP approach.

Solutions

Solution

1public class Solution { public int CalculateMinimumHP ( int [][] dungeon ) { int m = dungeon . Length , n = dungeon [ 0 ]. Length ; int [][] dp = new int [ m + 1 ][]; for ( int i = 0 ; i < m + 1 ; ++ i ) { dp [ i ] = new int [ n + 1 ]; Array . Fill ( dp [ i ], 1 << 30 ); } dp [ m ][ n - 1 ] = dp [ m - 1 ][ n ] = 1 ; for ( int i = m - 1 ; i >= 0 ; -- i ) { for ( int j = n - 1 ; j >= 0 ; -- j ) { dp [ i ][ j ] = Math . Max ( 1 , Math . Min ( dp [ i + 1 ][ j ], dp [ i ][ j + 1 ]) - dungeon [ i ][ j ]); } } return dp [ 0 ][ 0 ]; } }

1class Solution {2public3  int calculateMinimumHP(int[][] dungeon) {4    int m = dungeon.length, n = dungeon[0].length;5    int[][] dp = new int[m + 1][n + 1];6    for (var e : dp) {7      Arrays.fill(e, 1 << 30);8    }9    dp[m][n - 1] = dp[m - 1][n] = 1;10    for (int i = m - 1; i >= 0; --i) {11      for (int j = n - 1; j >= 0; --j) {12        dp[i][j] =13            Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);14      }15    }16    return dp[0][0];17  }18}

1class Solution {2public:3  int calculateMinimumHP(vector<vector<int>> &dungeon) {4    int m = dungeon.size(), n = dungeon[0].size();5    int dp[m + 1][n + 1];6    memset(dp, 0x3f, sizeof dp);7    dp[m][n - 1] = dp[m - 1][n] = 1;8    for (int i = m - 1; ~i; --i) {9      for (int j = n - 1; ~j; --j) {10        dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);11      }12    }13    return dp[0][0];14  }15};

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1public class Solution { public int CalculateMinimumHP ( int [][] dungeon ) { int m = dungeon . Length , n = dungeon [ 0 ]. Length ; int [][] dp = new int [ m + 1 ][]; for ( int i = 0 ; i < m + 1 ; ++ i ) { dp [ i ] = new int [ n + 1 ]; Array . Fill ( dp [ i ], 1 << 30 ); } dp [ m ][ n - 1 ] = dp [ m - 1 ][ n ] = 1 ; for ( int i = m - 1 ; i >= 0 ; -- i ) { for ( int j = n - 1 ; j >= 0 ; -- j ) { dp [ i ][ j ] = Math . Max ( 1 , Math . Min ( dp [ i + 1 ][ j ], dp [ i ][ j + 1 ]) - dungeon [ i ][ j ]); } } return dp [ 0 ][ 0 ]; } }

1class Solution {2public3  int calculateMinimumHP(int[][] dungeon) {4    int m = dungeon.length, n = dungeon[0].length;5    int[][] dp = new int[m + 1][n + 1];6    for (var e : dp) {7      Arrays.fill(e, 1 << 30);8    }9    dp[m][n - 1] = dp[m - 1][n] = 1;10    for (int i = m - 1; i >= 0; --i) {11      for (int j = n - 1; j >= 0; --j) {12        dp[i][j] =13            Math.max(1, Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);14      }15    }16    return dp[0][0];17  }18}

1class Solution {2public:3  int calculateMinimumHP(vector<vector<int>> &dungeon) {4    int m = dungeon.size(), n = dungeon[0].size();5    int dp[m + 1][n + 1];6    memset(dp, 0x3f, sizeof dp);7    dp[m][n - 1] = dp[m - 1][n] = 1;8    for (int i = m - 1; ~i; --i) {9      for (int j = n - 1; ~j; --j) {10        dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);11      }12    }13    return dp[0][0];14  }15};

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

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.