LeetCode – Two Sum

Let’s continue working with more LeetCode problems, this time focusing on an easy one.

We need to find if, in a given array, we can find two numbers such that they can be added up to a certain target value. We can be certain that there will be only one solution.

Solution#

Brute force#

As with other problems, one first approach would be to compare all possible combinations to find the two numbers that adds to the target. This solution is easy to implement but it has a bad time performance of $O(n^2)$.

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

You may be wondering why we have (i + 1) in the inner loop. This is to avoid comparing the same value with itself, if we do that we may get a wrong solutions to certain inputs (one example: [3, 2, 4] and 6).

This solutions solves the problem, but it’s slow with a time complexity of $O(n^2)$. Let’s try to find another approach to improve this.

Using a Hash Table#

Let’s try to think of the problem as a math equation, we want two values that add up to a certain third value.

This can be represented as the following simple equation.

$$ a + b = target $$

How can this help us? Notice that we already have two of three values of the equation for any given iteration. So we are searching for the third value, this is the value $b$ that can solve the previous equation.

$$ b = target - a $$

This missing value $b$ is just the difference between the target and the current value.

By knowing this, we can store somehow the values and indices of the array and check if some $b$ that can solves the equation is presented in our storing objet. When that happens we are done, and we can return the indices for the current value and the one stored for $b$.

We need an object able to save a value with its index, this is a perfect use for a Hash table. In Swift we have one already build-in, it’s called a Dictionary.

This data structure saves a key-value pair, like a real dictionary do. It’s also important to know that insertion and retrieval takes $O(1)$ time complexity, which make it ideal for this problem.

Here is the solution using this approach.

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    // Storing key: number, value: index in array
    var dic = [Int:Int]()
    
    for (currentNumberIndex, value) in nums.enumerated() {
        let diff = target - value
        
        if let missingNumberIndex = dic[diff] {
            return [missingNumberIndex, currentNumberIndex]
        }
        
        dic[value] = currentNumberIndex
    }

    return [-1,-1]
}

This solution is easy to read and quite efficient because we only check each element once. The time complexity is $O(n)$ and since we are storing each element in a dictionary, the space complexity is also $O(n)$.

Here we are using some cool Swift features:

• .enumerated(): returns a tuple containing the current index and value.
• Checking for optionals in dictionaries: we are using a if let statement to check whether the value we are missing is already on the dictionary.

Conclusion#

This problem provides valuable insights into the efficient use of dictionaries in Swift. We started with a brute force approach that had a time complexity of $O(n^2)$, but then we optimized our solution using a hash table (Dictionary) to achieve a linear time complexity of $O(n)$. By employing the concept of key-value pairs and leveraging Swift’s features like .enumerated(), we were able to find a more elegant and efficient solution.

Exploring different approaches and understanding when to use data structures like dictionaries can greatly enhance our problem-solving skills as developers. Happy coding!