Rotate List

excerpt: This covers the building blocks such as left shift in array and using modulo operator for modulo arithmetic tags: left-shift-array-element modulo-operator two-pointers-moving-in-opposite-direction modulo-arithmetic swap

Write a function that rotates a list by k elements. For example [1,2,3,4,5,6] rotated by two becomes [3,4,5,6,1,2]. Try solving this without creating a copy of the list. How many swap or move operations do you need?

Given: [1,2,3,4,5,6]

One rotation:  [2,3,4,5,6,1]
Two rotations: [3,4,5,6,1,2]

Brute Force Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def rotate(list, k)
  size = list.size - 1
  k.times do
    previous = list[0]  

    size.downto(0) do |j|
      list[j], previous = previous, list[j]
    end
  end
  
  list
end

list = [1,2,3,4,5,6] 
k = 2

p rotate(list, k)

If the value of k is greater than the size of the list, there is no point in shifting that many times as we need to shift it only the number of times that is less than the size of the list. We can use modulo operator to reduce the value of k so that it does not exceed the list size.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def rotate(list, k)
  size = list.size - 1
  
	# Use modulo operator to minimize rotations
	k = k % size
	
  k.times do
    previous = list[0]  

    size.downto(0) do |j|
      list[j], previous = previous, list[j]
    end
  end
  
  list
end

If you want to shift the elements to the right:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def rotate(list, k)
  k.times do
    previous = list[-1]  

    for j in (0..list.size - 1)
      list[j], previous = previous, list[j]
    end
  end
  
  list
end

list = [1,2,3,4,5,6] 
k = 2

p rotate(list, k)

Task Breakdown

Original List : 1 2 3 4 5 6 7 After reversing all numbers : 7 6 5 4 3 2 1 After reversing first k numbers : 5 6 7 4 3 2 1 After reversing last n-k numbers : 5 6 7 1 2 3 4 –> Result

1
2
3
4
5
6
7
def reverse(a, i, j)  
  while i < j
    a[i], a[j] = a[j], a[i]
    i += 1
    j -= 1
  end  
end

1
2
3
4
5
6
7
8
9
def rotate(nums, k)
  reverse(nums)
end

list = [1,2,3,4,5,6,7] 
k = 2

rotate(list, k)
p list

After reversing all numbers : 7 6 5 4 3 2 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
def rotate(nums, k)
  reverse(nums, 0, nums.size - 1)
  reverse(nums, 0, k-1)
end

list = [1,2,3,4,5,6,7] 
k = 3

rotate(list, k)
p list

After reversing first k numbers : 5 6 7 4 3 2 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def rotate(nums, k)
  reverse(nums, 0, nums.size - 1)
  reverse(nums, 0, k-1)
  reverse(nums, nums.size-1-k, nums.size-1)
end

list = [1,2,3,4,5,6,7] 
k = 3

rotate(list, k)
p list

After reversing last n-k numbers : 5 6 7 1 2 3 4 –> Final Result

Working Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def reverse(a, i, j)  
  while i < j
    a[i], a[j] = a[j], a[i]
    i += 1
    j -= 1
  end  
end

def rotate(nums, k)
  # Avoid unnecessary rotation
  k = k % nums.size
  reverse(nums, 0, nums.size - 1)
  reverse(nums, 0, k-1)
  
	# Fix bug in the index for this call:
  reverse(nums, k, nums.size-1)
end