Two Sum

The task is to find two numbers in an array that add up to a specific target.

You can find the original problem described on LeetCode.

Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

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]

Constraints

• 2 <= nums.length <= 10⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• Only one valid answer exists.

Problem Solving

A brute force solution

There is a simple method to solve this problem:
Use two for loops to iterate through the elements and find the combination.

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 []
}

Pretty straight forward and easy to implement, right? 😉
The time complexity for this solution is O(n²).

However, this is definitely not a good solution. 🙈

Hash Table

A good solution is to use a hash table (here we use Swift’s Dictionary) to store the numbers we have seen so far and their corresponding indices. This way, we can check in constant time if the complement of the current number (target - current number) exists in the hash table.

Here, let me show you. 👨‍🏫

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    // Store the number and its index
    var dictionary: [Int: Int] = [:]
    
    for (i, num) in nums.enumerated() {
        // Check if the complement (target - num) is already in the dictionary
        if let item = dictionary[target - num] {
            // If found, return the indices
            return [item, i]
        }
        // Store the current number and its index
        dictionary[num] = i
    }
    
    // Corner case (the problem states there must be a solution)
    return []
}

Complexity Analysis

Time Complexity

As mentioned before, the first solution has time complexity O(n²), where n is the number of elements in the array.
The time complexity for the second solution is O(n). We traverse the list containing n elements exactly once, and each lookup in the dictionary costs O(1) time.

Space Complexity

The space complexity of the first solution is O(1) since we do not create any extra space and return the indexs of the existing arrays.
The second solution, even though is better, in terms of time complexity, it costs O(n) space. The extra space required depends on the number of items stored in the dictionary, which stores at most n elements.

Conclusion

The solution here demonstrates the use of hash tables for efficient lookups.
This approach ensures a linear time complexity, making it highly efficient for large inputs. 🤓