# CtCI - Array Left Rotation

A left rotation operation on an array of size `N`shifts 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
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!