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());
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
.