Building Blocks

What Swift gives you and what it does not

The standard library has Array, Dictionary and Set. It has no queue, deque, heap or linked list. In an interview you have two options:

Ask: "Can I assume a heap with push and pop?" Many interviewers say yes.
If not, write it. This chapter gives you short versions you can write from memory.

Stack

An array is already a stack. append pushes, popLast pops, last peeks. All are O(1).

func isValidBrackets(_ s: String) -> Bool {
    let pairs: [Character: Character] = [")": "(", "]": "[", "}": "{"]
    var stack: [Character] = []
    for c in s {
        if let open = pairs[c] {
            guard stack.popLast() == open else { return false }   // wrong or missing opener
        } else {
            stack.append(c)
        }
    }
    return stack.isEmpty
}

print(isValidBrackets("([]{})"))   // true
print(isValidBrackets("(]"))       // false

If you want a named type:

struct Stack<Element> {
    private var items: [Element] = []

    var isEmpty: Bool { items.isEmpty }
    var peek: Element? { items.last }

    mutating func push(_ item: Element) { items.append(item) }
    mutating func pop() -> Element? { items.popLast() }
}

var stack = Stack<Int>()
stack.push(1)
stack.push(2)
print(stack.pop()!, stack.peek!)   // 2 1

Queue

removeFirst() on an array is O(n), because every element moves. In BFS this turns O(n) into O(n²). Two fixes:

Fix 1: a head index. Never remove. Just move a pointer forward. This is the fastest way to write BFS in an interview:

var queue = [1]
var head = 0
while head < queue.count {
    let node = queue[head]
    head += 1
    if node < 4 { queue.append(node * 2) }   // add children
}
print(queue)   // [1, 2, 4]

As a reusable type, which also frees memory now and then:

struct Queue<Element> {
    private var items: [Element] = []
    private var head = 0

    var isEmpty: Bool { head == items.count }
    var count: Int { items.count - head }

    mutating func enqueue(_ item: Element) { items.append(item) }

    mutating func dequeue() -> Element? {
        guard head < items.count else { return nil }
        let item = items[head]
        head += 1
        if head > 64 && head * 2 > items.count {   // more than half is dead space
            items.removeFirst(head)
            head = 0
        }
        return item
    }
}

Fix 2: two stacks. Push into inbox. Pop from outbox. When outbox is empty, move everything over once.

struct TwoStackQueue<Element> {
    private var inbox: [Element] = []
    private var outbox: [Element] = []

    var isEmpty: Bool { inbox.isEmpty && outbox.isEmpty }

    mutating func enqueue(_ item: Element) { inbox.append(item) }

    mutating func dequeue() -> Element? {
        if outbox.isEmpty {
            outbox = inbox.reversed()   // O(n), but each item moves only once
            inbox.removeAll()
        }
        return outbox.popLast()
    }
}

var q = TwoStackQueue<String>()
q.enqueue("a")
q.enqueue("b")
print(q.dequeue()!, q.dequeue()!)   // a b

Each item is moved at most once, so dequeue is O(1) amortized (on average over many calls). This is a classic interview question by itself.

Deque

A deque (double-ended queue) adds and removes at both ends in O(1). Write it as a ring buffer: an array where the start position moves and wraps around.

struct Deque<Element> {
    private var buffer: [Element?] = Array(repeating: nil, count: 8)
    private var head = 0
    private(set) var count = 0

    var isEmpty: Bool { count == 0 }
    var first: Element? { isEmpty ? nil : buffer[head] }
    var last: Element? { isEmpty ? nil : buffer[slot(count - 1)] }

    private func slot(_ offset: Int) -> Int { (head + offset) % buffer.count }

    mutating func append(_ item: Element) {
        growIfFull()
        buffer[slot(count)] = item
        count += 1
    }

    mutating func prepend(_ item: Element) {
        growIfFull()
        head = (head - 1 + buffer.count) % buffer.count
        buffer[head] = item
        count += 1
    }

