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

This is not so memory efficient but it is easy to read by using Queue:

 public void Rotate(int[] nums, int k) {
    Queue<int> numbers = new Queue<int>();
    int n = nums.Length;
    k = k%n;
    int start = n - k;
    for (var i = 0; i < nums.Length; i++)
    {
        numbers.Enqueue(nums[(start+i)%n]);
    }
    
    for (var i = 0; i < nums.Length; i++)
    {
        nums[i] = numbers.Dequeue();
    }
}    

Answer 2

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

For example, if the array arr of size n were shifted to the left 3 places then we'd store shift=3. Then, when asked to access the shifted arr at index i, we instead access the unshifted arr at index (i + shift) % n.

This behaves identically to a shifted array, but because we're applying shifts to the index rather than physically shifting every cell of the array, it takes constant O(1) time instead of linear O(n).

Answer 3

Here is an in-place Rotate implementation of a trick posted by גלעד ברקן in another question. The trick is:

Example, k = 3:

1234567

First reverse in place each of the two sections delineated by n-k:

4321 765

Now reverse the whole array:

5671234

My implementation, based on the Array.Reverse method:

/// <summary>
/// Rotate left for negative k. Rotate right for positive k.
/// </summary>
public static void Rotate<T>(T[] array, int k)
{
    ArgumentNullException.ThrowIfNull(array);
    k = k % array.Length;
    if (k < 0) k += array.Length;
    if (k == 0) return;
    Debug.Assert(k > 0);
    Debug.Assert(k < array.Length);

    Array.Reverse(array, 0, array.Length - k);
    Array.Reverse(array, array.Length - k, k);
    Array.Reverse(array);
}

Live demo.

Output:

Array: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
Rotate(5)
Array: 8, 9, 10, 11, 12, 1, 2, 3, 4, 5, 6, 7
Rotate(-2)
Array: 10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8, 9

Answer 4

public static void Rotate(int[] arr, int steps)
    {
        for (int i = 0; i < steps; i++)
        {
            int previousValue = arr[arr.Length - 1];
            for (int j = 0; j < arr.Length; j++)
            {
                int currentValue = arr[j];

                arr[j] = previousValue;
                previousValue = currentValue;
            }
        }
    }

Answer 5

    // using the same same array, and only one temp variable
    // shifting everything several times by one
    // works, simple, but slow
    public static int[] ArrayRotateLeftCyclical(int[] a, int shift)
    {
        var length = a.Length;

        for (int j = 0; j < shift; j++)
        {
            int t = a[0];
            for (int i = 0; i < length; i++)
            {
                if (i == length - 1)
                    a[i] = t;
                else
                    a[i] = a[i + 1];
            }
        }

        return a;
    }

Answer 6

    // fast and beautiful method
    // reusing the same array
    // using small temp array to store replaced values when unavoidable
    // a - array, s - shift 
    public static int[] ArrayRotateLeftWithSmallTempArray(int[] a, int s)
    {
        var l = a.Length;
        var t = new int[s]; // temp array with size s = shift

        for (int i = 0; i < l; i++)
        {
            // save cells which will be replaced by shift
            if (i < s)
                t[i] = a[i];

            if (i + s < l)
                a[i] = a[i + s];
            else
                a[i] = t[i + s - l];
        }

        return a;
    }

https://github.com/sam-klok/ArraysRotation

Answer 7

It's very straight forward answer. Main thing is how you choose the start index.

    public static List<int> rotateLeft(int d, List<int> arr) {
        int n = arr.Count;
        List<int> t = new List<int>();
        int h = d;

        for (int j = 0; j < n; j++)
        { 
            if ((j + d) % n == 0)
            {
                h = 0;
            }
           
            t.Add(arr[h]);
            h++;
        } 

        return t;
    }

using this code, I have successfully submitted to hacker rank problem,

Answer 8

If you take a look at constrains you will see that d <= n (number of rotations <= number of elements in array). Because of that this can be solved in 1 line.

static int[] rotLeft(int[] a, int d)
{
    return a.Skip(d).Concat(a.Take(d)).ToArray();
}

Answer 9

what about this?

 public static void RotateArrayAndPrint(int[] n, int rotate)
    {
         for (int i = 1; i <= n.Length; i++)
        {
            var arrIndex = (i + rotate) > n.Length ? n.Length - (i + rotate) : (i + rotate);
            arrIndex = arrIndex < 0 ? arrIndex * -1 : arrIndex;
            var output = n[arrIndex-1];
            Console.Write(output + " ");
        }
    }

Answer 10

O(1) space, O(n) time solution

I think in theory this is as optimal as it gets, since it makes a.Length in-place swaps and 1 temp variable swap per inner loop.

However I suspect O(d) space solutions would be faster in real life due to less code branching (fewer CPU command pipeline resets) and cache locality (mostly sequential access vs in d element steps).

