Simple C++ Solution with O(1) space complexity


  • 3
    J
    class Solution {
    public:
    int calculateMinimumHP(vector<vector<int>>& dungeon) {
    	int m = dungeon.size() - 1;
    	int n = dungeon[0].size() - 1;
    
    	dungeon[m][n] = dungeon[m][n]>0 ? 0 : dungeon[m][n];
    
    	for (int i = m; i >= 0; i--) {
    		for (int j = n; j >= 0; j--) {
    			if (i < m && j < n)
    				dungeon[i][j] = max(dungeon[i + 1][j], dungeon[i][j + 1]) + dungeon[i][j];
    			else if (i < m)
    				dungeon[i][j] = dungeon[i + 1][j] + dungeon[i][j];
    			else if (j < n)
    				dungeon[i][j] = dungeon[i][j + 1] + dungeon[i][j];
    
    			dungeon[i][j] = dungeon[i][j] > 0 ? 0 : dungeon[i][j];
    		}
    	}
    
    	return dungeon[0][0] > 0 ? 1 : abs(dungeon[0][0]) + 1;
      }
    };

  • 0
    H

    Very concise code!
    Could you explain dungeon[i][j] = dungeon[i][j] > 0 ? 0 : dungeon[i][j]; and your idea for me?


  • 0
    J

    Each element of dungeon[][] after running this function indicates how much HP is needed to get bottom-right. If dungeon[i][j] is larger than 0, this means that we don't need additional HP from dungeon[i][j] to bottom-right. That's why I set 0 to dungeon[i][j] when it is larger than 0.


  • 0
    M

    Gives wrong answer!


  • 0
    J

    Hmm... I just tested the code, but it is well accepted.


  • 0
    L

    It is interesting, however I would never think this as O(1) space solution cuz you just modified the input matrix.


Log in to reply
 

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