Rotate array

Given an array and an integer k, rotate the array k times.

Example

rotate([1,2,3,4,5], 2) #=> [3,4,5,1,2]
rotate([1,2,3,4,5], 4) #=> [5,1,2,3,4]
rotate([1,2,3,4,5], 5) #=> [1,2,3,4,5]

Solution

• To do it in place without using additional space, the trick is in reversing the array appropriately
• Reverse the first part 0..i, reverse the second part i..n, then reverse the entire array

Code

def rotate_array(arr, i)
  i = i%arr.size
  return arr if i == 0

  left = arr[0...i].reverse
  right = arr[i..arr.size].reverse
  arr = left + right

  arr.reverse
end

Complexity

Time: O(n), max of 3 traversals over the array Space: No additional space used