CODEWITHSUNDEEP
c++c++11c++17
Sma
Sma

Reputation: 41

Why does my program keep on giving me heap buffer overflow even though I am not going out of bounds on my array or overwriting any values

I am trying to solve Leetcode problem 746 which is a basic Dynamic programming problem. Even though my logic is little complex, it should work perfectly fine. I have had 2 sleepless nights trying to find what the problem in my code is. Can someone point exactly where am I doing heap overflow and how to avoid it ?

Also, I forgot to add, the size of cost is always greater than 3.

I have already tried inserting comments into my solution. I have realized that the problem lies with the costing[1] updating code but what the problem is, I have no idea.

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        if(cost.size() < 3)
            return 0;

        int costing[2];
        costing[0]=cost[0];
        costing[1]=cost[1];
        int i=1;
        while(i<cost.size()-2)
        {
                if(costing[0]+cost[i]>costing[0]+cost[i+1])
                {
                    costing[0]=costing[0]+cost[i+1];
                    i++;
                }

                else if (costing[0]+cost[i]<=costing[0]+cost[i+1])
                {
                    costing[0]=costing[0]+cost[i];
                    i+=2;
                }

                if(costing[1]+cost[i+1]>=costing[1]+cost[i+2])
                {
                    cout<<costing[1]+cost[i+1]<<"is greater than " <<costing[1]+cost[i+2]<<"\n";
                    costing[1]+=cost[i+2];
                    i+=2;
                }

                else if (costing[1]+cost[i+1]<costing[1]+cost[i+2])
                {
                                    cout<<costing[1]+cost[i+1]<<"is less than " <<costing[1]+cost[i+2]<<"\n";

                costing[1]+=cost[i+1];
                    i++;
                }
        }

        return min(costing[0],costing[1]);
    }
};

Upvotes: 3

Views: 245

Answers (2)

Wolf
Wolf

Reputation: 10238

Couldn't it be that your heap has not enough space? Vector allocate continuous memory blocks on the heap. If a vector grows for a long time, the heap may get fragmented. So at some point there is no free block available.

Maybe using std::vector::reserve can help you prevent this behaviour.

Also keep in mind that the indexed access ([i]) to vectors doesn't include range checking as opposed to the at function.

Upvotes: 0

P.W
P.W

Reputation: 26800

The initial value of i is 1. It can increment by 4 in one iteration of the while under different conditions (if the first else if and the second if are true).

So in the second iteration of the while, the value of i can become 9.

So in the last else if, cost[i+2] is cost[11]. Since your dataset has only 10 elements (as mentioned in the comment), this results in an out-of-bounds access.

Upvotes: 3

Related Questions