My O(1) space JAVA solution


  • 0
    Q
    public class Solution {
      public int calculateMinimumHP(int[][] dungeon) {
    		int width = dungeon.length;
    		int height = dungeon[0].length;
    		
    		for (int i = width-1;i>=0;i--){
    			for (int j = height-1;j>=0;j--){
    				if (i==width-1 && j==height-1){
    					dungeon[i][j] = dungeon[i][j]>0?1:1-dungeon[i][j];
    				}
    				else if (j==height-1){
    					int result = dungeon[i+1][j]-dungeon[i][j];
    					dungeon[i][j] = result>0?result:1;
    				}
    				else if (i==width-1){
    					int result = dungeon[i][j+1]-dungeon[i][j];
    					dungeon[i][j] = result>0?result:1;
    				}
    				else{
    					int result1 = dungeon[i][j+1]-dungeon[i][j];
    					int result2 = dungeon[i+1][j]-dungeon[i][j];
    					int result = Math.min(result1, result2);
    					dungeon[i][j] = result>0?result:1;
    				}
    			}
    		}
    		return dungeon[0][0];
        }
    }

  • 0
    S

    why you said it is O(1),not O(n^2)???


  • 0
    Q

    O(1) space obviously


  • 0
    M

    he didn't use extra space than input so it is O(1)


Log in to reply
 

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