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?

@FirstStep post and pre increment only really make a difference when assigning the result. — juharr, Jul 20 '16 at 13:34
@juharr I thought "_Given that i++ needs to remember the old value of i after incrementing, I think ++i may be shorter_" From reading comments in [**Post-increment and pre-increment within a 'for' loop produce same output**](http://stackoverflow.com/questions/4706199/post-increment-and-pre-increment-within-a-for-loop-produce-same-output) — Khalil Khalaf, Jul 20 '16 at 13:36
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 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 — sam sergiy klok, Sep 29 '21 at 05:46

score 11 · Accepted Answer · answered Jul 20 '16 at 13:47

11

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

answered Jul 20 '16 at 13:47

Lorentz Vedeler

5,101
2
29
40

Maybe we can solve this problem without using `arr `? – Jul 20 '16 at 13:48
Well, you can do LeftShiftArray(n, 1); the times you need. You dont need extra memory but a lot of I/O operations are needed. – Daniel Argüelles Jul 20 '16 at 14:01
@lorentz-vedeler Hmm, it worked and seems it was pretty fast. I wonder why my approach with using temporary cell for storing first element timed out on big chunks of data... I also copied the rest of cells like a[i] = a[i + 1]... – Alexander Aug 24 '19 at 20:17
1

@Alexander: that could probably warrant its own question on codereview or stackoverflow, but in short: 1. your algorithm is O(kn) where k is the number of shifted elements and n is the length of the array. 2. Array.Copy is significantly faster than copying elements manually. 3. There's a lot of branching logic inside your loops. – Lorentz Vedeler Aug 25 '19 at 15:56
I would suggest returning `buffer` (or e new better name) from `LeftShiftArray` and writing `n=LeftShiftArray(...)`, so you can use one less `Copy`. The allocation is done anyway and replacing a reference is cheaper than a copy. – JHBonarius Aug 25 '22 at 10:19

score 9 · Answer 2 · answered Dec 16 '18 at 07:30

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

It's a neat trick but worth mentioning that this triples the memory requirements. — Good Night Nerd Pride, Aug 23 '22 at 08:20

score 8 · Answer 3 · answered Jul 21 '16 at 13:53

8

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

answered Jul 21 '16 at 13:53

Dave

7,460
3
26
39

2

This is an underrated answer! Maybe it isn't a good fit for solving this homework problem, but in production it is great! (Also similar answers to a number of other problems ...) – davidbak Aug 22 '20 at 19:47

Ivan Stoev · Answer 4 · 2016-07-21T09:04:00.060

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 }

score 2 · Answer 5 · answered May 16 '19 at 15:31

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

score 1 · Answer 6 · answered May 27 '17 at 16:26

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

score 1 · Answer 7 · answered Mar 27 '18 at 20:38

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

score 1 · Answer 8 · answered Jul 24 '18 at 21:12

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

}

While this code may answer the question, providing information on how and why it solves the problem improves its long-term value — L_J, Jul 24 '18 at 21:41
That is the same code as the question, with the same problem - it requires double the space of the original array. — NetMage, Feb 16 '22 at 01:14

Siddhanth · Answer 9 · 2019-02-18T02:06:06.603

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

score 1 · Answer 10 · answered Feb 18 '19 at 20:16

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


    }

score 1 · Answer 11 · answered Mar 10 '19 at 22:15

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

score 1 · Answer 12 · answered Nov 21 '19 at 14:29

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

YOu could improve this by replacing `break` with `else` and moving the common `++swapCount` to after the `if`. Then you could also change the `for` to `for (int i = 0, swapCount = 0;` and make it `void` since it modifies `a` in place. Finally you could make it generic. — NetMage, Feb 16 '22 at 01:40

score 1 · Answer 13 · answered Jul 15 '20 at 22:16

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

score 1 · Answer 14 · answered Sep 29 '21 at 05:53

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

score 1 · Answer 15 · answered Dec 08 '22 at 05:08

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

score 0 · Answer 16 · answered Jan 07 '18 at 21:12

0

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!

answered Jan 07 '18 at 21:12

subhendu rath

11
1

Doesn't compile. There is no a or t defined anywhere. Maybe you should revise your solution. – Volkan Paksoy Feb 08 '18 at 07:20

score 0 · Answer 17 · answered Aug 24 '19 at 20:21

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

score 0 · Answer 18 · answered Apr 01 '20 at 08:24

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 + " ");
        }
    }

score 0 · Answer 19 · answered Jun 27 '21 at 19:43

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,

score 0 · Answer 20 · answered Sep 29 '21 at 05:50

    // 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

score 0 · Answer 21 · answered Jul 15 '22 at 13:36

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

How to efficiently rotate an array?

21 Answers21

Linked

Related