Write a version of rotate that operates in a single pass

Getting Help Code Review
1

I am currently reading *** Go Programming Language, by Alan Donovan***. In chapter 4, I stuck in some code of exercise 4.4 which state that “Write a version of rotate that operates in a single pass?” I want to write it with a little modification with number of left rotations.

package main
import(
  "fmt"
)

func rotate(s []int,shift int){
   first := s[:shift]
   copy(s,s[shift:])   // This change the values of first
   s[len(s)-shift]=first  // This doesn't work !!!
}

func main() {
   data := []int{1,2,3,4,5,6}
   left_shift := 3
   rotate(data,left_shift)  // 4 5 6 1 2 3	
   fmt.Println(data)
}

Can anyone help me to understand concepts of Slices.

2

slices are pointers to an special structure (https://blog.golang.org/slices-intro), so first is just a pointer to slice contents, if you change it, also the contents of first because it points to same address.
So you can use this code to do what you want to do:

func rotate(s []int, shift int) {
   slc3 := make([]int, 0)
   slc3 = append(slc3, s[shift:]...)
   slc3 = append(slc3, s[:shift]...)
   copy(s, slc3)
}
3

Even though the size of the slice didn’t get changed, initial array remains untouched even after an operation.

Can you explain here

4

I found a good blog article in the docs about this behavior: https://blog.golang.org/slices#TOC_4.

I know append says if the length is unchanged its modifies the underlying array but that doesn’t seem to be happening in your playground example.

5

yes. I’m not getting an expected behaviour in my case.

6

Later after some more reading I understood how slice work. So I have also write my version of rotate function which is O(n) space complexity.

// space is O(n)
func rotate(s []int,shift int)[]int{
    var newdata []int
    first := s[:shift]
    newdata = append(newdata,s[shift:]...)
    newdata = append(newdata,first...)
    return newdata
}	
func main(){
    data := []int{1,2,3,4,5,6}
    left_shift := 3
    fmt.Println(rotate(data,left_shift))  // 4 5 6 1 2 3
}

I was trying to do this same with O(1) space. Does it possible?

7

I have a solution in O(1) space, that rotates in place.

The premise is that when you shift left the first element by r positions, you save the value that it replaces, and keep replacing values to the left by r positions until you’ve replaced the first element.

Then, you repeat the operations with the second element, and so on, until you’ve done it for r elements, at which point you’ve rotated all the values in the array. This sums up to just len(s) array modification operations.

package main
import (
    "fmt"
)

func main() {
        s := []int{0, 1, 2, 3, 4, 5}
        fmt.Println(s) // "[0 1 2 3 4 5]"
        // Rotate s left by two positions.
        rotate(s, 2)
        fmt.Println(s) // "[2 3 4 5 0 1]"
}

// rotate rotates a slice s by shift positions left, in place.
func rotate(s []int, shift int) {
        for i, v := range s[:shift] {
                for j := i + len(s) - shift; j >= 0; j -= shift {
                        s[j], v = v, s[j]
                        fmt.Printf("i=%d, j=%d, v=%d, s=%v\n", i, j, v, s)
                }
        }
}

Outputs:

[0 1 2 3 4 5]
i=0, j=4, v=4, s=[0 1 2 3 0 5]
i=0, j=2, v=2, s=[0 1 4 3 0 5]
i=0, j=0, v=0, s=[2 1 4 3 0 5]
i=1, j=5, v=5, s=[2 1 4 3 0 1]
i=1, j=3, v=3, s=[2 1 4 5 0 1]
i=1, j=1, v=1, s=[2 3 4 5 0 1]
[2 3 4 5 0 1]
1 Like