Swift Built-In Time Complexity: The Interview Cheat Sheet

Swift feels ergonomic right up until you write a BFS loop using an Array as a queue and wonder why your solution times out on a 10,000-node graph. Swift built-in time complexity is mostly O(1) where you'd expect, with one ugly exception: queue.removeFirst(). It's O(n). Apple documents this. Most people never check.

Swift Built-In Time Complexity: Quick Reference

Operation	Array	Dictionary	Set
Access by index	O(1)	O(1) avg	N/A
Insert at end	O(1) amortized	O(1) avg	O(1) avg
Insert at index	O(n)	N/A	N/A
Remove at end	O(1)	O(1) avg	O(1) avg
Remove at index	O(n)	N/A	N/A
removeFirst()	O(n)	N/A	N/A
Search / contains	O(n)	O(1) avg	O(1) avg
Sort	O(n log n)	N/A	N/A

Worst case for Dictionary and Set is O(n) due to hash collisions, same as every hash-based structure in any language.

Array: The Amortized Append and the removeFirst() Landmine

Swift arrays grow by doubling their capacity, so append() is O(1) amortized. The potential-function proof is in the amortized analysis guide if you need to defend it. The trap is removeFirst(), which is O(n) because the entire array shifts forward.

This bites hardest in BFS:

var queue = [Int]()
queue.append(node)
let current = queue.removeFirst()  // O(n) every time

For a graph with V vertices and E edges, your BFS just went from O(V+E) to O(V² + E). On 10,000 nodes that's the difference between 10ms and a timeout. Your interviewer will not say "nice try." They will say nothing. There will just be silence and a small red X.

Fix: use an index pointer into the array, or reach for the Deque type from Apple's Swift Collections package. Deque gives O(1) at both ends but it isn't in the standard library and isn't available on LeetCode.

removeLast() is O(1). remove(at:) and insert(_:at:) are O(n) because they shift elements.

Using Array.removeFirst() for BFS. Every call shifts the whole array one slot left. Technically it works.

Copy-on-Write

Swift arrays are value types with copy-on-write semantics. Mutating an array inside a function triggers an O(n) copy if the caller still holds a reference. Usually fine in interviews, but state it when asked about space complexity.

ContiguousArray skips Objective-C bridging overhead for reference-type elements. If your element type is a pure Swift struct or enum, Array and ContiguousArray perform identically.

Dictionary: O(1) Lookup With One Non-Obvious Trap

Dictionary lookups, inserts, and deletes are O(1) average. The subscript operator returns an Optional, so you check existence with dict[key] != nil.

Here's the trap: dict.keys.contains(_:) is O(n), not O(1). The keys property returns a Dictionary.Keys view, and calling contains on it does a linear scan. Use dict[key] != nil, which goes through the hash table directly.

// O(n) - wrong way to check key existence
if dict.keys.contains("apple") { ... }

// O(1) - correct
if dict["apple"] != nil { ... }

Swift has no getOrDefault. The idiom is dict[key, default: 0] += 1 to increment a counter.

Iteration is O(n). Order is not guaranteed and changes between runs since Swift 3 randomizes hash seeds.

Set: Fast Membership, Clunky Syntax

Set is your O(1) membership check. insert, contains, and remove are all O(1) average.

Set algebra costs are easy to underestimate:

let a: Set<Int> = [1, 2, 3]
let b: Set<Int> = [2, 3, 4]

a.union(b)         // O(m + n)
a.intersection(b)  // O(min(m, n))
a.subtracting(b)   // O(m)
a.isSubset(of: b)  // O(m)

Set does not maintain insertion order. If you need ordered unique elements, maintain a separate array alongside the set. That's the classic LRU cache pattern.

String: The Unicode Wall

Swift strings do not support integer indexing. This is the first thing that surprises developers coming from Python or JavaScript, usually at the worst possible moment.

let s = "hello"
let c = s[2]       // compile error - no integer subscript

The reason is Unicode. A Swift String stores Unicode grapheme clusters, and each cluster can be a variable number of bytes. There is no O(1) way to reach "character 42" without scanning from the start. Apple thought hard about this. You might disagree with the decision. Apple does not care.

Swift exposes String.Index instead, and index(_:offsetBy:) is O(n):

