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]...)
}
7 months ago
  • 8da57acFix minor bugs found by the code static ana…
7 months ago
  • caa417fAdd option to configure the malware scanner…
7 months ago
  • 9c86744Modify default value for some of the alert …
7 months ago
  • 84dd39dAdd option to stop sending the failed login…
7 months ago
  • eb05935Add pre-checks for every plugin page for si…
7 months ago
  • d21a062Modify mechanism to ignore files from integ…
7 months ago
  • b1a9169Add developer option to disable failed pass…
7 months ago
  • 4e3ef13Add support for other English and Spanish b…
7 months ago
  • 2d07b4eFix error interception for Firewall API err…
7 months ago
pushed to master at cixtor/slackapi
  • 4a2c1c8Modify data type for methods related to cha…
  • 6716199Add CLI handler for the users.identity API …
  • f9c448dAdd CLI handler for the mpim.open API endpo…
  • 305d1c4Add CLI handler for the mpim.mark API endpo…
  • 8bb89afAdd CLI handler for the mpim.close API endp…
  • 202a017Add CLI handler for the dnd.teamInfo API en…
  • 68819e9Add CLI handler for the dnd.info API endpoi…
  • 9a2b29aAdd CLI handler for the dnd.endSnooze API e…
  • e7dc86aAdd CLI handler for the dnd.setSnooze API e…
  • 111c53fAdd CLI handler for the dnd.endDnd API endp…
  • cdb620dFix token usage when there are no extra par…
  • View comparison for these 11 commits
7 months ago
pushed to master at cixtor/slackapi
7 months ago
  • 6497e80Remove unnecessary automatic blacklisting o…
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#40
Fix multiple bugs with the API calls and queue system
18 commit with 793 additions and 293 deletion
7 months ago
7 months ago
7 months ago
  • 38cc02aModify timing for the dashboard alerts afte…
7 months ago
  • 350c074Fix infinite loop with email alerts and SMT…
7 months ago
  • acff4aaFix detection of base URL with built-in fun…
7 months ago
7 months ago
7 months ago
7 months ago
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#39
Add queue system for the security logs and cache improvement
5 commit with 517 additions and 541 deletion
7 months ago
7 months ago
  • 4c51445Fix static function call of non-static Site…
7 months ago
7 months ago
  • af47581Add changelog to release version 1.8.6
7 months ago
opened pull request Sucuri/sucuri-wordpress-plugin#38
Add changelog to release version 1.8.5
6 commit with 4062 additions and 1841 deletion
7 months ago
  • dc1a05aAdd changelog to release version 1.8.5
7 months ago
Do you have a project idea? Let's make it together!