Algorithms in Swift: Find two elements in the array that add up to given number

By popular demand, I’m starting a semi-regular series exploring common algorithm questions asked during iOS interviews. Let me know on Twitter if you’d like to see any particular algorithm or coding question answered.

In this post, let’s solve the following problem in Swift:

Given an array of numbers and another number called sum, find all pairs of numbers in the array that add up to the given sum.

For example, given an array of [2, 4, -1, 3, 0, 6] and the sum being 5, the output of the function should be: (2,3), (-1,6). That is, we found two pairs of elements from the input array that when added together, equal to the sum (being 5) because 2 + 3 = 5 and (-1) + 6 = 5.

There are two ways we could approach this problem.

Use Hashing

This method runs in O(n) and allows us to find all pairs of numbers from the input array that add up to the given sum.

The idea is to first initialize an empty dictionary and then, while iterating through the input array, check if the dictionary has a key equal to the difference between the sum and current element. If it does, then print the current element and the key from the dictionary. Then, add the current element to the dictionary as a key.

The code for this solution should look like that:

var inputArray = [2, 4, -1, 3, 0, 6]
var sum = 5

func findTwoSumHash(inputArray: [Int], sum: Int) {
    var dictionary: [Int: Int] = [:]
    
    for element in inputArray {
        let difference = sum - element
        
        if let _ = dictionary[difference] {
            print("(\(element), \(difference))")
        }
        
        dictionary[element] = element
    }
}

findTwoSumHash(inputArray: inputArray, sum: sum)

The output should have the following: (3, 2), (6, -1)

Use Sorting

This method runs in O(n log n) because we’re using the built in sorted() method. Use this method if you’re asked to find if only one pair of elements exist in the input array that add up to the given sum.

The idea behind this method is to first sort the input array and then iterate through it using left and right indexes set to 0 (leftmost index) and the size of the input array minus 1 (rightmost index). Keep looping while left index is smaller than the right index. For each pair of elements, check if they add up to the given sum. If so, print them and exit the function. Otherwise, check if their sum is less than the given sum, and if so, increment the left index. Otherwise, decrement the right index.

The code for this solution looks like that:

func findTwoSumSorted(inputArray: [Int], sum: Int) {
    let sortedArray = inputArray.sorted()
    var leftIndex = 0
    var rightIndex = sortedArray.count - 1
    
    while leftIndex < rightIndex {
        let leftElement = sortedArray[leftIndex]
        let rightElement = sortedArray[rightIndex]
        let currentSum = leftElement + rightElement
        
        if currentSum == sum {
            print("(\(leftElement), \(rightElement))")
            return
        } else if currentSum < sum {
            leftIndex += 1
        } else {
            rightIndex -= 1
        }
    }
}

findTwoSumSorted(inputArray: inputArray, sum: sum)

The output should only include one pair: (-1, 6)

Read more about the sorted() method on Apple’s documentation website.

Related tutorials: