Arrays
Overview
I figured we could start with one of the simplest data structures on our journey. Array's are a swift collection type & they can hold elements of a single type, whether it be Integers, Strings, or Structs/Classes. They are linear collections that are accessible using indexes starting at index Zero.
Array's in Memory
Swift arrays come in 2 different variations depending on how you initialize them:
Static arrays are an array implementation in which the size of the array is determined on initialization. Under the hood, the machine will allocate a fixed amount of memory to store this initialized array. Which is nice! But comes at a cost. In order to append values, the machine will copy the entire array over, and allocate new memory space for it + the new value you want to add. This is a linear operation.
Dynamic arrays are an array implementation that preemptively allocates DOUBLE the memory needed to store the arrays values. Therefore when you want to append a new value, that operation is constant time due to the already free space available to add the value into memory. When all the extra free space is filled up, the array is copied and stored elsewhere. This operation is Amortized constant time, when inserting at the end of the array.
Under the hood Swift Implementation
When looking through the swift source code on arrays, you will see the underlying implementation of arrays uses Structs. This means arrays are value types, and whenever you copy an array over to a new variable, the value of the array is copied and stored in a new memory address. Any changes to this copied variable will not affect the original array. For example:
var originalArray = [1, 2, 3]
var copyArray = originalArray
copyArray.append(4)
print(originalArray) // [1, 2, 3]
print(copyArray) // [1, 2, 3, 4]
To be even more efficient, Swift uses copy-on-write optimization for arrays. This means copies of arrays are stored at the same memory address until one of the copies is mutated. Then the array is stored into a new memory address. Keep this in mind when writing efficient code, because in swift copying the array over a bunch is not the time consuming event. The mutation of the copy is what will cost you in Big O time.
Big O operations on Arrays
- Accessing value at an index O(1)
- Update value at an index O(1)
- Insert value at beginning O(n)
- Insert value at middle O(n)
- Insert value at end:
- Dynamic arrays: Amortized O(1)
- Static arrays: O(n)
- Remove value at beginning O(n)
- Remove value at middle O(n)
- Remove value at end O(1)
- Copy array O(n)
Array Declarations
Arrays are very easy to declare (dynamic arrays):
let arrayOne = [String]()
let arrayTwo: [Int] = []
let arrayThree = [CustomObjectOne, CustomObjectTwo]
The swift compiler does some really cool things under the hood to infer the underlying type based on how you declare the variable.
You can also determine the size of the array & repeated values of the array on variable declaration like so (static array):
let arrayFour = Array(repearing: "Four" count: 6) // ["Four", "Four", "Four", "Four", "Four", "Four"]
Operations on Arrays
Inserting elements in arrays is simple, there are a couple main API's depending on your use case:
arrayFive.append(8) // at to the end
arrayFive.append(contentsOf: [0, 7]) // add a sequence
// [1, 2, 8, 0, 7]
arrayFive.insert(9, at: 3) // 0-based index
// [1, 2, 8, 9, 0, 7]
Here is how to delete elements in an array:
arrayFive.removeFirst()
arrayFive.removeLast()
// [2, 8, 9, 0]
arrayFive.remove(at: 0)
// remove index 0
// [8, 9, 0]
By accessing an element on an array you can substitute the value in place:
if let element = arrayFive.firstIndex(of: 8) {
arrayFive[element] = 9
}
// [9, 9, 0]
Higher Order Functions
Sort
Say you have a collection of elements in the form of an array, and you want to sort these elements by some sort of predicate. The swift collection type comes with the built in sorted by function. This function returns a new array from your desired sorting mechanism. For example:
func sorted(by: (Base.Element, Base.Element) throws -> Bool) rethrows -> [Base.Element]
The sorted by function takes a predicate in which you can define how to sort your elements.
struct FooStruct {
var value: Int
}
var nonSortedArray = [FooStruct(value: 15), FooStruct(value: 3), FooStruct(value: 9)]
// Trailing closure notation
var sortedArrayOne = nonSortedArray.sorted (a, b) -> Bool in {
return a.value < b.value
}
// Shorthand notation
var sortedArrayTwo = nonSortedArray.sorted { $0.value < $1.value }
print(sortedArrayTwo) // [FooStruct(value: 3), FooStruct(value: 9), FooStruct(value: 15)]
Map
The main purpose of Map is to iterate on every element in the array, but instead of sorting the elements, you can transform each element based on a closure you pass into it. Here is the underlying implementation:
func map<T>(_ transform: (Self.Element) throws -> T) rethrows -> [T]
Given the return type of the map function is T, we can pass in one type of array, and return a different type of array. For example taking in an array of numbers, mapping over them, and returning that array represented in String form.
let newArray = [1, 2, 3].map { (item) -> String
return String(item)
}
Filter
You can specify a filter in the form of a closure, and you can filter an array given your criteria.
func filter(_ isIncluded: @escaping (Self.Elements.Element) -> Bool) -> LazyFilterSequence<Self.Elements>
For example lets get all numbers from our array that are greater than 1.
let filteredArray = [1, 2, 3, 4, 5].map{ (item) -> Bool in
return item > 1
}
Reduce
This function allows us to combine all the elements in a collection, and return a unified common (and also generic) type!
func reduce<Result>(_ initialResult: Result, _ nextPartialResult: (Result, Bound) throws -> Result) rethrows -> Result
Let's say we want to take all of our numbers in an array, and combine them into a single long String.
// Long version
let reduced = [3, 4, 1, 2].reduce("") {(result, item) -> String in
return result + String(item)
}
// Inline version
let reduced = [2, 3, 1, 4].reduce("") { $0 + String($1) }
FlatMap
This takes in a closure and applies this closure to every element in the array. It returns the flattened sequence post traversal.
func flatMap<SegmentOfResult>(_ transform: ((key: Key, value: Value)) throws -> SegmentOfResult) rethrows -> [SegmentOfResult.Element] where SegmentOfResult : Sequence
Remember that map can return a different array type than was traversed upon. But with FlatMap we can transform, and then flatten. Typically this function is used in sequences of sequences.
let strings = [["Hello"], ["GoodBye"]]
let finalStrings = strings.flatMap({ $0 })
print(finalStrings) // ["Hello transformed", "Goodbye transformed"]
CompactMap
This function is frequently used with sequences that contain optionals. It is a safe way to traverse an array, and safely unwrap the value, and return the new sequence
func compactMap<ElementOfResult>(_ transform: (Base.Element) throws -> ElementOfResult?) rethrows -> [ElementOfResult]
For example:
let optionals: [Int?] = [1, nil, 6, 7]
let finalOptionals: [Int] = optionals.compactMap({ $0 })
print(finalOptionals) // [1, 6, 7]
Array Slicing
Slicing arrays, and getting specific ranges of arrays in swift can be slightly tricky as opposed to other programming languages.
Ranges
Starting in Swift 5, you can use the subscript of an arrays range, to get specific parts of an array. You use the swift built in Range type for this.
let test = [3, 2, 1, 0]
let test2 = test[0..<2] // Give us the indices from the first array 0 up to, but not including the 2nd zero based index.
print(test2) // [3, 2]
let nums = [10, 3, 4, 2, 11, 14, 15, 99]
let nums2 = nums[0..5]
print(nums2) // [10, 3, 4, 2, 11, 14]
Prefix/Suffix
There are also built in swift functions for getting the beginning and end sections of an array. All you need to do is pass the X number of prefixed or suffixed values you want from the array as a parameter in the function. Prefix is for the first X values from the array, and suffix is for the last X values you want from the array.
let longNums = [10, 3, 2, 1, 45, 67, 88, 99, 100, 312]
let firstThree = longNums.prefix(3)
let lastThree = longNums.suffix(3)
print(firstThree) // [10, 3, 2]
print(lastThree) // [99, 100, 312]
Conclusion
And thats it! You are now a Swift Array master, so give yourself a pat on the back. Coming soon we will be taking the arrays, and giving some real life application in Leetcode Problems. We will go over common tips & tricks you will encounter in Leetcode array problems. Stay Tuned!
