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


  • 1

    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

Log in to reply
 

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