Two Sum Problem

Here is a classic problem that has been given on plenty of interviews.

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Now there are a couple of ways to solve this problem. The first way you might think is to look at it and approach it through a brute force method.

Brute Force Method 👊

I see that I need two different indexes so I could use two for loops and propagate through this list comparing every possible combination to see if I have a pair that hits the target.

Code for two for loops a brute force method to solve this problem
In this scenario, we are going to loop through the array with both for loops allowing you to compare every single possible combination. This is obviously not the most efficient way as it will yield a big O of (n²) due to both for loops. In the event that there is a long list of numbers it can be less likely that your code will pass in the given time it needs.

Dictionary Approach:

Now looking at how to better improve this solution there is one data structure called a dictionary that will definitely assist us. A dictionary makes use of a key-value pair, this is can be extremely useful given that the search of a Dictionary is big o(1).

Code for two sum problem dictionary creation then search for pair
Here we are building a dictionary with the key being the number and the value being the index the number exists. Creating a dictionary allows us to search for the value as we go. In our next for loop as we search for the other number to complete the sum that hits the target we only have to iterate through the array ones at a time giving us a big-O (n). That being said all though we were able to reduce the big-O in time by not using a double for loop we increased the space complexity from the creation of the dictionary.

Better Dictionary Approach:

Now how can we make this a bit more efficient? Well, we can remove the need to have a separate loop for creating the dictionary by using a if-else block.

Code for two sum problem dictionary creation and search for pair
Hope you liked this post, please follow and clap for more! 🙃

Comments

[Ahmedur Rahman Shovon]

Hello @amsuarez ,
Thanks for adding a popular problem with easy explanation.

Here is my approach to solve the problem using Python.
I have included both brute force(O(n^2)), dictionary method and tested both method for several test cases:

def two_sum_brute_force(nums, target):
    total_numbers = len(nums)
    for i in range(total_numbers):
        for j in range(i+1, total_numbers):
            if nums[i]+nums[j] == target:
                return [i, j]

def two_sum_dictionary(nums, target):
    total_numbers = len(nums)
    d = {}
    for i in range(total_numbers):
        current_value = nums[i]
        other_value = target - current_value
        if other_value in d:
            return list(sorted([i, d[other_value]]))
        if current_value not in d:
            d[current_value] = i


if __name__ == "__main__":
    test_cases = [
        [[2, 7, 11, 15], 9],
        [[2, 7, 11, 15], 13],
        [[2, 7, 11, 15], 26]
    ]
    expected_results = [
        [0, 1],
        [0, 2],
        [2, 3],
    ]
    total_test_cases = len(test_cases)
    for i in range(total_test_cases):
        nums, target = test_cases[i]
        expected_result = expected_results[i]
        # Test Brute Force Solution
        result = two_sum_brute_force(nums, target)
        assert_message = "two_sum_brute_force({}, {}) returns {}. Expected {}".format(
            nums, target, result, expected_result
        )
        assert result == expected_result, assert_message
        # Test Dictionary Solution
        result = two_sum_dictionary(nums, target)
        assert_message = "two_sum_dictionary({}, {}) returns {}. Expected {}".format(
            nums, target, result, expected_result
        )
        assert result == expected_result, assert_message
    print("Passed all {} test cases".format(total_test_cases))

[Austin]

Thanks for sharing love to see everyone's approach!