{ In Scope }

Rotating Arrays: Two Ways

January 30, 2019

Given an array and a number of left rotations (each left rotation moves the first element to end and all subsequent elements one place to the left)

Example: leftRot([1,2,3,4,5],2) // [3,4,5,1,2] by way of the following steps: [1,2,3,4,5] -> [2,3,4,5,1] -> [3,4,5,1,2]

There are a few potential gotchas in how to approach this problem. The biggest one to me was to realize that d can be less than or greater than the total length of the array.

With that as the case, I wanted to understand what the effective (i.e. the total number of steps that actually needed to happen) number of rotations would be.

For example, if we did leftRot([1,2,3,4],6) We would have:

0) [1,2,3,4] ->
1) [2,3,4,1] ->
2) [3,4,1,2] ->
3) [4,1,2,3] ->
4) [1,2,3,4] ->
5) [2,3,4,1] ->
6) [3,4,1,2]

But steps 1 and 5, 2 and 6 are the same! That’s because 6 % 4 = 2, so the effective number of rotations is actually only two.

Knowing this, we can reduce the number of steps dramatically. In our small example we had a 66% decline in the number of steps.

Just imagine if the number of steps and array size diverge even further!

The iterative approach

/**
 * Left Rotation
 * @args {Array} a - An array of integers
 * @args {number} d - The number of left-shift rotations to perform
 * @returns {string} Space separated integers
 * @example <caption> Examples of rotLeft </caption>
 * rotLeft([1,2,3,4], 6) // returns [3,4,1,2]
 * rotLeft([1,2,3,4], 3) // returns [4,1,2,3]
 */
function rotLeft(a, d) {
  //calculate effective rotation (d % a.length)
  let effectiveRotation = d % a.length

  // rotate the elements of a
  for (let i = 0; i < effectiveRotation; i += 1) {
    a = a.slice(1).concat(a[0])
  }
  return a
}

A Loop-less Approach

Instead of using loops, we can also go directly to the point in the array to create new sub-arrays.

However, since arrays are single blocks of memory, the creation of two new sub-arrays and their subsequent concatenation into the new final array would still be linear time due to the time it takes to construct the arrays.

/**
 * Left Rotation
 * @args {Array} a - An array of integers
 * @args {number} d - The number of left-shift rotations to perform
 * @returns {string} Space separated integers
 * @example <caption> Examples of rotLeft </caption>
 * rotLeft([1,2,3,4], 6) // returns [3,4,1,2]
 * rotLeft([1,2,3,4], 3) // returns [4,1,2,3]
 */
function rotLeft(a, d) {
  //calculate effective rotation (d % a.length)
  let effectiveRotation = d % a.length

  // split a at index of effective rotation into left and right
  let leftPortion = a.slice(0, effectiveRotation) // O(n)
  let rightPortion = a.slice(effectiveRotation) // O(n)

  // concat left to right
  return rightPortion.concat(leftPortion) // O(n)
}

Conclusion

Though it’s still O(n), the loop-less approach is almost always going to be more efficient than the iterative approach.

Though they both have a time complexity of O(n). The loop-less approach has three methods that are all O(n), and as such is ~3n.

Meanwhile, the iterative approach is O(effectiveRotations * n) because each element in the array has to shift to the left for each effective iteration.

This is one of the drawbacks of arrays as data structures. Access is fast, but insertion / deletion is not (except at the end and assuming there’s sufficient space).

Resources

Arrays: Left Rotation | HackerRank - The inspiration for this post


Stephen Weiss

Written by Stephen Weiss who lives in Chicago with his wife, Kate, and dog, Finn. Follow him on Twitter!