Arrays in Swift

In this doc we will talk about something that we need pay attention to when we are dealing with arrays in programming.

Time Complexity

1. Reverse an array can be more efficient than removing then inserting

Compared to reverse an array, removing k elements from the end of an array then inserting them to the beginning of the array one by one is more time consuming.

Even though both of them are O(n), the latter one is more time consuming because it involves more operations and makes more shifts in the array.

Reverse can be more efficient because how it’s implemented: it’s basically swapping the first element with the last element, the second element with the second last element, and so on.
pseudo code of reverse an array:

func reverseArray(_ arr: inout [Int]) {
    var left = 0
    var right = arr.count - 1
    while left < right {
        arr.swapAt(left, right)
        left += 1
        right -= 1
    }
}

Related Leetcode problem: 189. Rotate Array

Convenient Methods

1. Array Indices

In Swift, you can get the range of indices of an array by using indices property of the array.

let arr = [[1, 2], [3, 4], [5, 6]]
let rowIndices = arr.indices
let colIndices = arr[0].indices
// rowIndices: 0..<3
// colIndices: 0..<2

for i in rowIndices {
    for j in colIndices {
        print(arr[i][j])
    }
}

2. Array Sorting

Instead of

return result.sorted { $0[0] == $1[0] ? $0[1] < $1[1] : $0[0] < $1[0] } 

You can use lexicographicallyPrecedes method of the array to make the code more readable.

return result.sorted { $0.lexicographicallyPrecedes($1) }

3. Zip two arrays

You can use zip method to combine two arrays into a single array of tuples.

let arr1 = [1, 2, 3]
let arr2 = ["a", "b", "c"]
let zipped = Array(zip(arr1, arr2))
// zipped: [(1, "a"), (2, "b"), (3, "c")]

This can be helpful in scenarios like you need to iterate over two arrays simultaneously. For example, compare two arrays of Charaters, which have the same length, and return the number of different characters at the same index.

func numDifferentCharacters(_ s: String, _ t: String) -> Int {
    return zip(s, t).reduce(0) { $0 + ($1.0 == $1.1 ? 0 : 1) }
}

Another example, return an array of Data that contains the same number of characters as the start Data, and each character is from the bank Data, and the value is not in the filtered Data.

Leetcode problem: 433. Minimum Genetic Mutation

typealias Data =  [Character]
func variants(_ start: Data, _ bank: [Data], _ filtered: Set<Data>) -> [Data] {
    return bank.filter { candidate in 
        !filtered.contains(candidate) && zip(start, candidate).filter { $0 != $1 }.count == 1
    }
}

4. Stride

You can use stride method to iterate over a range of numbers with a specific step.

Instead of the following code:

var i = 0
while i < n {
    // do something
    i += 2
}

You can use stride method to make the code more readable.
There are three versions of stride method:

• stride(from:to:by:): from a number to another number with a specific step, excluding the last number.
• stride(from:through:by:): from a number to another number with a specific step, including the last number.
• stride(through:by:): from 0 to another number with a specific step, including the last number.

let end = 10
for i in stride(from: 2, to: end, by: 2) {
    print(i)
}
// 2, 4, 6, 8
for i in stride(from: 2, through: end, by: 2) {
    print(i)
}
// 2, 4, 6, 8, 10
for i in stride(through: end, by: 2) {
    print(i)
}
// 0, 2, 4, 6, 8, 10

Common Tricks

1. Check duplicate existence

When you need to check if there are duplicates in an array, you can use a set to store the elements you have seen so far.

func containsDuplicate(_ nums: [Int]) -> Bool {
    var set = Set<Int>()
    for num in nums {
        if set.contains(num) {
            return true
        }
        set.insert(num)
    }
    return false
}
// or simply
func containsDuplicate(_ nums: [Int]) -> Bool {
    return Set(nums).count != nums.count
}

2. Number from an array of digits characters

When you need to get a number from an array of digits characters, you can use reduce method of the array.

let digits = ["1", "2", "3"]
let num = digits.reduce(0) { $0 * 10 + Int($1)! }
// num: 123

If you need to backtrack the number for example from a binary tree, do not pass the array of characters, pass the integer number instead.
For example, to get the sum of all root-to-leaf numbers in a binary tree, you can pass the number to the next level of recursion.

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

func sumNumbers(_ root: TreeNode?) -> Int {
    func dfs(_ node: TreeNode?, _ num: Int) -> Int {
        guard let node = node else { return 0 }
        let num = num * 10 + node.val
        if node.left == nil && node.right == nil {
            return num
        }
        return dfs(node.left, num) + dfs(node.right, num)
    }
    return dfs(root, 0)
}

Don’t do things like this:

func sumNumbers(_ root: TreeNode?) -> Int {
    func dfs(_ node: TreeNode?, _ num: [Character]) -> Int {
        guard let node = node else { return 0 }
        let num = num + [Character(String(node.val))]
        if node.left == nil && node.right == nil {
            return Int(String(num))!
        }
        return dfs(node.left, num) + dfs(node.right, num)
    }
    return dfs(root, [])
}

3. Use Array to track different states

When you need to track different states in a problem, you can use an array to store the states of each element, by assigning different values to different states.
For example, in Leetcode problem 207. Course Schedule, you can use an array to store the states of each course, where 0 means unvisited, 1 means visiting, and 2 means visited.

// 0: not visited; 1: in one path, if appear again, cycle; 2: visited and this is a good one without cycle
var visitStates = [Int](repeating: 0, count: numCourses)

This is way better than using different sets to store different states.

4. Use tuple to get row and column in one line

When you need to get the row and column of a 2D array in one line, you can use tuple to get them.

let (rows, cols) = (rooms.count, rooms[0].count)

5. Directions in 2D array

When you need to traverse a 2D array in four directions, you can use an array of tuples to represent the four directions.

let directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for (dx, dy) in directions {
    let (nx, ny) = (x + dx, y + dy)
}

6. O(n) time complexity for finding the longest consecutive elements sequence

Given an unsorted array of integers, how to find the length of the longest consecutive elements sequence? The time complexity should be O(n).

The trick here is to use a set to store the numbers, and for each number, check if the number - 1 exists in the set. If it does not exist, it means this number is the start of a new sequence. Then, keep checking the next number until the number + 1 does not exist in the set. The length of the sequence is the difference between the current number and the start number.

func longestConsecutive(_ nums: [Int]) -> Int {
        var footprints = Set(nums)
        var result = 0
        footprints.forEach {
            guard footprints.contains($0 - 1) == false else { return }
            // Only runs, if this is the start of the sequence
            var streak = 1
            var next = $0 + 1
            while footprints.contains(next) {
                streak += 1
                next += 1
            }
            result = max(result, streak)
        }
        return result
    }

Why is the time complexity O(n)? Isn’t there a nested loop inside the forEach loop?
It’s because we only tap into the inside loop when we find the start of a sequence and thus all existing numbers greater than the start of the sequence will be visited in the inner loop only once. That means, the totoal times we visit all the numbers is O(n). Also, the outer loop only runs once for each number, so the time complexity for outer loop is O(n) as well. Therefore, the total time complexity is calculated as O(n) + O(n) = O(n).