Two Sum Problem - Leetcode

Problem Statement

Consider you are given an array of integers and a target sum, return indices of two numbers in the array such that they add up to the given target. You may assume that each input would have exactly one solution. Also, you cannot use the same element twice. You are allowed to return the answer in any order

Examples

Example 1:

Input: nums = [7,2,13,11], target = 9
Output: [0,1]

Example 2:

Input: nums = [7,3,5], target = 8
Output: [1,2]

Solutions

Let us try to understand the problem statement first. Here we are given an array of integer elements and a target sum. We are supposed to write an algorithm that returns indices of two elements in this array such that, when we add these two elements it should be equal to the target sum given.

For instance, in example 1 [7,2,13,11] is the given array and the given target sum = 9. If we take a look at the given array, the pair which adds to the target sum 9 is (7,2) i.e. 7+2 = 9. So our algorithm should return (0,1) as the result because these are the indexes of elements 7 and 2 respectively in the given array.

Similarly for the array in example 2 [7,3,5] output is (1,2) because these are the indexes of elements 3 and 5 respectively which add up to the target sum 8.

Note: If there are multiple such pairs we need to return the indexes of the first pair from left.

It is stated in the problem statement that we can return the indices in any order. Let us understand this using the first example. The output for this example is [0,1], so when the problem statement says we can return the indices in any order what it means is that we can return either [0,1] or [1,0] as our output, both will be considered correct. Same for the second one, we can return either [1,2] or [2,1].

Solution 1: Brute Force

A straightforward solution to this problem is to check for every possible pair present in the given array.

For a given input array nums we need to do the following steps:

• Run two loops and check for every combination in the given array.

• Fix the outer loop at a specific index and move the inner loop to get all the possible pairs. The outer loop runs from i=0 to i=n-2 and the inner loop runs from j=i+1 to j=n-1.

• In each iteration of the inner loop check if the numbers represented by the outer and inner loop indexes add up to the target sum.

• If nums[outerLoopIndex] + nums[innerLoopIndex] is equal to the target, return [outerLoopIndex, innerLoopIndex] as the result. Else continue iteration to check for the next pair.

• Repeat the above steps until you find a combination that adds up to the given target.

For example, for array [7,2,13,11] and target sum 24, we fix the outer loop at index i=0 i.e element 7 and check it with all possible values of the inner loop from j=i+1 to j=n-1, i.e from index 1 to 3. So, we will be checking the following pair of elements in the first iteration of the outer loop: (7,2) (7,13) and (7,11). Now we increment the outer loop index i by 1 and check it with indices 2 to 3 (i+1 to n-1) of the inner loop. We repeat this until we return the correct output.

Note: n here is the size of the array.

JavaScript

function twoSum(nums, target) {
    const n = nums.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

Python3:

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

In the worst case, this algorithm has a running time complexity of O(n^2). The worst case would occur when the required combination is the last combination to be checked by our loops.

Complexity Analysis

• Time Complexity: O(n^2)

• Space Complexity: O(1)

Solution 2: Using Hashmap

It is possible to solve this problem in linear time. The idea is to make use of a hashmap(object in javascript) to store the indices of the elements that are already seen. Hashmap "key" is the number in the given input array (You add this to the hashmap as you visit each element). Hashmap "value" is the index of the number in the array represented by the hashmap key.

• Create a hashmap that accepts integer datatype as key and value.

• Iterate through each element in the given array starting from the first element.

• In each iteration check if the required number (required number = target sum - current number) is present in the hashmap.

• If present, return [required number index, current number index] as the result.

• Otherwise, add the current iteration number as the key and its index as value to the hashmap. Repeat this until you find the result

Simulation

Consider you are given the below input array and target = 24.

Let currIdx be the variable representing the current element under process and let idxMap be our index map. Cells marked in orange indicate the currently processed array element.

In the beginning, currIdx\=0 and idxMap is empty as shown in the first figure below. Next, we check if the required number = target - current number is present in the idxMap.

Required number = 24 - 7 = 17 is not present in our hashmap, so we add 7 as idxMap key and 0 as idxMap value (0 is the index of 7 in the input array) as shown in figure 2 below.

Next, we move on to the second element in the array by incrementing the current index. So currIdx\=1 which points to element 2 in the array. Again we check if the required number is present in idxMap, the required number = 24 - 2 = 22 is not in our hashmap so we add 2 to the hashmap along with its index 1.

Increment current index, currIdx\=2, which is element 13 in the input array. Again required number = 24 - 13 = 11 is not in our hashmap. Add {13:2} to idxMap. The same is shown in the diagram below.

Our hashmap now contains 3 elements 7, 2 and 13 along with their indexes. Again we increment currIdx, currIdx\=3 which is element 11.

Now required number = 24 - 11 = 13 is present in idxMap (shown by the cell highlighted in green in the second figure below). That means we have found the pair which adds up to the target sum 24, i.e. (11, 13). Therefore we return the indexes of 11 and 13 as our result. Index of 11 is nothing but currIdx which is 3 and the index of 13 can be found from our hashmap which is 2, therefore we return (3, 2) or (2, 3) as our result.

JavaScript:

function twoSum(nums, target) {
    const indexMap = new Map();

    for (let currIndex = 0; currIndex < nums.length; currIndex++) {
        const currNum = nums[currIndex];
        if (indexMap.has(target - currNum)) {
            return [indexMap.get(target - currNum), currIndex];
        }
        indexMap.set(currNum, currIndex);
    }

    return [];
}

Python3:

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

           if remaining in seen:
               return [i, seen[remaining]]

           seen[value] = i
       return []

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

The running time complexity of this solution is O(n) since we would have to go through all array elements in the worst case. As described in two-sum solution 1, the worst case occurs when the required combination is the last combination to be checked.

Also, the auxiliary space required is O(n) since we store the array elements in hashmap and in the worst case we would end up storing all values in the given array in hashmap.

That is all for this article, thank you for taking your time to read this. If you have any questions, please let me know in the comments section below, I will be more than happy to answer.