loading...

Discussion on: Two Sum Problem

Collapse
arsho profile image
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))
Collapse
snappydevlpr profile image
Austin Author

Thanks for sharing love to see everyone's approach!