The two sum problem is a classic coding challenge required in many tech interviews, and the #1 challenge on leetcode.com.

Usually, one is given an unsorted array of integers and a target integer. In this scenario, your goal is to write an efficient algorithm that returns if there are two elements in the array that add up to the target. You are required to either return the indices or the integers themselves.

The example in this post assumes that there will be an answer and there will only be one pair that sums up to the target.

In your potential interview, it is important that you specifically ask your interviewer if they would like you to return all pairs, only the first pair, or what they want you to return if there is no pair at all.

The Brute Force Solution

The "brute force solution" is the least efficient way of solving any problem. It has the worst time/space complexity–but, it is a solution. However, it is better than nothing if you are unable to come up with a more advanced approach, and you may score points by being able to be coached into the proper direction.

For this example, we are going to use nested loops. There is an outer loop that iterates through every element and an inner loop to find two elements that sum up to k.

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

    // Iterate through every element in numbers
    for (i, number1) in numbers.enumerated() {

        /**
        For every iteration, 
        iterate through numbers,
        where i does not equal j.
        */
        for (j, number2) in numbers.enumerated() where i != j {
   
            // Get the sum of number1 and number2
            let sum = number1 + number2
        
            // Check if sum equals the target
            if sum == target {
      
              // If so, return the indicies or numbers
              return [i, j] // or [number1, number2]
            }
        }
    }
    
    /**
    Return an empty array if unable to
    find a pair that adds up to the target.
    */
    return []
}

The time complexity of this approach is O(n^2). As an example: If there are 100 elements in the array, you iterate 100 * 100-1, in short 100^2 or O(n^2).

Now, let's look at a more efficient solution. Efficiency is important when considering scalability. For example, the array could contain thousands or millions of elements.

Hash Map for a Linear Solution

Using a Hash Map, store every element of the array in the map and check if there is an element in the map/dictionary that–with the element at current index–sums up to k.

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

    /**
    Init an empty dictionary.
    The value will be the array element.
    The key will be the index of the element.
    */
	var hashMap: [Int: Int] = [:]

    // Iterate through every element in numbers
    for (i, element) in numbers.enumerated() {
    
    	/**
        Check if the hashMap contains an element
        that with the current element, sums up to k.
        */
    	if let mapped = hashMap[target - element] {
        	return [i, mapped]
        }
        
        // Add the element to the dictionary
        hashMap[element]
    }
    
    /**
    Return an empty array if unable to
    find a pair that adds up to the target.
    */
    return []
}

This is the best solution with a linear runtime. At most, we are checking every element once. The downside of this solution (which your interviewer may ask) is, that it requires O(n) space, given that we potentially need to store every element in the dictionary/hash map.

My Take:

We can always buy more space... We can always buy more memory... but we can't buy more time.