    mutating func popFirst() -> Element? {
        guard let item = first else { return nil }
        buffer[head] = nil
        head = slot(1)
        count -= 1
        return item
    }

    mutating func popLast() -> Element? {
        guard let item = last else { return nil }
        buffer[slot(count - 1)] = nil
        count -= 1
        return item
    }

    private mutating func growIfFull() {
        guard count == buffer.count else { return }
        var bigger = [Element?](repeating: nil, count: buffer.count * 2)
        for i in 0..<count { bigger[i] = buffer[slot(i)] }
        buffer = bigger
        head = 0
    }
}

var d = Deque<Int>()
d.append(2)
d.prepend(1)
d.append(3)
print(d.popFirst()!, d.popLast()!, d.count)   // 1 3 1

The Swift Collections package has a Deque, but most interview sites do not include it.

Heap (priority queue)

A heap gives you the smallest (or largest) item in O(1), and adds or removes in O(log n). It is stored in an array: the children of index i are at 2i + 1 and 2i + 2.

struct Heap<Element> {
    private var items: [Element] = []
    private let isHigher: (Element, Element) -> Bool   // true if the first belongs above

    init(by isHigher: @escaping (Element, Element) -> Bool) {
        self.isHigher = isHigher
    }

    var isEmpty: Bool { items.isEmpty }
    var count: Int { items.count }
    var peek: Element? { items.first }

    mutating func push(_ item: Element) {
        items.append(item)
        var child = items.count - 1
        while child > 0 {
            let parent = (child - 1) / 2
            guard isHigher(items[child], items[parent]) else { break }
            items.swapAt(child, parent)
            child = parent
        }
    }

    mutating func pop() -> Element? {
        guard !items.isEmpty else { return nil }
        items.swapAt(0, items.count - 1)
        let top = items.removeLast()
        var parent = 0
        while true {
            let left = 2 * parent + 1
            let right = left + 1
            var best = parent
            if left < items.count && isHigher(items[left], items[best]) { best = left }
            if right < items.count && isHigher(items[right], items[best]) { best = right }
            if best == parent { break }
            items.swapAt(parent, best)
            parent = best
        }
        return top
    }
}

The closure decides the order. < gives a min-heap. > gives a max-heap.

var minHeap = Heap<Int>(by: <)
var maxHeap = Heap<Int>(by: >)
for n in [5, 1, 8, 3] {
    minHeap.push(n)
    maxHeap.push(n)
}
print(minHeap.pop()!, maxHeap.pop()!)   // 1 8

// Tuples work too: here the smallest distance comes out first.
var frontier = Heap<(distance: Int, node: Int)>(by: { $0.distance < $1.distance })
frontier.push((distance: 7, node: 2))
frontier.push((distance: 3, node: 5))
print(frontier.pop()!.node)             // 5

The classic use, "k-th largest", keeps a min-heap of size k:

func kthLargest(_ nums: [Int], _ k: Int) -> Int? {
    var heap = Heap<Int>(by: <)
    for n in nums {
        heap.push(n)
        if heap.count > k { _ = heap.pop() }   // drop the smallest
    }
    return heap.count == k ? heap.peek : nil
}

print(kthLargest([3, 2, 1, 5, 6, 4], 2)!)   // 5

Time: O(n log k). Space: O(k).

Linked list

LeetCode-style problems use a class like this. Nodes are classes because they are shared and point to each other.

final class ListNode {
    var val: Int
    var next: ListNode?

    init(_ val: Int, _ next: ListNode? = nil) {
        self.val = val
        self.next = next
    }
}

func makeList(_ values: [Int]) -> ListNode? {
    let dummy = ListNode(0)       // a dummy head avoids special cases
    var tail = dummy
    for value in values {
        let node = ListNode(value)
        tail.next = node
        tail = node
    }
    return dummy.next
}

func toArray(_ head: ListNode?) -> [Int] {
    var result: [Int] = []
    var node = head
    while let current = node {
        result.append(current.val)
        node = current.next
    }
    return result
}

