C Solution (4ms) with O(mn) Time and O(1) Space


  • 2
    W

    O(1) Space solution is based on if dungeon is declared as int ** but not const int **. Since each grid in dungeon is traversed through once, and it can be reused to hold the optimized cost.

    int calculateMinimumHP(int **dungeon, int m, int n)
    {
        for ( int i = m - 1; i >= 0; --i )
        {
            for ( int j = n - 1; j >= 0; --j )
            {
                if ( i == m - 1 && j == n - 1 )
                {
                    /** heheheheh */
                }
                else if ( i == m - 1 )
                {
                    /** choose cost as the minimum between current and right */
                    int right = dungeon[i][ j + 1 ];
                    if ( right < 0 )
                    {
                        dungeon[i][j] += right;
                    }
                }
                else if ( j == n - 1 )
                {
                    /** choose cost as the minimum between current and down */
                    int down = dungeon[ i + 1 ][j];
                    if ( down < 0 )
                    {
                        dungeon[i][j] += down;
                    }
                }
                else
                {
                    /** choose the optimized next cost as the maximum between right and down */
                    int right = dungeon[i][ j + 1 ];
                    int down = dungeon[ i + 1 ][j];
                    int next = ( right > down ) ? right : down;
    
                    /** choose cost as the minimum between current and next */
                    if ( next < 0 )
                    {
                        dungeon[i][j] += next;
                    }
                }
            }
        }
    
        int ret = dungeon[0][0];
        if ( ret > 0 )
        {
            return 1;
        }
        
        return -ret + 1;
    }

Log in to reply
 

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