How did I get a segmentation fault in this code?

Question

vector<int> cutTheSticks(vector<int> arr) {
    vector<int> res;
    vector<int>::iterator it;
    int i=0, mini=0, c=arr.size();
    while(c>0) {
        res.push_back(c);
        mini=*min_element(arr.begin(),arr.end());
        for(i=0;i<arr.size();i++) {
            arr[i]-=mini;
        }
        for(auto it=arr.begin();it!=arr.end();it++) {
            i=*it;
            if(i==0)
                arr.erase(it);
        }
        c=arr.size();
    }
    return res;
}

I am running this piece of code in the hackerank portal and not on any system.

`arr.erase(it);` and then `it++` ... Look at what happens with iterators when you `erase()` and also what `erase()` returns. — Ted Lyngmo, Jul 08 '20 at 14:06
You assign `c` before the `while(c>0) {` but never again in the loop. This will run forever, or strictly speaking, until the free memory is exceeded. — Scheff's Cat, Jul 08 '20 at 14:07
`arr.erase(it);` does that invalidate `it` ? Can you always do `it != arr.end();` and `it++;` afterwards ? — Jeffrey, Jul 08 '20 at 14:07
In addition to the problem of calling `arr.erase()` in the inner loop, if `arr` is ever emptied (i.e. which is possible as there are nested loops, one of which erases elements), `min_element()` will return an end iterator, so the assignment to `mini` will have undefined behaviour. — Peter, Jul 08 '20 at 14:10
use `it = arr.erase(it);` when erasing since the iterator becomes invalid after erasing — AndersK, Jul 08 '20 at 14:25

brc-dd · Answer 1 · 2020-07-08T15:34:20.667

The way you are using erase is causing the problem in this case. In fact, you exactly don't need a complex approach like this for the problem.

You can simply sort the array in reverse order and then use pop_back() while last element is 0. It will also help to reduce complexity as then you won't need to call min_element each time. You can directly use arr.back() for the minimum element.

Logic behind my approach:

In each iteration, you are subtracting minimum element from each element. This makes number(s) having the minimum value as 0. Clearly, since the array is sorted in reverse order, these numbers will be in the end of the array. You then want to remove these elements for which pop_back is one of the best available options.

Here is sample code:

vector<int> cutTheSticks(vector<int> arr) {
    vector<int> res;
    sort(arr.begin(), arr.end(), greater<int>());
    while (not arr.empty()) {
        res.push_back(arr.size());
        for (auto &&i : arr)
            i -= arr.back();
        while (not (arr.back() or arr.empty()))
            arr.pop_back();
    }
    return res;
}

PS:

If you want to stick with your original algorithm then replace

for (auto it = arr.begin(); it!=arr.end(); it++) {
    i = *it;
    if(i == 0)
        arr.erase(it);
}

with something like:

arr.erase(remove(arr.begin(), arr.end(), 0), arr.end()); // called as erase-remove idiom

or

for (auto it = arr.begin(); it!=arr.end(); /* it++ */) {
    i = *it;
    if(i == 0)
        it = arr.erase(it);
    else
        ++it;
}

This thread may help you: Remove elements of a vector inside the loop.

How did I get a segmentation fault in this code?

1 Answers1