Rotate Array in Swift

Question

While exploring algorithms in Swift, couldn't find algorithm for array rotation in swift without using funcs shiftLeft / shiftRight.

C has this graceful algo with time complexity of O(N):

/* Function to left rotate arr[] of size n by d */
void leftRotate(int arr[], int d, int n)
{
    rvereseArray(arr, 0, d-1);
    rvereseArray(arr, d, n-1);
    rvereseArray(arr, 0, n-1);
}

/*Function to reverse arr[] from index start to end*/
void rvereseArray(int arr[], int start, int end)
{
    int temp;
    while (start < end)
    {
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        start++;
        end--;
    }
}

I'm struggling with converting this into swift:

func rotate(array:[Int], positions:Int, arSize:Int) {

    var a = array
    var p = positions
    var s = arSize

    reverseArray(array: a, start: 0, end: p-1)
    reverseArray(array: a, start: p, end: s-1)
    reverseArray(array: a, start: 0, end: s-1)
}

func reverseArray(array: [Int], start:Int, end:Int) {

    var a = array
    var s = start
    var e = end
    var temp = 0
    while s < e {
        temp = a[s]
        a[s] = a[e]
        a[e] = temp
        s += 1
        e -= 1
    }
} 

As I understand, for swift, we need to specify return types. How they should be configured without increasing space(memory) complexity? (aka, without creating new temporary arrays)

---

This question is different from others, because its about how returns work in swift compare to C.

Answer 1

// a is the array to be left rotated // d is the number of unit for left rotation

func rotLeft(a: [Int], d: Int) -> [Int] {
    var a = a
    for index in 0...(d - 1) {
       a.append(a[0])
       a.remove(at: 0)
     }
    return a
 }

// calling Function

rotLeft(a: [1,2,3,4,5], d: 4)

// OutPut [5, 1, 2, 3, 4]

Answer 2

We can use Slice

func rotLeft(a: [Int], d: Int) -> [Int] {

var slice1 = a[..<d]
var slice2 = a[d...]
var array = Array(slice2) + Array(slice1)

return array

}

print(rotLeft(a:[1,2,3,4,5], d:4))

//prints [5,1,2,3,4]

Answer 3

Edit update:

Swift 5 or later

extension RangeReplaceableCollection {
    mutating func rotate(positions: Int) {
        let index = self.index(startIndex, offsetBy: positions, limitedBy: endIndex) ?? endIndex
        let slice = self[..<index]
        removeSubrange(..<index)
        insert(contentsOf: slice, at: endIndex)
    }
}

---

extension RangeReplaceableCollection where Self: BidirectionalCollection {
    mutating func rotate(positions: Int, size: Int) {
        let index = self.index(startIndex, offsetBy: positions, limitedBy: endIndex) ?? endIndex
        let end = self.index(index, offsetBy: size - positions, limitedBy: self.index(before: endIndex)) ?? endIndex
        replaceSubrange(..<index, with: self[..<index].reversed())
        replaceSubrange(index..<end, with: self[index..<end].reversed())
        replaceSubrange(..<end, with: self[..<end].reversed())
    }
}

---

var test = [1,2,3,4,5,6,7,8,9,10]
test.rotate(positions: 3)   // [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]

var test2 = "1234567890"
test2.rotate(positions: 3)   // "4567890123"

Answer 4

To be complete, the rotation function should support negative (right) rotations and rotating more than the array's size

extension Array 
{
    mutating func rotateLeft(by rotations:Int) 
    { 
       // rotation irrelevant when less than 2 elements
       if count < 2 { return }  

       // effective left rotation for negative and > count
       let rotations = (rotations%count + count) % count 

       // no use rotating by zero
       if rotations == 0 { return } 

       // rotate
       (1..<count).reduce(0)
       { let i = ($0.0+rotations)%count; swap(&self[$0.0],&self[i]); return i }
    }

    mutating func reverse()
    {
       (0..<count/2).forEach{ swap(&self[$0],&self[count-$0-1]) }
    }
}

Answer 5

We can do it using Array's dropFirst() and dropLast() functions.

func rotateLeft(arrToRotate: inout [Int], positions: Int){
  if arrToRotate.count == 0 || positions == 0 || positions > arrToRotate.count{
      print("invalid")
      return
  }
  arrToRotate = arrToRotate.dropFirst(positions) + arrToRotate.dropLast(arrToRotate.count-positions)
}

var numbers : [Int] = [1, 2, 3, 4, 5]
rotateLeft(arrToRotate: &numbers, positions:2)
print(numbers)  //prints [3, 4, 5, 1, 2]

Answer 6

This solution rotates the element of time complexity O(n)

func rotLeft(a: [Int], d: Int) -> [Int] {
   var arr = a
   var size = arr.count - 1
   for i in 0...size  {
     let newloc = (i + (arr.count - d)) % arr.count
     arr[newloc] = a[i]
   }
   return arr
}

you shouldn't use .append(x) as in the worst case it can be O(n) and you shouldn't use .remove(at: x) as its O(n) when you can avoid using those methods As when using them you basically get n + n + n which isn't that great