Two Sum Problem Solution

Two Sum problem is a common question that you can find in several problem solving websites and also in technical interviews.

Problem Statement (leetcode):

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

You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Solutions:

Solution 1: Brute Force

The first solution that came up in my mind is to check every possibility, so it will be a loop inside a loop to check every possibility.

The outer loop runs from i = 0 to i = n-1 and the inner loop runs from j = i + 1 to j = n - 1.

In each iteration in the inner loop, it checks if the sum of the array with the index of the outer loop and the array with the index of the inner loop equals the target.

If nums[i] + nums[j] is equal to target, return [i, j], else continue.

Example:

The array: [15,11,7,2]. The target: 9.

The outer loop will start from i = 0 to i = n - 1 (n is the length of the array which is in this case is 4) and the inner loop will start from j = i + 1 to j = n - 1.

The first outer iteration, we start the first inner iteration and checking if the sum of the first index (0) of the array and the second index (0 + 1) of the array equal the target ( 15 + 11 = 26 != 9) and so on until we get these sums (15,11) (15,7) (15,2) in the first outer iteration, and at the second outer iteration we are going to do the same thing until we find the right sum (7,2) which will return the indexes: [2,3].

Code:

Python:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range((1 + i), len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

        return []

PHP:

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $n = count($nums);
        for ($i = 0; $i < $n; $i++) {
            for ($j = $i + 1; $j < $n; $j++) {
                if ($nums[$i] + $nums[$j] === $target) {
                    return [$i, $j];
                }
            }
        }

        return [];
    }
}

In the worst case, we will check every element, so its time complexity will be O(n^2).

Complexity:

Time Complexity: O(n^2)

Space Complexity: O(1)

Solution 2: Optimized Solution (Using Hashmap)

After solving the problem with the time complexity of O(n^2), we can solve it in linear time. The idea is we use a Hashmap to store the visited elements in the array. the Hashmap key is the element of the array, and the Hashmap value will be the index of this element.

Declare a Hashmap (dictionary in python), some languages like java force you to declare which data types are the key and the value, in our case both are integers.

We will use one loop to iterate through each element in the array.

In each iteration we will check if the result of target - theCurrentElement is in the Hashmap as a key, else, we will insert theCurrentElement as a key in the Hashmap and its index as a value in the Hashmap.

And we will repeat this until we find it.

Example:

The array: [27,3,7,11]. The target: 10.

We will declare seen as a Hashmap.

We will do a loop that iterate our array.

In the first iteration we will store the result of ( target: 10 - currentElement: 27) in a variable called remaining which will be in this case -17, then we will check if this number is in the seen, the seen is empty so we will store 27 in the seen as a key and the index 0 as a value.

In the second iteration we will see if the remaining is in the seen, in this case in 7, 7 is not in the seen, so we will store again in the seen, the current element 3 as key and its index 1 as a value.

In the third iteration we will see if the remaining 3 is in the seen, we already stored 3 in the seen, so now we can return the value of seen using the key of 3 and the index of the current element.

Code:

Python:

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}
        for i, value in enumerate(nums):
            remaining = target - value
            if remaining in seen:
                return [seen[remaining], i]

            seen[value] = i

Complexity:

Time Complexity: O(n)

Space Complexity: O(n)