Interview Prepdp-grid-intervalshardAmazonGoogle

Dungeon Game

Choose your preparation mode4 modes available

Try It Solution Trace

📋

Problem

Imagine a knight trapped in a dungeon filled with monsters and magic potions, needing to find the minimum initial health to survive the journey to rescue the princess.

You are given an m x n grid dungeon where each cell contains an integer representing health points gained (positive) or lost (negative). The knight starts at the top-left cell and must reach the bottom-right cell by moving only right or down. The knight's health must never drop to zero or below at any point. Determine the minimum initial health the knight needs to start with to reach the princess safely.

1 ≤ m, n ≤ 200-1000 ≤ dungeon[i][j] ≤ 1000

Edge cases: Single cell with positive value → minimum initial health is 1Single cell with negative value → minimum initial health is 1 - cell valueAll cells zero → minimum initial health is 1

</>

IDE

def calculateMinimumHP(dungeon: List[List[int]]) -> int:

def calculateMinimumHP(dungeon):
    # Write your solution here
    pass

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int calculateMinimumHP(vector<vector<int>>& dungeon) {
    // Write your solution here
    return 0;
}

function calculateMinimumHP(dungeon) {
    // Write your solution here
}

0/9

Common Bugs to Avoid

Wrong: 0Not clamping minimum health to 1, allowing zero or negative health.✅ Use max(1, calculated_health) at every DP step to ensure health never drops below 1.

Wrong: Incorrect low values (e.g., 3 instead of 7)Using greedy approach picking only one path (right or down) instead of minimum of both.✅ At each cell, take min of dp[i+1][j] and dp[i][j+1] to consider all paths.

Wrong: Too high values (e.g., 10 instead of 7)Not taking minimum of next steps, or adding dungeon[i][j] instead of subtracting.✅ Use dp[i][j] = max(1, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]) correctly.

Wrong: Timeout or no outputUsing brute force recursion without memoization or DP.✅ Implement DP with memoization or bottom-up tabulation to achieve O(m*n) time.

✓

Test Cases

t1_01basic

Input{"dungeon":[[-2,-3,3],[-5,-10,1],[10,30,-5]]}

Expected7

Starting with 7 health, the knight can survive the path (right, right, down, down) without health dropping below 1.

t1_02basic

Input{"dungeon":[[0,-3],[-10,0]]}

Expected4

Minimum initial health 4 allows path (right, down) without health dropping below 1.

Practice

(1/5)

1. You need to find the cheapest cost to travel from a source city to a destination city with at most K stops, given a list of flights with costs. Which algorithmic approach guarantees finding the optimal solution efficiently under these constraints?

easy

A. Greedy algorithm using Dijkstra's shortest path without modification

B. Topological sort followed by single pass relaxation of edges

C. Simple depth-first search exploring all paths without pruning

D. Dynamic programming using a bottom-up approach iterating over stops

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Dungeon Game

Practice

Solution

Step 1: Understand the problem constraints

Step 2: Identify suitable algorithm

Final Answer:

Quick Check:

Solution

Step 1: Understand problem constraints

Step 2: Identify suitable algorithmic pattern

Final Answer:

Quick Check:

Solution

Step 1: Compress input string "aba"

Step 2: Trace dp table filling

Final Answer:

Quick Check:

Solution

Step 1: Understand problem structure

Step 2: Identify suitable algorithm

Final Answer:

Quick Check:

Solution

Step 1: Identify loops in bottom-up DP

Step 2: Calculate complexity

Final Answer:

Quick Check:

Ready to prove it?