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

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 2

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 3

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 4

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 5

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 6

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