CtCI - Array Left Rotation

CtCI - Array Left Rotation

A left rotation operation on an array of size Nshifts each of the array’s elements one unit to the left. For example, if two left rotations are performed on array [1,2,3,4,5], then the array would become [3,4,5,1,2]. Given an array of N integers and a number, D, perform D left rotations on the array. Then print the updated array as a single line of space-separated integers.

The first line contains two space-separated integers denoting the respective values of N (the number of integers) and D (the number of left rotations you must perform). The second line contains N space-separated integers describing the respective elements of the array’s initial state.

// Input
5 4
1 2 3 4 5

// Output
5 1 2 3 4

Let’s start with the brute-force solution, and we can do this in two different ways. One way is to iterate over the list D times and for each iteration we will modify the value of a new variable, the value for each iteration will be the numbers from position K _(where K is the index of the iteration) to the end of the list, plus the numbers from position zero to K.

var newList []int
for i := 1; i <= d; i++ {
    newList = append(list[i:], list[0:i]...)
}

This will generate a new array with the same size as the original list. A better brute-force approach would be to update the content of the array in-place by setting a new variable only for the first number in the list for each iteration, then replace the value of the array with the numbers from position one to the end of the original list, and finally appending the number from the temporary variable.

var temp int
for i := 0; i < d; i++ {
    temp = list[0]
    list = append(list[1:], temp)
}

Good, now the additional memory is simply O(1). However, we are still doing O(n) with the complexity of the iteration. Let’s see if we can optimize the code even more. We have that for D=4 we are returning A[D:] + A[0:D] so it is logical that we can simply move everything from position D to the beginning and the numbers from the beginning to the end.

list = append(list[d:], list[0:d]...)

Awesome! We have taken both the complexity and memory to O(1). However, this only works if D < N because otherwise we will raise an index out of range exception as we are trying to access positions that do not exist in the array with the first list selection A[D:]. Let’s see what happens to the array when D=5 through D=10.

D=5; N[1, 2, 3, 4, 5]
[2 3 4 5 1]
[3 4 5 1 2]
[4 5 1 2 3]
[5 1 2 3 4]
[1 2 3 4 5]
D=6; N[1, 2, 3, 4, 5]
[2 3 4 5 1]
[3 4 5 1 2]
[4 5 1 2 3]
[5 1 2 3 4]
[1 2 3 4 5]
[2 3 4 5 1]
D=7; N[1, 2, 3, 4, 5]
[2 3 4 5 1]
[3 4 5 1 2]
[4 5 1 2 3]
[5 1 2 3 4]
[1 2 3 4 5]
[2 3 4 5 1]
[3 4 5 1 2]
D=8; N[1, 2, 3, 4, 5]
[2 3 4 5 1]
[3 4 5 1 2]
[4 5 1 2 3]
[5 1 2 3 4]
[1 2 3 4 5]
[2 3 4 5 1]
[3 4 5 1 2]
[4 5 1 2 3]
D=9; N[1, 2, 3, 4, 5]
[2 3 4 5 1]
[3 4 5 1 2]
[4 5 1 2 3]
[5 1 2 3 4]
[1 2 3 4 5]
[2 3 4 5 1]
[3 4 5 1 2]
[4 5 1 2 3]
[5 1 2 3 4]
D=10; N[1, 2, 3, 4, 5]
[2 3 4 5 1]
[3 4 5 1 2]
[4 5 1 2 3]
[5 1 2 3 4]
[1 2 3 4 5]
[2 3 4 5 1]
[3 4 5 1 2]
[4 5 1 2 3]
[5 1 2 3 4]
[1 2 3 4 5]

We notice that for both D=5 and D=10 the array gets to its original form, so for a list of N numbers if we do N rotations we get the same result as if the rotation was not applied, we can assume that D=0 if D==N, or D=6 we have that D=1 if D==N+1, and so on like this:

D=5;  D=0 if D==N+0
D=6;  D=1 if D==N+1
D=7;  D=2 if D==N+2
D=8;  D=3 if D==N+3
D=9;  D=4 if D==N+4
D=10; D=0 if D==N+N

We can see a pattern here already, but lets take D=15 through D=20:

D=15; D=15%N = 0
D=16; D=16%N = 1
D=17; D=17%N = 2
D=18; D=18%N = 3
D=19; D=19%N = 4
D=20; D=20%N = 0

Good, so we can reduce any number of rotations greater than the number of items in the list by extracting the modulo, this means we can still keep O(n) no matter how big the number of rotations is.

func solution(list []int, d int) []int {
    d = d % n /* Keep rotations in range */
    return append(list[d:], list[0:d]...)
}
Do you have a project idea? Let's make it together!