# Array rotation in C++

Posted on

Problem

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

Solution

# 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());
}
``````

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`.