In this post, we'll walk through solving the Two Sum problem using Swift. The Two Sum problem is a classic coding challenge, often used in technical interviews, and is one of the first problems you encounter when learning about algorithms. The goal of the problem is simple: given an array of integers, find two numbers that add up to a given target, and return their indices.

We’ll explore the problem in depth, starting with a brute force solution that is easy to understand but not very efficient. Then, we'll move to a more optimal solution using a dictionary (HashMap equivalent in Swift), which reduces the time complexity significantly. This post will provide step-by-step instructions, code examples, and explanations, ensuring that you fully grasp how to solve the problem in Swift.

Problem Statement

The problem can be stated as follows:

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

Example:

Input: nums = [2, 7, 11, 15], target = 9  
Output: [0, 1]  
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Assumptions:

  1. There will always be exactly one solution.
  2. You may not use the same element twice.
  3. The solution can be returned in any order.

Approach 1: Brute Force

The brute force approach is the most straightforward way to solve the problem. In this method, we check each pair of numbers in the array and determine if their sum equals the target. While this approach is easy to understand and implement, it’s not efficient because it requires checking every possible pair, resulting in a time complexity of O(n²).

Steps:

  1. Use two nested loops to check each pair of numbers in the array.
  2. For each pair, check if the sum of the two numbers equals the target.
  3. If a match is found, return the indices of the two numbers.

Code Implementation:

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    for i in 0..<nums.count {
        for j in i + 1..<nums.count {
            if nums[i] + nums[j] == target {
                return [i, j]
            }
        }
    }
    return []
}

Explanation:

  • The outer loop selects each number in the array one by one.
  • The inner loop checks all the other numbers after the current number to see if any pair adds up to the target.
  • When we find a pair that sums up to the target, we return their indices as a result.

Time Complexity:

  • Time Complexity: O(n²) – This is because we are iterating over every pair of numbers. The outer loop runs n times, and for each iteration, the inner loop runs (n - 1) times.
  • Space Complexity: O(1) – The algorithm uses constant space, as we are not storing anything other than the result.

Example Test Case:

let nums = [2, 7, 11, 15]
let target = 9
let result = twoSum(nums, target)
print(result)  // Output: [0, 1]

Limitations:

  • Efficiency: The brute force solution has a time complexity of O(n²), which makes it impractical for large arrays.
  • Nested Loops: The use of nested loops leads to performance bottlenecks when working with large datasets.

Approach 2: Using a Dictionary (Optimized)

To improve the efficiency of the solution, we can use a dictionary (also called a HashMap in other languages) to store the numbers we’ve seen so far and their corresponding indices. This allows us to check whether the complement of the current number (i.e., target - current_number) has already been encountered, in constant time.

This optimized approach reduces the time complexity from O(n²) to O(n), as we only need to iterate through the array once while performing constant-time lookups in the dictionary.

Steps:

  1. Initialize an empty dictionary to store the numbers and their indices.
  2. Iterate through the array and, for each number, compute its complement (i.e., target - current_number).
  3. If the complement is found in the dictionary, return the indices of the complement and the current number.
  4. If the complement is not found, add the current number and its index to the dictionary for future reference.

Code Implementation:

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var numDict = [Int: Int]()
    
    for (i, num) in nums.enumerated() {
        let complement = target - num
        
        if let complementIndex = numDict[complement] {
            return [complementIndex, i]
        }
        
        numDict[num] = i
    }
    
    return []
}

Explanation:

  • We declare a dictionary numDict where the keys are the numbers in the array and the values are their corresponding indices.
  • For each number in the array, we calculate its complement (target - num).
  • We check if the complement is already in the dictionary:
    • If it is, this means we have found two numbers that add up to the target, so we return their indices.
    • If it’s not in the dictionary, we add the current number and its index to the dictionary.

Time Complexity:

  • Time Complexity: O(n) – We traverse the array only once, and dictionary lookups and insertions take constant time, O(1).
  • Space Complexity: O(n) – We use extra space to store up to n elements in the dictionary.

Example Test Case:

let nums = [3, 2, 4]
let target = 6
let result = twoSum(nums, target)
print(result)  // Output: [1, 2]

Explanation:

In this case, nums[1] + nums[2] = 2 + 4 = 6, so the function returns [1, 2].

Detailed Walkthrough:

  • Start with an empty dictionary, numDict = [:].
  • On the first iteration (i = 0), num = 3. The complement is 6 - 3 = 3. Since 3 is not in numDict, we add 3: 0 to the dictionary.
  • On the second iteration (i = 1), num = 2. The complement is 6 - 2 = 4. Since 4 is not in numDict, we add 2: 1 to the dictionary.
  • On the third iteration (i = 2), num = 4. The complement is 6 - 4 = 2. This time, 2 is in numDict, so we return [1, 2] as the result.

Edge Cases

While the problem guarantees exactly one solution, you should still account for various edge cases during implementation:

  1. Negative and Positive Numbers:
    The array may contain both negative and positive numbers. Ensure that the solution works for both.

    let nums = [-3, 4, 3, 90]
let target = 0
if let result = twoSum(nums, target) {
    print(result)  // Output: [0, 2]
}

  2. Duplicate Values:
    The array may contain duplicate values, and the solution should still return the correct indices.

    let nums = [3, 3]
let target = 6
if let result = twoSum(nums, target) {
    print(result)  // Output: [0, 1]
}

  3. Array with Only Two Elements:
    Since the problem guarantees at least two elements, the array can have exactly two elements, and the solution should still work.

    let nums = [1, 4]
let target = 5
if let result = twoSum(nums, target) {
    print(result)  // Output: [0, 1]
}

  4. Zeros in the Array:
    If the array contains zeros, the solution should correctly handle the target involving zero.

    let nums = [0, 4, 3, 0]
let target = 0
if let result = twoSum(nums, target) {
    print(result)  // Output: [0, 3]
}

  5. Large Inputs:
    If the array contains a large number of elements, the hash map approach ensures efficiency even with significant data size.

    let nums = Array(0..<100000)
let target = 199999
if let result = twoSum(nums, target) {
    print(result)  // Output: [99998, 99999]
}

Optimizations and Best Practices

1. Dictionary Lookup Optimization:

In Swift, dictionary lookups and insertions are expected to take constant time, O(1). Using a dictionary to store numbers and their indices is what allows us to bring down the time complexity to O(n).

2. Returning Early:

Once we find the indices of the two numbers that sum to the target, we return immediately without continuing to process the rest of the array. This ensures that the function performs as efficiently as possible.

3. Array Index Handling:

The function returns the indices of the numbers in the order they appear in the array, which satisfies the problem’s requirement of returning the indices in any order. By using enumerated() to loop over both the indices and the values of the array, we avoid any confusion regarding index tracking.

Conclusion

We’ve explored two approaches for solving the Two Sum problem in Swift: a brute force solution and an optimized solution using a dictionary. While the brute force solution is simple to implement, it has poor performance with large arrays due to its O(n²) time complexity. The dictionary-based solution, however, provides a much more efficient O(n) solution by utilizing constant-time lookups and insertions.