# Why the code gives wrong answer in OJ?

• 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?

• I have the same problem with Python.

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

• 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;
}
};``````

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

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