How to efficiently rotate an array?

Question

Given an array of n integers and a number, d, perform left rotations on the array. Then print the updated array as a single line of space-separated integers.

Sample Input:

5 4
1 2 3 4 5

The first line contains two space-separated integers denoting the respective values of n (the number of integers) and d (the number of left rotations you must perform). The second line contains n space-separated integers describing the respective elements of the array's initial state.

Sample Output:

5 1 2 3 4

static void Main(String[] args)
{
    string[] arr_temp = Console.ReadLine().Split(' ');
    int n = Int32.Parse(arr_temp[0]);
    int d = Int32.Parse(arr_temp[1]);

    string[] arr = Console.ReadLine().Split(' ');
    string[] ans = new string[n];

    for (int i = 0; i < n; ++i)
    {
        ans[(i + n - d) % n] = arr[i];
    }

    for (int j = 0; j < n; ++j)
    {
        Console.Write(ans[j] + " ");
    }
}

How to use less memory to solve this problem?

Answer 1

Do you really need to physically move anything? If not, you could just shift the index instead.

Answer 2

I've solve the challange from Hackerrank by following code. Hope it helps.

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;

namespace ConsoleApp1
{
class ArrayLeftRotationSolver
{
    TextWriter mTextWriter;
    public ArrayLeftRotationSolver()
    {
         mTextWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

    }

    public void Solve()
    {

        string[] nd = Console.ReadLine().Split(' ');

        int n = Convert.ToInt32(nd[0]);

        int d = Convert.ToInt32(nd[1]);

        int[] a = Array.ConvertAll(Console.ReadLine().Split(' '), aTemp => Convert.ToInt32(aTemp))
        ;
        int[] result = rotLeft(a, d);

        mTextWriter.WriteLine(string.Join(" ", result));

        mTextWriter.Flush();
        mTextWriter.Close();
    }

    private int[] rotLeft(int[] arr, int shift)
    {
        int n = arr.Length;
        shift %= n;
        int[] vec = new int[n];
        for (int i = 0; i < n; i++)
        {
            vec[(n + i - shift) % n] = arr[i];
        }
        return vec;
    }

    static void Main(string[] args)
    {
         ArrayLeftRotationSolver solver = new ArrayLeftRotationSolver();
         solver.Solve();
    }
}

}

Answer 3

Isn't using IEnumerables better? Since It won't perform all of those maths, won't allocate that many arrays, etc

public static int[] Rotate(int[] elements, int numberOfRotations)
{
    IEnumerable<int> newEnd = elements.Take(numberOfRotations);
    IEnumerable<int> newBegin = elements.Skip(numberOfRotations);
    return newBegin.Union(newEnd).ToArray();
}

IF you don't actually need to return an array, you can even remove the .ToArray() and return an IEnumerable

Usage:

void Main()
{
    int[] n = { 1, 2, 3, 4, 5 };
    int d = 4;
    int[] rotated = Rotate(n,d);
    Console.WriteLine(String.Join(" ", rotated));
}

Answer 4

Actually you asked 2 questions:

How to efficiently rotate an array?

and

How to use less memory to solve this problem?

Usually efficiency and low memory usage are mutually exclusive. So I'm going to answer your second question, still providing the most efficient implementation under that memory constraint.

The following method can be used for both left (passing negative count) or right (passing positive count) rotation. It uses O(1) space (single element) and O(n * min(d, n - d)) array element copy operations (O(min(d, n - d)) array block copy operations). In the worst case scenario it performs O(n / 2) block copy operations.

The algorithm is utilizing the fact that

rotate_left(n, d) == rotate_right(n, n - d)

Here it is:

public static class Algorithms
{
    public static void Rotate<T>(this T[] array, int count)
    {
        if (array == null || array.Length < 2) return;
        count %= array.Length;
        if (count == 0) return;
        int left = count < 0 ? -count : array.Length + count;
        int right = count > 0 ? count : array.Length - count;
        if (left <= right)
        {
            for (int i = 0; i < left; i++)
            {
                var temp = array[0];
                Array.Copy(array, 1, array, 0, array.Length - 1);
                array[array.Length - 1] = temp;
            }
        }
        else
        {
            for (int i = 0; i < right; i++)
            {
                var temp = array[array.Length - 1];
                Array.Copy(array, 0, array, 1, array.Length - 1);
                array[0] = temp;
            }
        }
    }
}

Sample usage like in your example:

var array = Enumerable.Range(1, 5).ToArray(); // { 1, 2, 3, 4, 5 } 
array.Rotate(-4); // { 5, 1, 2, 3, 4 } 

Answer 5

This is my attempt. It is easy, but for some reason it timed out on big chunks of data:

        int arrayLength = arr.Length;
        int tmpCell = 0;
        for (int rotation = 1; rotation <= d; rotation++)
        {
            for (int i = 0; i < arrayLength; i++)
            {
                if (arr[i] < arrayElementMinValue || arr[i] > arrayElementMaxValue)
                {
                    throw new ArgumentException($"Array element needs to be between {arrayElementMinValue} and {arrayElementMaxValue}");
                }
                if (i == 0)
                {
                    tmpCell = arr[0];
                    arr[0] = arr[1];
                }
                else if (i == arrayLength - 1)
                {
                    arr[arrayLength - 1] = tmpCell;
                }
                else
                {
                    arr[i] = arr[i + 1];
                }
            }
        }

Answer 6

I have tried to used stack and queue in C# to achieve the output as follows:

public int[] rotateArray(int[] A, int rotate)
{
    Queue<int> q = new Queue<int>(A);
    Stack<int> s;
    while (rotate > 0)
    {
        s = new Stack<int>(q);
        int x = s.Pop();
        s = new Stack<int>(s);
        s.Push(x);
        q = new Queue<int>(s);
        rotate--;
    }
    return q.ToArray();
}