'Rotate Array in Swift

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.

swiftalgorithm


Solution 1:[1]

We can use Slice 

func rotLeft(a: [Int], d: Int) -> [Int] {
    let slice1 = a[..<d]
    let slice2 = a[d...]
    return Array(slice2) + Array(slice1)
}

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

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

Solution 2:[2]

Why create a reverse function when we already have it in the Swift standard library? My solution (derived from Leo Dabus'):

extension Array {
    mutating func rotate(positions: Int, size: Int? = nil) {
        let size = size ?? count
        guard positions < count && size <= count else { return }

        self[0..<positions].reverse()
        self[positions..<size].reverse()
        self[0..<size].reverse()
    }
}

Solution 3:[3]

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]) }
    }
}

Solution 4:[4]

// 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]

Solution 5:[5]

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

Solution 6:[6]

If anybody lands here after watching the Embracing Algorithms WWDC18 session by David Abrahams, here is one of the implementations of rotate from the swift/test/Prototypes/Algorithms.swift file.

extension MutableCollection where Self: BidirectionalCollection {
    /// Rotates the elements of the collection so that the element
    /// at `middle` ends up first.
    ///
    /// - Returns: The new index of the element that was first
    ///   pre-rotation.
    /// **- Complexity: O(*n*)**
    @discardableResult
    public mutating func rotate(shiftingToStart middle: Index) -> Index {
        self[..<middle].reverse()
        self[middle...].reverse()
        let (p, q) = _reverseUntil(middle)
        self[p..<q].reverse()
        return middle == p ? q : p
        }
    }

This algorithms depends on reverseUntil(:) defined in the same file

extension MutableCollection where Self: BidirectionalCollection {

/// Reverses the elements of the collection, moving from each end until
/// `limit` is reached from either direction. The returned indices are the
/// start and end of the range of unreversed elements.
///
///     Input:
///     [a b c d e f g h i j k l m n o p]
///             ^
///           limit
///     Output:
///     [p o n m e f g h i j k l d c b a]
///             ^               ^
///             f               l
///
/// - Postcondition: For returned indices `(f, l)`:
///   `f == limit || l == limit`
@inline(__always)
@discardableResult
internal mutating func _reverseUntil(_ limit: Index) -> (Index, Index) {
    var f = startIndex
    var l = endIndex
    while f != limit && l != limit {
        formIndex(before: &l)
        swapAt(f, l)
        formIndex(after: &f)
    }
    return (f, l)
}
}

Solution 7:[7]

You need to consider the scenario such as-

The number of rotation can be equal/more than the size of array you need to rotate.

To handle this scenario use modulo operator to find the actual number of rotation as you will find out rotating an array by a number equal to its size result in same array.

    func rotateLeft(array:[Int],numberOfRotation:Int) -> [Int]
    {
     let offset = numberOfRotation % array.count
     let tempResult = array[offset...] + array[..<offset]
     return Array(tempResult)
    }

Solution 8:[8]

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]

Solution 9:[9]

here is a way to rotate left or right. Just call rotate on your array as shown. This does not mutate the array, if you wish to mutate the array, set the array equal to the rotation.

extension Array {
    func rotate(moveRight: Bool, numOfRotations: Int) -> Array<Element>{
        var arr = self
        var i = 0
        while i < numOfRotations {
            if moveRight {
                arr.insert(arr.remove(at: arr.count - 1), at: 0)
            } else {
                arr.append(arr.remove(at: 0))
            }
            i += 1
        }
        return arr
    }
}

var arr = ["a","b","c","d","e"]

print(arr.rotate(moveRight: true, numOfRotations: 2))
// ["d", "e", "a", "b", "c"]
print(arr)
// ["a", "b", "c", "d", "e"]
arr = arr.rotate(moveRight: true, numOfRotations: 2)
print(arr)
// ["d", "e", "a", "b", "c"]

Solution 10:[10]

Approach 1:

func rotate(_ nums: inout [Int], _ k: Int) {
    nums.enumerated().forEach { nums[ (k + $0)  % nums.count] = $1 }
}

Approach 2:

func rotLeft(a: [Int], d: Int) -> [Int] {
    var a = a
    
    reverse(&a, 0, d)
    reverse(&a, d, a.count)
    reverse(&a, 0, a.count)
    return a
}

func reverse(_ a: inout [Int], _ s: Int, _ r: Int) {
    var r = r, s = s
    
    while s < r {
        a.swapAt(s, r - 1)
        s += 1
        r -= 1
    }
}

Related Questions