DEV Community

Cover image for Not an "Easy" Algorithm: Rotating an Array, Three Ways

Not an "Easy" Algorithm: Rotating an Array, Three Ways

Alisa Bajramovic on June 12, 2020

Today's algorithm is the Rotate Array problem: Given an array, rotate the array to the right by k steps, where k is non-negative. Try to come up...
Collapse
 
gwutama profile image
Galuh Utama • Edited

After reading the problem, just on top of my head, this can be easily solved with a ring buffer. Best of all, it can be implemented in any language.

Collapse
 
realdolos profile image
Dolores Greatamsky

Quick and really dirty and not exactly efficient :D

function rrotate(arr, steps) {
  steps = (steps || 0) % arr.length;
  return new Proxy(arr, {
    get(target, prop) {
      const idx = typeof prop === "string" ? Number(prop) - steps : NaN;
      return Number.isInteger(idx) ?
         target[idx >= 0 ? idx : target.length + idx] :
         target[prop];
    }
   });
}

But it works (mostly)

Array.from(rrotate([1,2,3,4,5], 2))
// [4, 5, 1, 2, 3]
rrotate([1,2,3,4,5], 2).slice()
// [4, 5, 1, 2, 3]
rrotate([1,2,3,4,5], 2).forEach(e => console.log(e))
// 4
// 5
// 1
// 2
// 3
[...rrotate([1,2,3,4,5], 7)]
// [4, 5, 1, 2, 3]
for (let e of rrotate([1,2,3,4,5], 12)) console.log(e);
// 4
// 5
// 1
// 2
// 3
Collapse
 
miketalbot profile image
Mike Talbot ⭐

A good point, one of those if you knew the actual problem you'd find a way of solving it better than actually manipulating an array which feels "expensive".

 
miketalbot profile image
Mike Talbot ⭐

Glad you like it :) Honestly only do that when it matters though - I mean I write code that uses all of the slow things when I know it will not be handling lots of data because it's quicker to write and that is the important thing for the task at hand!

 
miketalbot profile image
Mike Talbot ⭐

Yeah immer.js allows you to mutate arrays and then it works out an immutable version from it. That's very cool, but still has a cost as I replied in the comments to that article with a sandbox example showing (on my machine at least) significant frame drops in some use cases.

It so happened the example I had given and then implemented in immer is a kind of kryptonite to immer.js (because it happens over multiple cycles) but yeah, I see things on DEV all the time that use spread in loops - I just think, hope no one calls that example with 1 million entries not the example 10!

Collapse
 
camicode profile image
CamCode

Hi,
I followed this article and thank you for doing it.
Can I ask you how did you think about them?
I mean, you have used some particular pseudocode or resource?
You know what a pleasure to solve these problems , but make a huge effort yet.
P.S Sorry for my bad English

Collapse
 
miketalbot profile image
Mike Talbot ⭐ • Edited

I would have though the shortest version of (1) would be:

    let rotate = (arr,n) => (arr.unshift(...arr.splice(-n % arr.length, n % arr.length)), arr)

Though I guess the splice allocates an array of size n % length

Collapse
 
jakebman profile image
jakebman • Edited

There's also the reference implementation for C++'s rotate() method

It has the ability to rotate a smaller sub-section of an array as well. The array that started as [array[0], ... array[first], array[first+1], ..., array[middle], array[middle + 1], .... array[last -1] (array[last], which might be the magical just off the edge n+1th item), ...]
will become [array[0], ... array[middle], array[middle+1], ..., array[last -1], array[first], array[first + 1], .... (array[last], which is the first index that does not move), ...]

C++ has some non-javascriptisms, so let's a js transliteration:

function rotate (array, first, middle, last)
{
  next = middle;
  while (first!=next)
  {
    swap (array, first++, next++);
    if (next==last) next=middle;
    else if (first==middle) middle=next;
  }
}

// A well-known C++ library function. Simple implementation here.
function swap(arr, i, j){
  temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
 
miketalbot profile image
Mike Talbot ⭐

It's probably the game programmer in me coming out. Don't allocate things because something has to garbage collect them later. That takes time, causes glitches etc.

I wrote the below a while ago about this. It really doesn't matter if you are sure the code isn't going to work on giant data or be called frequently. If that is the case then my "dont allocate/copy/garbage collect" OCD kicks in :)

 
miketalbot profile image
Mike Talbot ⭐

I guess my point was that the array is a specific data structure, I expect it to be optimised for being an array. If my problem is something that includes a "rotation" then a rolling buffer may well be a better algorithm - requires no shifting, just a very slightly more complicated retrieve operation and then move a head and tail pointer.

For example: if you are constantly inserting all over a list and only rarely retrieving all the items then no contiguous array, no matter how optimised, will be anywhere near the performance of a linked list.

If I want to implement a thing that has the last 100 values in it then shifting an array for every insertion is massively more costly than increment and modulus. Getting a new array with slice is allocating memory every time. It's easy to write the code, but the consequences may be significant under load.

Collapse
 
jpantunes profile image
JP Antunes

Nice post! I have two solutions, neither of which is better than yours, but still might be interesting.

Approach 1: Functional style, easy to read but slow

const head = (arr, k) => arr.slice(0, k);
const tail = (arr, k) => arr.slice(k);
const rotator = (arr, k) => [...tail(arr, k), ...head(arr, k)];

Approach 2: using recursion and modifying the array in place

const recursed = (arr, k) => k == 0 ? arr : (arr.push(arr.shift()) , recursed(arr, --k)); 
Collapse
 
kingofcramers profile image
Harry

Good article, but just wanted to point out: The first solution is actually O(n^2) time complexity (not good!) since you have to move the entire array every time you shift an element to the front.

This makes the first solution a less efficient approach than the others mentioned here.

Collapse
 
karmablackshaw profile image
KarmaBlackshaw

I never thought of using modulo. Nice post!

Collapse
 
anishhajare profile image
Anish Hajare

Nice approach, just wanted to point out the typo, in the 3rd approach it says coding the second approach and in the following paragraph instead of num.0 it is num,0.