My solutions in 3 languages with O(n^2) time and O(1) space

• I use bottom-up strategy to solve this question.
Reuse the original dungeon array to store intermediate result. So these solution will modify original array.

Java:

``````public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
for (int i = dungeon.length - 1; i >= 0; i--) {
for (int j = dungeon[i].length - 1; j >= 0; j--) {
boolean rowEnd = i == dungeon.length - 1;
boolean columnEnd = j == dungeon[i].length - 1;
if (!rowEnd && !columnEnd) {
dungeon[i][j] -= Math.min(dungeon[i + 1][j], dungeon[i][j + 1]);
} else if (rowEnd ^ columnEnd) {
dungeon[i][j] -= dungeon[i + (rowEnd ? 0 : 1)][j + (columnEnd ? 0 : 1)];
}
dungeon[i][j] = dungeon[i][j] > 0 ? 0 : -dungeon[i][j];
}
}
return dungeon[0][0] + 1;
}
}
``````

C++;

``````class Solution {
public:
int calculateMinimumHP(vector<vector<int> > &dungeon) {
for (int i = dungeon.size() - 1; i >= 0; i--) {
for (int j = dungeon[i].size() - 1; j >= 0; j--) {
bool rowEnd = i == dungeon.size() - 1;
bool columnEnd = j == dungeon[i].size() - 1;
if (!rowEnd && !columnEnd) {
dungeon[i][j] -= min(dungeon[i + 1][j], dungeon[i][j + 1]);
} else if (rowEnd ^ columnEnd) {
dungeon[i][j] -= dungeon[i + (rowEnd ? 0 : 1)][j + (columnEnd ? 0 : 1)];
}
dungeon[i][j] = dungeon[i][j] > 0 ? 0 : -dungeon[i][j];
}
}
return dungeon[0][0] + 1;
}
};
``````

Python:

``````class Solution:
# @param dungeon, a list of lists of integers
# @return a integer
def calculateMinimumHP(self, dungeon):
for i in list(reversed(range(len(dungeon)))):
for j in list(reversed(range(len(dungeon[i])))):
rowEnd = i == len(dungeon) - 1
columnEnd = j == len(dungeon[i]) - 1
if not rowEnd and not columnEnd:
dungeon[i][j] -= min(dungeon[i + 1][j], dungeon[i][j + 1])
elif rowEnd ^ columnEnd:
dungeon[i][j] -= dungeon[i + (0 if rowEnd else 1)][j + (0 if columnEnd else 1)];
dungeon[i][j] = 0 if dungeon[i][j] > 0 else -dungeon[i][j]
return dungeon[0][0] + 1``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.