func reverse(_ head: ListNode?) -> ListNode? {
    var previous: ListNode? = nil
    var current = head
    while let node = current {
        let next = node.next
        node.next = previous
        previous = node
        current = next
    }
    return previous
}

func middle(_ head: ListNode?) -> ListNode? {
    var slow = head
    var fast = head
    while fast?.next != nil {       // fast moves 2 steps, slow moves 1
        slow = slow?.next
        fast = fast?.next?.next
    }
    return slow
}

print(toArray(reverse(makeList([1, 2, 3]))))   // [3, 2, 1]
print(middle(makeList([1, 2, 3, 4, 5]))!.val)  // 3

Use === to check if two variables point to the same node. Use ObjectIdentifier to put nodes in a Set:

func hasCycle(_ head: ListNode?) -> Bool {
    var seen = Set<ObjectIdentifier>()
    var node = head
    while let current = node {
        if !seen.insert(ObjectIdentifier(current)).inserted { return true }
        node = current.next
    }
    return false
}

(The O(1) space answer uses slow and fast pointers: if they ever meet with ===, there is a cycle.)

Tree node

final class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?

    init(_ val: Int, _ left: TreeNode? = nil, _ right: TreeNode? = nil) {
        self.val = val
        self.left = left
        self.right = right
    }
}

//      4
//     / \
//    2   7
//   / \
//  1   3
let root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(7))
print(root.left!.right!.val)   // 3

To test your code, build a tree from the LeetCode level-order format, where nil means "no node":

func makeTree(_ values: [Int?]) -> TreeNode? {
    guard let first = values.first, let rootValue = first else { return nil }
    let root = TreeNode(rootValue)
    var queue = [root]
    var head = 0
    var i = 1
    while i < values.count && head < queue.count {
        let node = queue[head]
        head += 1
        if let value = values[i] {
            node.left = TreeNode(value)
            queue.append(node.left!)
        }
        i += 1
        if i < values.count, let value = values[i] {
            node.right = TreeNode(value)
            queue.append(node.right!)
        }
        i += 1
    }
    return root
}

let tree = makeTree([4, 2, 7, 1, 3, nil, 9])
print(tree!.right!.right!.val)   // 9

Graph: adjacency list

Most graph problems give nodes 0..<n and a list of edges. Turn them into an adjacency list: for each node, the list of its neighbors.

func buildGraph(n: Int, edges: [[Int]], directed: Bool = false) -> [[Int]] {
    var graph = Array(repeating: [Int](), count: n)
    for edge in edges {
        graph[edge[0]].append(edge[1])
        if !directed { graph[edge[1]].append(edge[0]) }
    }
    return graph
}

let graph = buildGraph(n: 4, edges: [[0, 1], [0, 2], [2, 3]])
print(graph)   // [[1, 2], [0], [0, 3], [2]]

When nodes are strings, use a dictionary. When edges have weights, store a small struct:

var flights: [String: [String]] = [:]
for (from, to) in [("SFO", "JFK"), ("JFK", "LHR"), ("SFO", "SEA")] {
    flights[from, default: []].append(to)
}
print(flights["SFO"]!)   // ["JFK", "SEA"]

struct Edge {
    let to: Int
    let weight: Int
}
var roads = Array(repeating: [Edge](), count: 3)
roads[0].append(Edge(to: 1, weight: 4))
roads[1].append(Edge(to: 2, weight: 1))
print(roads[0][0].weight)   // 4

Representation	Space	Check one edge	Best for
Adjacency list `[[Int]]`	O(V + E)	O(degree)	Most problems (sparse graphs)
Matrix `[[Bool]]`	O(V²)	O(1)	Small, dense graphs
Edge list `[[Int]]`	O(E)	O(E)	Union-find, sorting edges by weight

A grid is also a graph. Each cell is a node, and its neighbors are up, down, left and right. You do not need to build a list for it.

#What Swift gives you and what it does not

#Stack

#Queue

#Deque

#Heap (priority queue)

#Linked list

#Tree node

#Graph: adjacency list