static int[] RotateInplaceLeft(int[] a, int d)
{
    var swapCount = 0;

    //get canonical/actual d    
    d = d % a.Length;
    if(d < 0) d += a.Length;
    if(d == 0) return a;

    for (var i = 0; swapCount < a.Length; i++) //we're done after a.Length swaps
    {
        var dstIdx = i; //we need this becasue of ~this: https://youtu.be/lJ3CD9M3nEQ?t=251 
        var first = a[i]; //save first element in this group

        for (var j = 0; j < a.Length; j++)
        {
            var srcIdx = (dstIdx + d) % a.Length;
            if(srcIdx == i)// circled around 
            {
                a[dstIdx] = first;
                swapCount++;
                break; //hence we're done with this group
            }
            a[dstIdx] = a[srcIdx];
            dstIdx = srcIdx;
            swapCount++;
        }
    }
    return a;
}

Answer 11

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 12

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 13

An old question, but I thought I'd add another possible solution using just one intermediate array (really, 2 if you include the LINQ Take expression). This code rotates to right rather than left, but may be useful nonetheless.

public static Int32[] ArrayRightRotation(Int32[] A, Int32 k)
    {
        if (A == null)
        {
            return A;
        }

        if (!A.Any())
        {
            return A;
        }

        if (k % A.Length == 0)
        {
            return A;
        }

        if (A.Length == 1)
        {
            return A;
        }

        if (A.Distinct().Count() == 1)
        {
            return A;
        }

        for (var i = 0; i < k; i++)
        {
            var intermediateArray = new List<Int32> {A.Last()};
            intermediateArray.AddRange(A.Take(A.Length - 1).ToList());
            A = intermediateArray.ToArray();
        }

        return A;
    }

Answer 14

Take the Item at position 0 and add it at the end. remove the item at position 0. repeat n times.

List<int> iList = new List<int>(); 

    private void shift(int n)
    {
        for (int i = 0; i < n; i++)
        {
            iList.Add(iList[0]);
            iList.RemoveAt(0);
        }


    }

Answer 15

Hope this helps.

public static int[] leftrotation(int[] arr, int d)
    {

        int[] newarr = new int[arr.Length];
        var n = arr.Length;
        bool isswapped = false;
        for (int i = 0; i < n; i++)
        {
            int index = Math.Abs((i) -d);
            if(index == 0)
            {
                isswapped = true;
            }

            if (!isswapped)
            {
                int finalindex = (n) - index;
                newarr[finalindex] = arr[i];
            }
            else
            {
                newarr[index] = arr[i];
            }
        }
        return newarr;
    }

Answer 16

This problem can get a bit tricky but also has a simple solution if one is familiar with Queues and Stacks. All I have to do is define a Queue (which will contain the given array) and a Stack. Next, I just have to Push the Dequeued index to the stack and Enqueue the Popped index in the Queue and finally return the Queue. Sounds confusing? Check the code below:

static int[] rotLeft(int[] a, int d) {

    Queue<int> queue = new Queue<int>(a);
    Stack<int> stack = new Stack<int>();

    while(d > 0)
    {
        stack.Push(queue.Dequeue());
        queue.Enqueue(stack.Pop());
        d--;            
    }

    return queue.ToArray();
}

Answer 17

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 18

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

Answer 19

Let's say if I have a array of integer 'Arr'. To rotate the array 'n' you can do as follows:

static int[] leftRotation(int[] Arr, int n)
{
    int tempVariable = 0;
    Queue<int> TempQueue = new Queue<int>(a);
      for(int i=1;i<=d;i++)
       {
           tempVariable = TempQueue.Dequeue();
           TempQueue.Enqueue(t);
    }

    return TempQueue.ToArray();`
}

Let me know if any comments. Thanks!

Answer 20

I have also tried this and below is my approach... Thank you

public static int[] RotationOfArray(int[] A, int k)
  {
      if (A == null || A.Length==0)
          return null;
      int[] result =new int[A.Length];
      int arrayLength=A.Length;
      int moveBy = k % arrayLength;
      for (int i = 0; i < arrayLength; i++)
      {
          int tmp = i + moveBy;
          if (tmp > arrayLength-1)
          {
              tmp =  + (tmp - arrayLength);
          }
          result[tmp] = A[i];             
      }        
      return result;
  }

Answer 21

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 22

This will use less memory in most cases as the second array is only as big as the shift.

public static void Main(string[] args)
{
    int[] n = { 1, 2, 3, 4, 5 };
    LeftShiftArray(n, 4);
    Console.WriteLine(String.Join(",", n));
}

public static void LeftShiftArray<T>(T[] arr, int shift)
{
    shift = shift % arr.Length;
    T[] buffer = new T[shift];
    Array.Copy(arr, buffer, shift);
    Array.Copy(arr, shift, arr, 0, arr.Length - shift);
    Array.Copy(buffer, 0, arr, arr.Length - shift, shift);
}