Greetings, traveler!

The Two Sum problem is a classic interview question and a great exercise in algorithmic thinking. The task is simple to state, but it opens the door to multiple solution strategies, each with its own trade-offs.

Problem statement:
Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

Approach 1: Sorting and Two Pointers

One intuitive way to approach this problem is by using the two pointers technique. The idea is to first sort the numbers while keeping track of their original indices. Then, we place two pointers at opposite ends of the sorted array and move them towards each other depending on the current sum.

Implementation

class TwoPointersSolution {
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        // Step 1: Build an array of (index, value) pairs and sort them by value.
        var sortedPairs = numbers.enumerated().sorted(by: { $0.element < $1.element })
        
        // Step 2: Place two pointers at opposite ends of the sorted array.
        var lowPointer = 0
        var highPointer = numbers.count - 1
        
        // Step 3: Check the sum of the values at the two pointers.
        while lowPointer < highPointer {
            let currentSum = sortedPairs[lowPointer].element + sortedPairs[highPointer].element
            
            if currentSum == target {
                return [sortedPairs[lowPointer].offset, sortedPairs[highPointer].offset]
            } else if currentSum < target {
                lowPointer += 1
            } else {
                highPointer -= 1
            }
        }
        
        return []
    }
}

class TwoPointersSolution {
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        // Step 1: Build an array of (index, value) pairs and sort them by value.
        var sortedPairs = numbers.enumerated().sorted(by: { $0.element < $1.element })
        
        // Step 2: Place two pointers at opposite ends of the sorted array.
        var lowPointer = 0
        var highPointer = numbers.count - 1
        
        // Step 3: Check the sum of the values at the two pointers.
        while lowPointer < highPointer {
            let currentSum = sortedPairs[lowPointer].element + sortedPairs[highPointer].element
            
            if currentSum == target {
                return [sortedPairs[lowPointer].offset, sortedPairs[highPointer].offset]
            } else if currentSum < target {
                lowPointer += 1
            } else {
                highPointer -= 1
            }
        }
        
        return []
    }
}

Complexity

• Time: O(nlogn), dominated by the sorting step.
• Space: O(n), since we store pairs of values and their indices.

This approach is clean and works well, especially if the array is already sorted. However, if we must always sort, the performance is not optimal compared to other methods.

Approach 2: Dictionary (Hash Map)

A more efficient approach is to use a dictionary (hash map) to store numbers as we iterate through the array. For each element, we check if the complement (target - currentValue) is already in the dictionary. If it is, we’ve found our pair.

Implementation

class HashMapSolution {
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        // 1. Initialize a lookup dictionary.
        var lookupMap: [Int: Int] = [:]
        
        // 2. Iterate through each element and calculate the needed value.
        for (position, currentValue) in numbers.enumerated() {
            let neededValue = target - currentValue
            
            if let matchedIndex = lookupMap[neededValue] {
                return [matchedIndex, position]
            }
            
            lookupMap[currentValue] = position
        }
        
        return []
    }
}

class HashMapSolution {
    func twoSum(_ numbers: [Int], _ target: Int) -> [Int] {
        // 1. Initialize a lookup dictionary.
        var lookupMap: [Int: Int] = [:]
        
        // 2. Iterate through each element and calculate the needed value.
        for (position, currentValue) in numbers.enumerated() {
            let neededValue = target - currentValue
            
            if let matchedIndex = lookupMap[neededValue] {
                return [matchedIndex, position]
            }
            
            lookupMap[currentValue] = position
        }
        
        return []
    }
}

Complexity

• Time: O(n), since we process each element once and dictionary operations are O(1) on average.
• Space: O(n), for storing the elements in the dictionary.

This solution is generally the preferred one for the Two Sum problem. It offers linear time complexity and is straightforward to implement in Swift.

Conclusion

Both solutions solve the Two Sum problem correctly, but they highlight different algorithmic strategies:

• Two Pointers: O(nlog⁡n) time, useful when the input is already sorted or when sorting provides additional benefits.
• Dictionary: O(n) time, the most efficient in the general case and widely used in practice.