Solving problem: Two Sum

Table of Contents

---

• What is the Two-Sum Problem
• Example
• Test Cases
• Solution O(n^2)
• Solution O(n)

What is the Two-Sum Problem

---

Suppose you are given an array of integers and you need to find out what number in the array add up to the specific target. You need to return the indices of the two numbers.

You may assume that each input would have exactly one solution, and you cannot not use the same element twice.

Example

---

In this example, you are provided with an input of integers. The length of this array will vary depending on every testcase. You will get atleast 2 items in the array.

INPUT:
   target = 9,
   nums = [2, 7, 11, 15]

OUTPUT: [0, 1]

Explanation:

Test Cases

---

INPUT:
   target = 6,
   nums = [3,2,4]

OUTPUT: [1,2]

INPUT:
   target = 6,
   nums = [3,3]

OUTPUT: [0, 1]

HINT: Can you come up with an algorithm that is less than O(n2) time complexity?

Solution O(n^2)

---

The solution to this problem is pretty simple. There can be multiple solutions to the problem. Let's see how to solve this problem.

• Javascript

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

• Python

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

This code defines a function named twoSum which takes two parameters: an array of integers nums and a target integer target.

The function uses two nested for loops to iterate through every possible pair of indices in the nums array. The inner loop starts at the beginning of the array every time the outer loop iterates. To avoid adding the same element twice, the function uses a conditional statement to skip over the iteration when the i and j indices are equal.

Within the inner loop, the function checks whether the sum of the numbers at the current i and j indices equals the target value. If a pair of indices is found that match the target value, the function immediately returns an array containing the two indices.

This code solves the problem of finding two indices of elements in an array that add up to a given target value. However, this solution has a time complexity of O(n^2), which makes it inefficient for larger input sizes. For very large input sizes, it could take a long time to find the solution.

Solution O(n)

---

• Javascript

var twoSum = function (nums, target) {
	const hash = [];

	for (let i = 0; i < nums.length; i++) {
		let n = nums[i];
		if (hash[target - n] != undefined) {
			return [hash[target - n], i];
		}
		hash[n] = i;
	}
};

• Python

def twoSum(self, nums: List[int], target: int) -> List[int]:
   i = 0
   hash = {}

   for x in nums:
      if(hash.get(target-x) != None):
         return [hash.get(target-x), i]

      hash[x] = i
      i = i + 1

The function initializes an empty hash array to store previously visited elements and their indices. It then iterates through each element of the nums array using a for loop and creates a variable n that stores the value of the current element at index i.

Within the loop, the function checks if target-n exists in the hash array. If it does, then the function returns an array containing the indices of the two elements that add up to the target value. The first index is the value at hash[target-n], which is the index of the previously visited element, and the second index is i, which is the index of the current element being iterated over.

If target-n does not exist in the hash array, then the current element n and its index i are added to the hash array. This allows the function to keep track of previously visited elements and their indices and quickly check whether the complement of the current element exists in the array.

This solution has a time complexity of O(n) which is more efficient than the O(n^2) solution in the previous solution for larger input sizes.

 

🔝 Go To Beginning 🔝