Hallo beren en zalmen, Leo hier. Today we will solve the very first Leetcode challenge called the Two Sum problem in Swift. This problem looks very simple at first. You just have to traverse the array with two loops and find what is asked. But that is the best approach?

What if we could optimize the time complexity using hash maps? This is the motivation of this article. We will check both approaches and see the advantages and disadvantages of each one. I always say that Leetcode is a very good source of humility for developers, because when you think you know it all, just go to Leetcode and try a hard challenge to feel again the feeling of how big your ignorance is in comparison to all the knowledge out there.

Fasten your seatbelts and let’s learn how to use hashmaps and achieve that in Swift. But first…

Painting of The Day

The painting today is a 1872 Luminist style art piece called Eaton’s Neck, Long Island by the master John Frederick Kensett. John Frederick Kensett lived from 1816 to 1872. Was a famous American artist and engraver. He was a member of the Hudson River School, Kensett’s signature works are calm landscape paintings of New England and New York, whose clear light and serene surfaces celebrate the permanent qualities of nature, and are associated with Luminism. 

Luminism is an American landscape painting style of the 1850s to 1870s, characterized by the effects of light in the landscape, through the use of upper perspective and the concealment of visible brushstrokes. Luminist landscapes emphasize tranquility, and often depict calm, reflective water and soft, calm clear skies.

I chose this painting because if you get this question in your interview you should be really tranquilized, as the landscapes of Luminism, because is a very easy question to go through.

The Problem – Two Sum Problem in Swift

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

The first thing we will do today is to solve this problem using brute force, I mean, we will generate all the possible combinations of two numbers without repetition. The problem is very to solve that way and you can solve it using two for loops.

See the solution below:

class Solution {

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

        for x in 0..<nums.count {
            for y in x+1..<nums.count {
                if nums[x] + nums[y] == target {
                    return [x,y]
                }
            }
        }
        
        return []
    }
}

The problem states that we can assume that all the input will have exactly one answer, this way this code is safe. And this solves the algorithm challenge.

And what is the problem with that? Well if you are into algorithms like me, every time you see a nested for loop your eye brown gets a little up and you think to yourself if there’s no better way to write that. Using nested for loops make this algorithm have a space complexity of O(1) and that is great! However… The time complexity is O(n^2) which is terrible. That will exponentially get slower with bigger inputs to the function. This means that:

• For nums array of size 2 – O(2ˆ2)  – The time complexity is 4 
• For nums array of size 5 – O(5^2) –  The time complexity is 25
• For nums array of size 15 – O(25ˆ2) – The time complexity is 225

  As you can see, it does not perform well. How could we reduce that time complexity?  

Using Hashmap to Decrease Time Complexity

As the title spoils, we will use a Hashmap implementation called Dictionary which has very cool initializers. We can use a little bit of math to use the keys of the dictionary as the results we are looking for. I’ll expand the explanation of the idea below. To achieve a solution in O(N) of this algorithm we will follow some steps:

1. Traverse the array using its index.
2. For each value in the array, we calculate the difference between the target number and the current value.
3. Then we check if the current number exists as a key in the dictionary. If yes we found the two indexes that can sum to the target.
4. If not, we add the difference as a key and the current index as the value of that dictionary key. This is the “ah ha!” of this algorithm.

  Think about it and let’s run this algorithm together. Image the array [2,7,4,9] and the target = 9. The algorithm will:

1. Start to traverse the array and the first index is 0 with a current value 2.
2. We calculate the difference between the target and the current value. The result of the difference in this scenario is 7.
3. Check if the hashmap contains any key that is current value because if yes, we found the other number we are looking for. But in this case, the dictionary is empty so we won’t find anything.
4. As the hashmap key check fails, we will store the difference as a key and the current index as a value. Why? Because for every iteration we are trying to search that value in the hashmap if we found we already know that we found the counterpart of what we are looking for.

  Check the final algorithm below:

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var dictResult = [Int: Int]()
        
        for x in 0..<nums.count {
            let difference = target - nums[x]
            
            if let index = dictResult[nums[x]] {
                return [x,index]
            } else {
                dictResult[difference] = x
            }
            
        }
        
        return []
    }
}

Time and Space Complexity – The Big O Notation

For the final solution using hashmaps, we have the time complexity of O(N) because now we are just traversing the array at most N times. In other words, if the input array is 2, we will check at most 2 items, if the input array is 10 we will check 10, and so on.

The space complexity now is O(N) and that is the drawback of this solution. The space required to solve this algorithm doubled in the worst-case scenario because now for every input array entry we will have one entry in our hashmap (dictionary).  

Continue Studying

Practice with stacks is a great exercise while preparing for algorithms interviews. Stacks are useful for a great number of problems. For example how to solve a matching parenthesis problem in Swift. If you told me that we could solve that with stacks before I knew the solution I wouldn’t believe it, but yes we can do that with stacks!

Today the first solution for the problem was a brute force approach to generate all the possibilities of Integers pairs in with the input data. But there are times that you want to generate that without repeating, and that’s when you will learn how to generate all the permutations without repeating numbers in Swift. Permutations are hard, I would keep an eye on them when studying for algorithms interviews.  

Summary – Two Sum Problem in Swift

Today we checked how to solve a very classic first problem in Leetcode. We learned two ways to solve, one using brute force with a very naive and another one using the power of the dictionaries in Swift to leverage our solution to increase its time complexity.

Fellow developers, that’s all. I hope you liked reading this article as much as I enjoyed writing it. If you want to support this blog you can Buy Me a Coffee or just leave a comment saying hello. You can also sponsor posts and I’m open to freelance writing! You can reach me on LinkedIn or Twitter and send me an e-mail through the contact page.

Thanks for the reading and… That’s all folks. Image Credit: Wikiart