3
\$\begingroup\$

I am completely new to data structures and algorithms. I tried this problem on hackerank. I got the desired output but my code wasn't efficient enough to execute in the given time limit.

How can I optimise my code? Is it proper way to solve this problem?

Question:

A left rotation operation on an array of size shifts each of the array's elements unit 1 to the left. Given an integer,d, rotate the array that many steps left and return the result. The first line contains two space-separated integers that denote n, the number of integers, and d, the number of left rotations to perform. The second line contains n space-separated integers that describe the array

My code:

    #include<iostream>
#include<vector>
#include<algorithm>

//function to rotate an array to the left
void rotate_left(std::vector<int> &arr)
{
    int next = arr.back(), temp;
    arr.back() = arr[0];
    for (int i = (int)arr.size() - 2; i >= 0; i--)//for the last but one
    {
        temp = arr[i];//storing the value of current variable 
        arr[i] = next;//taking the next element i.e i+1
        next = temp;
    }
    
}

int main()
{
    int n,d, input;
    if (std::cin >> n >> d)
    { }
    else
    {
        std::cerr << "failed to read input "<<"\n";
        return EXIT_FAILURE;
    }

    std::vector<int> a;
    for (int i = 0; i < n; i++)
    {
        if (std::cin >> input)
        {
            a.push_back(input);
        }
        else
        {
            std::cerr << "failed to read input " << "\n";
            return EXIT_FAILURE;
        }
    }
    //calling the function
    for (int i = 0; i < d; i++)
    {
        rotate_left(a);
    }
    for (auto output : a)
    {
        std::cout << output <<" ";
    }
    
    return 0;
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Have you tried not changing the vector at all, just outputting the expected values? \$\endgroup\$
    – D. Jurcau
    Mar 17 at 20:31

1 Answer 1

5
\$\begingroup\$

Simplify the code

Your code is more complex than necessary for just rotating an array by one element. You don't have to special-case swapping the first and last elements, and I would also use std::swap():

void rotate_left(std::vector<int> &arr) {
    for (std::size_t i = 0; i < arr.size() - 1; ++i) {
         std::swap(arr[i], arr[i + 1]);
    }
}

Of course, you could also just use std::rotate() to rotate the array for you.

Optimizing the code

If you need to rotate by more than 1 position, then calling rotate_left() multiple times is going to be slow, especially for large values of d. The best way is to try to move each element into the right place in one go. One way to do move elements in the range [d, arr.size()) to the start of the array, and then move [0, d) to the end. You need to first make a copy of the range [0, d), otherwise it will be overwritten by the first move. So:

void rotate_left_by(std::vector<int> &arr, std::size_t d) {
    std::vector<int> head(arr.begin(), arr.begin() + d);
    auto tail_begin = std::copy(arr.begin() + d, arr.end(), arr.begin());
    std::copy(head.begin(), head.end(), tail_begin);
}

Here I used the constructor of std::vector to make a copy of the head of the original input, then I use std::copy() to move the tail of the original input to the front of the array. The return value of std::copy() is the iterator right past the end of the copied area, so you can use that to copy the original head to the tail without having to do any further iterator arithmetic. Note the similarity in structure to how you swapped elements in your for-loop.

As vnp mentioned in the comments, it is also be possible to do an arbitrary rotation without needing a temporary vector to store elements. Such an algorithm can be useful if you have a limited amount of memory.

Also, when reading the elements of the array from standard input, you know the number of elements you want to read. It's then good practice to call reserve() on the vector you are going to push_back() to, in order to avoid unnecessary memory reallocations.

But as D. Jurcau mentioned, even better is not having to manipulate the array itself, just store it and then print it out in a rotated order. Actually, you don't need to store the whole array to begin with, you just need to store d elements in a std::vector: first read d elements into that vector, then for the rest of the input just copy it straight to the output. After finishing processing the input, just print the contents of the vector.

Use std::size_t for sizes, counters and indices

An int might not be big enough to be able to represent all sizes and all possible indices into containters. The right type to use is std::size_t. Do this consistently, this way you also avoid having to cast things to int just to prevent compiler warnings.

Error handling

There are some issues with your code when it comes to error handling. What if the input array has length 0? Also, my example rotate_left_by() function will probably crash if the input array is shorter than d. It's always good to check if your code handles all the edge cases correctly.

You are checking whether reading from std::cin succeeded, which is great! However, if you really want to be correct, you might also want to check that writing to std::cout also succeeded, and if not return EXIT_FAILURE. This is especially important for programs that are running unattended, or are part of a pipeline, as the output might not be visible, and the exit code is the only thing able to signal that things went wrong.

Make it more generic

Your code works only on std::vector<int>. It would be nice to have a function that can rotate arbitrary containers. It might be good practice to try to implement std::rotate() yourself, and make it work not only for random access containers like std::vector, but also for things like std::list.

\$\endgroup\$
2
  • \$\begingroup\$ (1) Resorting to swap is suboptimal; it makes each item to be moved twice. Moving once is enough. (2) Copying the left part into head incurs the linear space complexity. There are at least two ways to rotate in-place. \$\endgroup\$
    – vnp
    Mar 17 at 23:50
  • \$\begingroup\$ (1) I'm kind of hoping the compiler will see that part of the swap of the previous iteration will be reused in the current iteration, but I didn't verify. (2) Yes, that's true, but it's relatively simple to implement and if you only care about performance and not memory usage, it's probably fine? \$\endgroup\$
    – G. Sliepen
    Mar 18 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.