Solving the ‘Two Sum Problem’ on LeetCode — Swift Solutions Walkthrough

Image Source

Introduction

In this post, we will delve into three distinct solutions to the Two Sum Problem, this time using Swift. By contrasting their time and space complexities, we’ll understand which method offers optimal performance. A comprehensive, step-by-step breakdown with annotated code for each solution follows the conclusion.

Problem Description

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

Function Prototype:

func twoSum(_ nums: [Int], _ target: Int) -> [Int]

Example 1:

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

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Solution 1: Brute Force Approach

This method involves using two loops to check each combination of numbers.

Swift Code:

class Solution {
    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 []
    }
}

Time Complexity: O(n²), We have two nested loops, where the outer loop runs ’n’ times and the inner loop runs ’n’ times for each iteration of the outer loop, resulting in a total of n*n = n² iterations.
Space Complexity: O(1), We are not using any additional data structures that grow with the size of the input. The space taken by the input and the space taken by the variables i and j are constant.

Solution 2: Sorting and Two Pointers Approach

By sorting the numbers and using two pointers, we can achieve a more efficient solution.

Swift Code:

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var numbers = nums.enumerated().sorted(by: { $0.element < $1.element })
    var left = 0
    var right = nums.count - 1

    while left < right {
        let sum = numbers[left].element + numbers[right].element
        if sum == target {
            return [numbers[left].offset, numbers[right].offset]
        } else if sum < target {
            left += 1
        } else {
            right -= 1
        }
    }
    return []
    }
}

Time Complexity: O(n log n),

• Sorting the nums array is the most time-consuming part of this solution, with a time complexity of O(n log n) for average and worst-case scenarios.
• After sorting, we just iterate through the array once using two pointers, which is O(n).
• Thus, the overall time complexity is dominated by the sorting part, making it O(n log n).

Space Complexity: O(n), We are using a sortedNums array to store pairs of numbers and their original indices. This array has a space complexity of O(n) since it grows linearly with the input size.

Solution 3: Dictionary Approach

Swift offers a Dictionary type, similar to hash maps in other languages.

Swift Code:

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

Time Complexity: O(n),

• We only iterate through the nums array once. For each number, we do constant-time operations: checking if a number exists in a dictionary and adding a number to a dictionary are both O(1) operations.
• Thus, the time complexity for this solution is O(n).

Space Complexity: O(n),

• The dictionary’s size can grow up to ’n’ in the worst case (where no two numbers sum up to the target until the very end).
• Thus, the space complexity is O(n).

Comparison of Swift Solutions

Now that we’ve walked through three distinct approaches to solve the Two Sum problem using Swift, let’s compare them in terms of their performance and use cases.

Brute Force Approach

Advantages:

• Simplicity: It’s the most straightforward solution, making it easy to understand and implement.
• Space Efficiency: This method only uses constant space.

Drawbacks:

• Time Inefficiency: With a time complexity of O(n²), it might not be the most optimal for large arrays.

Sorting and Two Pointers Approach

Advantages:

• Improved Time Complexity: Sorting the array and then using two pointers brings down the time complexity to O(n log n), which is more efficient than the brute force method.
• Readability: The logic behind this approach is intuitive, especially for those familiar with the two-pointer technique.

Drawbacks:

• Space Usage: Requires O(n) space because of storing indices in a sorted manner.
• Data Manipulation: The original data gets sorted, which might not always be desirable in certain applications.

Dictionary Approach

Advantages:

• Optimal Time Complexity: With a time complexity of O(n), it’s the fastest solution among the three for most cases.
• Swift-native: Making use of Swift’s powerful Dictionary type, this solution feels natural to the language.

Drawbacks:

• Space Overhead: This method uses a dictionary to store the array elements and their indices, resulting in a space complexity of O(n).

Conclusion

Selecting the optimal strategy is often a matter of weighing the trade-offs between time and space complexities. For the “Two Sum” problem in Swift, the Dictionary Approach stands out as the most efficient, particularly when working with larger datasets. However, as with all programming challenges, it’s essential to understand the nuances and potential benefits of each method, tailoring your solution to the specific needs of the application.

1. Swift’s Dictionary type
2. Two Sum problem on LeetCode

Thank you for reading! If you find this guide helpful, please consider highlighting, clapping, responding or connecting with me on Twitter/X as it’s very appreciated!

Also check out my other Leetcode Walkthrough Lists:

• Palindrome Number Problem

Step-by-Step Explanations with Code Comments

Solution 1: Brute Force Approach with Comments

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    // Step 1: Start the first loop to iterate over each number in the array.
    for i in 0..<nums.count {
        // Step 2: Begin the second loop to go through the numbers following the current one.
        for j in (i + 1)..<nums.count {
            // Step 3: Check if the current pair of numbers add up to the target.
            if nums[i] + nums[j] == target {
                return [i, j]
            }
        }
    }
    // Step 4: If no such pair is identified, return an empty array.
    return []
    }
}

1. Step 1: The initial loop starts, focusing on every individual number in the nums array.
2. Step 2: A secondary loop commences, which reviews the numbers positioned after the number identified by the outer loop.
3. Step 3: If the combination of the numbers from the two loops equals the target, their indices are returned.
4. Step 4: Should no such pair be detected, an empty array is produced.

Solution 2: Two Pointers with Sorting Approach

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    // Step 1: Pair numbers with their original indices.
    var numbers = nums.enumerated().sorted(by: { $0.element < $1.element })
    
    var left = 0
    var right = nums.count - 1
    
    // Step 2: Use two pointers, one at the start and another at the end.
    while left < right {
        let sum = numbers[left].element + numbers[right].element
        
        // Step 3: If the numbers at the two pointers add up to the target, return their original indices.
        if sum == target {
            return [numbers[left].offset, numbers[right].offset]
        } else if sum < target {
            left += 1
        } else {
            right -= 1
        }
    }
    
    // Step 4: If no suitable pair is found, return an empty array.
    return []
    }
}

• Step 1: Numbers are paired with their original positions in the numbers array.
• Step 2: Two pointers are used: left starting at the array's beginning and right at its end.
• Step 3: If the numbers pointed to by the pointers sum up to the target, their original positions are returned.
• Step 4: If no match is found, an empty array is returned.

Solution 3: Dictionary Approach with Comments

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    // Step 1: Initialize a dictionary for fast lookups.
    var dict: [Int: Int] = [:]
    
    // Step 2: Go through each number in the array.
    for (index, num) in nums.enumerated() {
        let complement = target - num
        
        // Step 3: If the complement is found in the dictionary, return its index along with the current number's index.
        if let complementIndex = dict[complement] {
            return [complementIndex, index]
        }
        
        // Step 4: Otherwise, store the current number and its index in the dictionary.
        dict[num] = index
    }
    
    // Step 5: If no matching pair is found, return an empty array.
    return []
    }
}

• Step 1: A dictionary named dict is initiated for rapid data lookups.
• Step 2: The entire list of numbers in the nums array is iterated through.
• Step 3: For each number, if its complement is found in the dictionary, the positions of both numbers are returned.
• Step 4: If the complement isn’t present in the dictionary, the current number and its position are saved in the dictionary (dict) for later lookups.
• Step 5: If no two numbers are found that add up to the target, an empty array is produced.