Why the code gives wrong answer in OJ?


  • 1
    N

    This is my code for triangle problem:

    class Solution {
    public:
        int min(int a, int b ){
            if( a<b)    return a;
            return b;
        }
        int minimumTotal(vector<vector<int> > &triangle) {
            if( triangle.size() == 1 )   return triangle[0][0];
            int i, j, left, top, minSum = INT_MAX, height = triangle.size(), width;
            for( i=1; i<height; i++){
                width = triangle[i].size();
                for( j=0; j<width; j++){
                    left = (j>0)? triangle[i-1][j-1]: INT_MAX;
                    top = triangle[i-1][j-1];
                    triangle[i][j] += min(top, left);
                }
            }
            width = triangle[height-1].size();
            for( i=0; i<width; i++){
                if( minSum > triangle[height-1][i])
                    minSum = triangle[height-1][i];
            }
            return minSum;
        }
    };
    

    For the input:

    [[1],[2,3]]

    the output given by the program is 4. The correct answer is 3. However, the code works on my machine. What is going wrong?


  • 0
    W

    I have the same problem with Python.

    My computer generates the correct answer, while OJ generates the wrong one.


  • 0
    N

    Found the error. The top element is present at the index triangle[i-1][j]. Also an initial check for empty triangle should be done. I am posting the correct solution:

    class Solution {
    public:
        int minimumTotal(vector<vector<int> > &triangle) {
            int rows = triangle.size();
            if( rows == 0 )  return 0;
            if( rows ==  1 )    return triangle[0][0];
            int i, j, left, top, cols, minimum = INT_MAX;
            for( i=1; i<rows; i++ ){
                for( j=0; j<=i; j++ ){
                    left = (j>0)? triangle[i-1][j-1]: INT_MAX;
                    top = (j<i)? triangle[i-1][j]: INT_MAX;
                    triangle[i][j] += min(left, top);
                }
            }
            cols = triangle[rows-1].size();
            for( i=0; i<cols; i++)
                minimum = min(minimum, triangle[rows-1][i]);
            return minimum;
        }
    };

  • 0
    N

    Check the above answer. If it doesn't help, then post your code.


Log in to reply
 

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