let start = s.startIndex
let idx = s.index(start, offsetBy: 2)  // O(n)
let c = s[idx]                          // O(1) once you have the index

string.count is also O(n). The interview workaround: convert to an array of characters at the top of your solution.

let chars = Array(s)  // O(n), once
let c = chars[2]      // O(1), forever after

You pay once and get O(1) random access for the rest of the solution.

String comparison is O(n). Building a result character by character via += reallocates on each append. Accumulate in an array and call String(chars) at the end instead.

Sorting: Timsort Since Swift 5

sort() mutates in place. sorted() returns a new array. Both are O(n log n).

var arr = [3, 1, 4, 1, 5]
arr.sort()                           // in-place, O(n) extra space
let sorted = arr.sorted()            // new array, O(n) extra space
arr.sort(by: >)                      // descending

Swift 5 switched from Introsort to Timsort, which is stable and performs better on partially sorted data. Stability matters for multi-key sorts: sort by a secondary field first, then by primary with a stable sort, and relative order from the first pass is preserved. The stable sort guide explains why stability is the property that makes that work.

sort() only works on var collections. A let array requires sorted().

What You Have to Write Yourself

This is the section that matters most in interviews. In Python you reach for heapq. In Java you grab PriorityQueue. In Swift you write a 25-line struct and hope you don't mess up the index arithmetic.

No heap or priority queue. Implement a 25-line binary heap. One quirk: siftDown needs to be a top-level function or use explicit inout, because Swift won't let a nested function capture an inout parameter.

struct MinHeap {
    var heap = [Int]()
    mutating func push(_ val: Int) {
        heap.append(val)
        siftUp(heap.count - 1)
    }
    mutating func pop() -> Int {
        heap.swapAt(0, heap.count - 1)
        let val = heap.removeLast()
        siftDown(0)
        return val
    }
    // siftUp and siftDown omitted for brevity
}

No binary search in the standard library. firstIndex(of:) does a linear scan, O(n). Swift Evolution SE-0074 proposed lowerBound and upperBound back in 2016. It was never merged. The proposal is still sitting there, a monument to good intentions and busy schedules. Write your own.

No deque. Swift Collections has Deque<T> with O(1) both-end operations, but it requires importing Collections. LeetCode's Swift environment doesn't have it as of early 2026.

No ordered map. There is no TreeMap or SortedDictionary equivalent in the standard library. Sorted keys means maintaining a separate sorted array.

Swift's standard library missed the npm memo. Heap? Roll your own. Binary search? Also roll your own. Deque? You already know.

Five Traps That Appear in Interviews

1. removeFirst() is O(n). Use an index pointer for BFS.

2. string.count is O(n). Calling it inside a loop is a hidden O(n²). Cache it: let n = s.count.

3. keys.contains() is O(n). Use dict[key] != nil for O(1).

4. sorted() allocates O(n) extra space. Account for it when asked about space complexity. sort() also uses O(n) auxiliary space because Timsort needs scratch memory.

5. No binary search means O(n) on sorted arrays. firstIndex(of:) is a linear scan. Write the binary search or time out.

For broader Swift idioms beyond complexity, the Swift for coding interviews guide covers comparators, collection patterns, and the gotchas that don't show up in a time complexity table.

Say the Complexity Out Loud

Knowing removeFirst is O(n) is half the job. The other half is saying "removeFirst is O(n), so I'm using an index pointer instead" while writing the code, without breaking stride. If that narration isn't automatic, you're burning cognitive budget you can't spare.

The fix is simple. Just narrate. Say it in your next mock interview. It sounds obvious, and it is, but you will forget under pressure unless you've done it out loud enough times that it's a reflex.

SpaceComplexity runs voice-based mock interviews that score exactly this: can you narrate your complexity analysis while coding, or do you go silent the moment you hit a tricky data structure choice?

Further Reading

• Apple Developer Documentation: Array
• Apple Developer Documentation: Dictionary
• Apple Developer Documentation: Set
• SwiftRocks: Introsort, Timsort, Swift's Sorting Algorithm
• Swift Forums: Array.removeFirst() is O(n)
• Swift Evolution SE-0074: Binary Search (unmerged proposal)