Dungeon Game
Updated
Problem statement
A knight must rescue a princess held in the bottom-right room of a dungeon. The dungeon is an m x n grid of rooms, and the knight starts in the top-left room. From any room the knight can move only one room to the right or one room down.
Each room changes the knight's health by dungeon[r][c]: a negative number is a demon that takes that much health, a positive number is a magic orb that adds health, and 0 is an empty room. The first and the last room count too.
The knight starts with a positive whole number of health points. If the health ever drops to 0 or below, the knight dies. Return the smallest starting health that lets the knight reach the princess alive.
Function
calculateMinimumHP(dungeon: int[][]) → intExamples
Example 1
dungeon = [[-3,5],[-10,1]]return = 4Going right then down visits -3, 5, 1. With 4 health the knight has 1 after the first room and stays alive. Going down first meets -3 and then -10, which needs 14. So the answer is 4.
Example 2
dungeon = [[2,-6,1],[-4,3,-2]]return = 3Going down first visits 2, -4, 3, -2. The running total goes 2, -2, 1, -1, so its lowest point is -2 and the knight needs 3 health to stay at 1 or more. The other two paths both enter the -6 room and fall to -4 or lower, so they need at least 5. The answer is 3.
Example 3
dungeon = [[0]]return = 1The only room is empty, but the knight's health must always be positive, so the answer is 1.
Constraints
m == dungeon.lengthn == dungeon[i].length1 <= m, n <= 200-1000 <= dungeon[i][j] <= 1000
More LotusFlare Onsite Interview questions
Similar questions at other companies
- Dungeon GameAmazon · ONSITE INTERVIEW
- Maximum Non-Adjacent Coins in Two RowsKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
- Longest Increasing Path in a MatrixNew Relic · PHONE SCREEN · ONSITE INTERVIEW
- Longest Increasing Path in a MatrixVisa · ONSITE INTERVIEWVisa interview questions
- Maximal Rectangle in a Binary MatrixGoogle · ONSITE INTERVIEWGoogle interview questions
- Dungeon HealthGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- DSA Round: Maximum Score Grid PathOpenAI · ONSITE INTERVIEWOpenAI interview questions
- Longest Decreasing Matrix Path with Limited RelaxationsDuolingo · ONSITE INTERVIEWDuolingo interview questions
- Longest Increasing Path in a MatrixDoorDash · ONSITE INTERVIEWDoorDash interview questions
- Maximum All-Ones Square Side LengthOmnissa · ONSITE INTERVIEWOmnissa interview questions