Slicing in Swift
Taking part of an array looks like one cheap operation, but in Swift the result depends on what type you end up with. Slicing an array with a range gives an ArraySlice, not a new Array:
let nums = [10, 20, 30, 40, 50, 60]
let part = nums[1..<4]
print(part, part.startIndex, part.endIndex)
print(part[1])
let copy = Array(part)
print(copy, copy[0])
[20, 30, 40] 1 4
20
[20, 30, 40] 20
An ArraySlice shares the original array's storage, so creating one is O(1) and uses no extra space for the elements. Its indices keep the numbering of the original array: part starts at 1, so part[1] is 20 and part[0] would crash. Converting with Array(part) copies the elements, costs O(k) for a slice of k elements, and restarts the indices at 0.
Strings follow the same idea. text.prefix(5) returns a Substring that shares the original text, and String(sub) makes a real copy, which costs O(k):
let text = "Hello, world"
let sub = text.prefix(5)
print(sub, type(of: sub))
let str = String(sub)
print(str, type(of: str))
Hello Substring
Hello String
Finding where a string slice ends can itself cost time, because a string can't jump to the character at offset k without walking past the earlier ones. So the cost of slicing a string is tied to how far into it the slice reaches.
Slicing helpers
The common helpers return slices too. dropFirst() and prefix(_:) on an array produce an ArraySlice in constant time, while wrapping the result in Array(...) pays for the copy:
let nums = [1, 2, 3, 4, 5]
let tail = nums.dropFirst()
print(tail, type(of: tail))
print(Array(nums.prefix(2)))
print(Array(nums[1...3].reversed()))
[2, 3, 4, 5] ArraySlice<Int>
[1, 2]
[4, 3, 2]
This makes dropFirst() a cheap alternative to removeFirst() when you only need to read the rest of the array. A recursive function that passes Array(a.dropFirst()) down at every level, however, copies n - 1, then n - 2 elements and so on, which is O(n²) in total. Passing the slice itself, or an index, avoids that.
Concatenation
Joining two sequences means building a new one that holds every element, so a + b costs O(n + m) for sequences of lengths n and m. The difference between + and appending in place matters inside loops:
var arr = [1, 2, 3]
arr = arr + [4] // builds a new array, O(n)
arr += [5, 6] // appends in place, O(m) amortized
arr.append(contentsOf: [7])
print(arr)
var s = "ab"
s += "cd"
s = s + "ef" // builds a new string, O(n)
print(s)
[1, 2, 3, 4, 5, 6, 7]
abcdef
If a loop of n iterations rebuilds the whole array or string each time with x = x + piece, the work adds up to 1 + 2 + ... + n, which is O(n²). Appending in place with +=, append or append(contentsOf:) keeps the whole loop at O(n) overall, because each append is amortized O(1) per element added.
To combine many strings, collect them in an array and call joined once:
var parts: [String] = []
for i in 0..<5 { parts.append(String(i)) }
print(parts.joined())
print(["a", "b", "c"].joined(separator: "-"))
01234
a-b-c
Copies and value semantics
Arrays and strings are value types: assigning one to another variable behaves as a copy. Swift makes that cheap with copy-on-write. The storage is shared until one of the two variables is changed, and only then is it actually copied, at O(n) cost.
let original = [1, 2, 3]
var other = original // no elements copied yet
other.append(4) // the copy happens here
print(original, other)
[1, 2, 3] [1, 2, 3, 4]
So passing an array to a function is cheap, but modifying a copy of it is not free the first time.
Key takeaways
- Slicing an array gives an
ArraySliceinO(1);Array(slice)copies inO(k). - A slice keeps the original indices, so don't assume it starts at 0.
a + bcreates a new sequence inO(n + m); repeating it in a loop isO(n²).- Append in place or use
joinedto build results in linear time.
