I wrote this algorithm to rotate elements in an array. It's not very efficient, but it works. It has another disadvantage that it doesn't rotate right (it would be nice to pass it negative steps, for example).

def rotate_left!(array, steps = 1)
  for i in 0...steps
    first = array[0]
    for j in 1...array.size
      array[j - 1] = array[j]
    array[-1] = first

An aside, does this count as \$O(n^2)\$? For each step, we have to iterate over the entire array and shift positions by -1.

Let \$A\$ be the size of the array, \$S\$ be the steps, and \$C\$ be the constant operations of storing the first element then adding it to the end of the array.

$$ T(A, S) = S(A) + S(2C) $$

This notation is ad-hoc, so excuse me if it doesn't make sense.

I am aware of array#rotate, and of array#shift and array#pop. For example:

def my_rotate!(array, steps = 1)
  for i in 1..steps
# or 

But I'm curious if there are other ways that rely less on Array instance methods.

  • \$\begingroup\$ The last expression could also written as array.push(*array.shift(steps)). \$\endgroup\$
    – sschmeck
    Apr 13, 2016 at 3:40

2 Answers 2


Your algorithm is \$O(N*M)\$ where:
\$N\$ = size of array
\$M\$ = steps

It's possible to do an array rotation that's \$O(N)\$, regardless of the number of steps you specify though.

Start by thinking of the array as two pieces, separated at "steps" indices into the array. For example, if you're going to rotate by 4, then mentally separate it into array[1..5] and array[5..N].

To do the rotation, start by reversing each of those pieces. Then reverse the entire array, something on this order:

for j in 1...steps/2
    temp = array[j]
    array[j] = array[steps-j+1]
    array[steps-j+1] = temp

for k in 1...(array.size-steps)/2
    temp = array[steps+k]
    array[steps+k] = array[array.size-k+1]

for i in 1...array.size
    temp = array[i]
    array[i] = array[array.size-i+1]
    array[array.size-i+1] = temp

Note: I'm more accustomed to C-style arrays, where indexes start at 0 instead of 1. I've tried to compensate appropriately, but I haven't tested this, so I wouldn't be surprised if there were still a few off-by-one errors.

This steps through the entire array twice, regardless of the size of rotation, so it's likely to be slower than yours for steps=1, about the same speed for steps = 2, and faster for steps > 2.

  • \$\begingroup\$ Thanks. I will implement your method and check back. Ruby arrays also start at 0 index. ... is exclusive range notation, so it saves me from having to do 0..array.size - 1 (notice 2 dots instead of 3). \$\endgroup\$
    – Mohamad
    Apr 9, 2016 at 14:12
  • \$\begingroup\$ Does my notation of \$T(A,S)=S(A)+S(2C)\$ make sense? Or is it nonsense? \$\endgroup\$
    – Mohamad
    Apr 9, 2016 at 14:13
  • \$\begingroup\$ @Mohamad: I guess it makes at least reasonable sense. \$\endgroup\$ Apr 9, 2016 at 14:14
  • \$\begingroup\$ Ruby array are indexed from 0, as in C, but Ruby arrays also support negative indexes, which count backwards from the end. \$\endgroup\$ Apr 9, 2016 at 19:24
  • \$\begingroup\$ Ok, I went back to basics are looked at how we reverse and rotate arrays, and I was able to understand and implement your version. It's in this Gist. I was also able to see that my own implementation was needlessly complex. I could have used array[i] = array[i + 1] (instead of array[j - 1] = array[j]) had I started my iteration at 0 instead of 1, which is easier to digest. \$\endgroup\$
    – Mohamad
    Apr 9, 2016 at 20:12

I was not able to get @Jerry Coffin's particular implementation to work, but I used his idea to create this similar \$O(n)\$ implementation.

As he describes, we reverse the array at \$A[0..S-1]\$ and \$A[S..N-1]\$, where \$S\$ is steps and \$N\$ is the length of the array. We then reverse the entire array.

def array_rotate!(array, steps)
  for i in 0...steps / 2
    temp = array[i]
    array[i] = array[steps - i - 1]
    array[steps - i - 1] = temp

  for j in steps...(array.size + steps) / 2
    temp = array[j]
    array[j] = array[array.size - 1 - (j - steps)]
    array[array.size - 1 - (j - steps)] = temp

  for k in 0...array.size / 2
    temp = array[k]
    array[k] = array[array.size - 1 - k]
    array[array.size - 1 - k] = temp

a = [*"a".."e"]
array_rotate!(a, 3)
puts a.inspect
#=> ["d", "e", "a", "b", "c"]

To illustrate this technique: Given %w[a b c d e] and \$S = 3\$ and \$5\$:

  1. We reverse \$A[0..S-1]\$: %w[c b a d e]
  2. We reverse \$A[S..N-1]\$: %w[c b a e d]
  3. We reverse the entire array \$A[0..N-1]\$: %w[d e a b c]

This still can't rotate in both directions.

a = [*"a".."e"]
array_rotate!(a, -2)
puts a.inspect
#=> ["e", "d", "a", "b", "c"]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.