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?

Fable

@FirstStep post and pre increment only really make a difference when assigning the result. – Wounded

@Wounded 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 – Gratt

Sounds like a CodinGame contest ;-) – Uri

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; } github.com/sam-klok/ArraysRotation – Keneth

Answer 1

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

Alforja

Maybe we can solve this problem without using arr ? – Fable

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. – Rear

@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]... – Tunnel

@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. – Alforja

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. – Nitid

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).

Coenobite

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 ...) – Pulverable

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

Daukas

why don't just use queue.Enqueue(queue.Dequeue()); ? – Footstep

It's a neat trick but worth mentioning that this triples the memory requirements. – Frei

The user did specifically mention that they looking for a solution with less memory usage. – Arium

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 } 

Harkness

Answer 5

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

Parental

Answer 6

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

Schlep

Answer 7

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

Disenthrall

Answer 8

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

}

Holo

While this code may answer the question, providing information on how and why it solves the problem improves its long-term value – Pavonine

That is the same code as the question, with the same problem - it requires double the space of the original array. – Sociable

Answer 9

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

Prurient

Answer 10

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


    }

Favien

Answer 11

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

Contrasty

Answer 12

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

Carlsen

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. – Sociable

Answer 13

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

Harriot

Answer 14

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

Keneth

Answer 15

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

Downtrend

Answer 16

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!

Gonfanon

Doesn't compile. There is no a or t defined anywhere. Maybe you should revise your solution. – Lunkhead

Answer 17

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

Tunnel

Answer 18

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

Ordinal

Answer 19

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,

Dandle

Answer 20

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

Keneth

Answer 21

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

Karakoram

Answer 22

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

Preemption