abort called is showing in Hackerrank

Question

I was solving a problem of the array in which I have to do a left rotation of an array. wrote the code and submit successfully some test cases passed in some it showing abort called I don't know whats the problem. I googled it shows it's due to storage becomes full. what if I declare my temp array in heap. would it make any difference? forgive me for my indentation.

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

vector<int> rotateLeft(int d, vector<int> arr) {
    vector<int> temp(d);

    for (int i = 0; i < d; i++) {
        temp[i] = arr[i];
    }
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = arr[d + i];
    }
    for (int i = 0; i < arr.size(); i++) {
        arr[arr.size() - d + i] = temp[i];
    }
    return arr;
}

int main() {
    ofstream fout(getenv("OUTPUT_PATH"));

    string first_multiple_input_temp;
    getline(cin, first_multiple_input_temp);

    vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));

    int n = stoi(first_multiple_input[0]);

    int d = stoi(first_multiple_input[1]);

    string arr_temp_temp;
    getline(cin, arr_temp_temp);

    vector<string> arr_temp = split(rtrim(arr_temp_temp));

    vector<int> arr(n);

    for (int i = 0; i < n; i++) {
        int arr_item = stoi(arr_temp[i]);

        arr[i] = arr_item;
    }

    vector<int> result = rotateLeft(d, arr);

    for (int i = 0; i < result.size(); i++) {
        fout << result[i];

        if (i != result.size() - 1) {
            fout << " ";
        }
    }

    fout << "\n";

    fout.close();

    return 0;
}

string ltrim(const string & str) {
    string s(str);

    s.erase(s.begin(), find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace))));

    return s;
}

string rtrim(const string & str) {
    string s(str);

    s.erase(find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(), s.end());

    return s;
}

vector<string> split(const string & str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}

Answer 1

The problem is in your 3 loops:

    for (int i = 0; i < d; i++) {
        temp[i] = arr[i];
    }
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = arr[d + i];
    }
    for (int i = 0; i < arr.size(); i++) {
        arr[arr.size() - d + i] = temp[i];
    }

first loop will crash if d > n. It can be the case that your task may have d > n sometimes.

Second loop should crash always when d > 0, because arr[d + i] is out of bounds if d + i >= arr.size() which will always happen because loop is until i < arr.size().

Third loop will also always crash because out of bounds. For example if d == 1 and i == arr.size() - 1 then you get arr[arr.size() - 1 + arr.size() - 1] which is out of bounds.

Also you have to watch if d > n in some tests, then you have to make d %= n;.

Also just a notice - inputs of most HackerRank problems can be read using just things like int i = 0; std::cin >> i; and loops. No need for strings operations like stoi/ltrim/rtrim/split. For example to read array of n numbers, provided as one or several lines of input, you can do:

std::vector<int> nums;
for (size_t i = 0; i < n; ++i) {
    int i = 0;
    std::cin >> i;
    nums.push_back(i);
}

You can use just standard std::rotate to rotate array left.

One interesting way to solve the problem in O(N) time and O(1) extra memory without std::rotate and std::reverse functions and without temporary storage is to reverse order of first d elements, then reverse order of last n - d elements, then reverse whole array. Of cause usually you just use std helpers, but sometimes you want to implement algorithms from scratch. I.e. something like following:

void reverse(int * begin, int * end) {
    --end;
    while (begin < end)
        std::swap(*begin++, *end--);
}
void rotate(int * begin, int * end, int d) {
    d %= (end - begin);
    reverse(begin, begin + d);
    reverse(begin + d, end);
    reverse(begin, end);
}

---

The shortest way to fix your algorithm (it takes O(N) time and O(N) extra memory) to make it work is:

vector<int> rotateLeft(int d, vector<int> arr) {
    d %= arr.size();
    vector<int> temp(d);

    for (int i = 0; i < d; i++) {
        temp[i] = arr[i];
    }
    for (int i = 0; i < arr.size() - d; i++) {
        arr[i] = arr[d + i];
    }
    for (int i = 0; i < d; i++) {
        arr[arr.size() - d + i] = temp[i];
    }
    return arr;
}