Array Left Rotation

See the original problem on HackerRank.

Solutions

A tradeoff of this problem is about using a temporary array or not. In the latter case, the steps to do are simpler because we can just copy the two parts the array: all the elements before the rotation point and then all the element after.

Here is a Java implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
public static int[] rotateArray(int[] arr, int d)
{
    int n = arr.length;

    int[] rotated = new int[n]; 

    // Copy segments of shifted elements to rotated array:
    System.arraycopy(arr, d, rotated, 0, n - d);
    System.arraycopy(arr, 0, rotated, n - d, d);
    return rotated;
}

Here is an interesting solution using Linq in C#, by Emanuele Prato:

1
2
3
4
5
6
static int[] leftRotation(int[] a, int d) 
{
    int[] array1 = a.Take(d).Reverse().ToArray(); 
    int[] array2 = a.Skip(d).Take(a.Length - d + 1).Reverse().ToArray(); 
    return array1.Concat(array2).Reverse().ToArray(); 
}

Doing the roation in-place is more challenging.

First of all, you may have noticed that “cheating” is possible by allocating the final array and then reading the elements in the final positions - by Roberto Melis:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
vector<int> values(n);
// reading to 'd'
for (int i = 0; i < d; ++i)
{
    cin >> values[n-d+i];
}
// reading from 'd' to the end
for (int i = 0; i < n-d; ++i)
{
    cin >> values[i];
}

for (auto & v : values)
{
    cout << v << " ";
}

The problem of rotation can be solved by doing a “reverse” operation three times. Here is the core part, by Roberto Melis:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
vector<int> values(n);
copy_n(istream_iterator<int>(cin), n, begin(values));

auto swap = [&values](int from, int to)
{
    for (int i = from; i < from+(to-from)/2; ++i)
        std::swap(values[i], values[to-1-(i-from)]);
};

swap(0, d);
swap(d, n);
swap(0, n);

copy(begin(values), end(values), ostream_iterator<int>(cout, " "));

swap can be rewritten in terms of std::reverse:

1
2
3
4
5
6
7
8
vector<int> values(n);
copy_n(istream_iterator<int>(cin), n, begin(values));

reverse(begin(v), begin(v)+d);
reverse(begin(v)+d, end(v));
reverse(begin(v), end(v));

copy(begin(values), end(values), ostream_iterator<int>(cout, " "));

Actually, in C++ we can replace the whole logic with std::rotate:

1
2
3
4
5
6
7
8
int d;
cin >> d >> d;
vector<int> v{istream_iterator<int>(cin), istream_iterator<int>()};
if (d != v.size())
{
    rotate(begin(v), begin(v)+d, end(v));
}
copy(begin(v), end(v), ostream_iterator<int>(cout, " "));

Anyway, this problem is instructive. We can try rolling our own implementation of array rotation or understand that it’s possible to use three calls to reverse.

We've worked on this challenge in these gyms: modena 
comments powered by Disqus